Concept Notes — Bit Manipulation (ভেতর থেকে বোঝা)¶
এই note-এর লক্ষ্য একটাই: bit operation গুলোকে মুখস্থ formula না বানিয়ে ছবি বানানো। প্রতিটা trick-এর পেছনে একটা ছবি আছে — সেটা একবার দেখলে আর ভোলা যায় না।
1. Binary মানে place value-র টেবিল¶
Decimal-এ 234 মানে: 2 × 100 + 3 × 10 + 4 × 1। ঘরগুলো 10-এর power।
Binary-তে ঘরগুলো 2-এর power: ... 8 4 2 1।
তাহলে "13-এর binary কী?" প্রশ্নটা আসলে: "8, 4, 2, 1 — কোনগুলো যোগ করলে 13 হয়?"
Code-এ বের করার নিয়ম Level 0-এর digit extraction-এরই যমজ ভাই — শুধু 10-এর জায়গায় 2:
def to_binary(n):
bits = []
while n > 0:
bits.append(n % 2) # last bit
n //= 2 # bit টা ফেলে দাও
return bits[::-1] or [0]
print(to_binary(13)) # [1, 1, 0, 1]
Mini dry run (n = 13):
n = 13 → 13 % 2 = 1, n হয় 6 bits = [1]
n = 6 → 6 % 2 = 0, n হয় 3 bits = [1, 0]
n = 3 → 3 % 2 = 1, n হয় 1 bits = [1, 0, 1]
n = 1 → 1 % 2 = 1, n হয় 0 bits = [1, 0, 1, 1]
উল্টালে: 1101 ✓
Python-এ shortcut: bin(13) দেয় '0b1101'। কিন্তু loop টা একবার নিজে লেখো — পরের সব trick এর উপর দাঁড়িয়ে।
2. পাঁচটা primitive — সবকিছুর মূলে mask = 1 << i¶
1 << i মানে: 1 কে i ঘর বাঁয়ে ঠেলা। ফলে এমন একটা সংখ্যা পাও যার শুধু ith bit জ্বলছে। এটাই mask — একটা টর্চলাইট, যেটা শুধু একটা ঘরে আলো ফেলে।
এখন পাঁচটা কাজ (i = ডান থেকে গোনা, 0 থেকে শুরু):
def check_bit(n, i): return (n >> i) & 1 # ith bit জ্বলছে কি?
def set_bit(n, i): return n | (1 << i) # জ্বালাও
def clear_bit(n, i): return n & ~(1 << i) # নেভাও
def toggle_bit(n, i): return n ^ (1 << i) # উল্টাও
def clear_lowest(n): return n & (n - 1) # সবচেয়ে নিচের জ্বলা bit নেভাও
কেন কাজ করে — operator-গুলোর স্বভাব মনে রাখো:
| 1→ জোর করে 1 বানায় (set)& 0→ জোর করে 0 বানায় (clear; তাই~mask— mask উল্টে শুধু target ঘরে 0)^ 1→ উল্টে দেয় (toggle)& 1→ যা আছে তাই দেখায় (check)
Mini dry run (n = 13 = 1101, i = 1):
check: (1101 >> 1) = 110, & 1 = 0 → bit 1 নেভানো ✓
set: 1101 | 0010 = 1111 = 15
clear: 1101 & 1101(~0010 এর শেষ 4 bit) = 1101 → অপরিবর্তিত (আগেই 0 ছিল)
toggle: 1101 ^ 0010 = 1111 = 15
3. n & (n - 1) — এক ঝটকায় lowest set bit মুছে ফেলা¶
এটা bit জগতের সবচেয়ে বিখ্যাত trick। দেখো n - 1 করলে কী হয়:
n = 1 0 1 1 0 0 0 (lowest set bit-টা ★ চিহ্নিত ঘরে)
★
n - 1 = 1 0 1 0 1 1 1 ★ ঘরটা 0 হয়ে গেল, তার ডানের সব 0 হয়ে গেল 1
AND = 1 0 1 0 0 0 0 ★ আর তার ডান — সব মুছে সাফ!
মানে: 1 বিয়োগ করা = সবচেয়ে ডানের 1-টা "ভাঙানো" (যেমন 100 টাকার নোট ভাঙালে খুচরা হয়)। ভাঙা অংশের সাথে AND করলে ওই অংশটুকু শূন্য, বাকি সব অক্ষত।
এর থেকে দুটো জিনিস ফ্রি-তে পাওয়া যায়:
Popcount (set bit গোনা): প্রতিবার একটা করে bit মুছি, যতবার মুছতে পারলাম ততটাই set bit ছিল।
def popcount(n):
count = 0
while n:
n &= n - 1
count += 1
return count
print(popcount(13)) # 3 (1101-এ তিনটা 1)
Dry run: 13 → 12 → 8 → 0, তিন ধাপ → উত্তর 3। (binary-তে: 1101 → 1100 → 1000 → 0000)
Power of two check: 2-এর power মানে binary-তে ঠিক একটা 1। একটা মুছলেই 0 হয়ে যাবে:
n > 0 টা জরুরি — নইলে 0-ও পাশ করে যাবে (common mistake #4 দেখো README-তে)।
4. XOR — যে operator নিজের ছায়া মুছে দেয়¶
XOR (^) টেবিল: আলাদা হলে 1, একই হলে 0।
XOR-এর magic হলো: একই জিনিস দুইবার XOR করলে কেটে যায়। a ^ a = 0, আর a ^ 0 = a। তার উপর order matters না (commutative + associative)। তাই:
জোড়াগুলো নিজে নিজেই বাতিল — যে একলা, সে-ই টিকে থাকে। এটাই Single Number problem:
def odd_one_out(nums):
acc = 0
for x in nums:
acc ^= x
return acc
print(odd_one_out([4, 1, 2, 1, 2])) # 4
Dry run: 0^4=4 → 4^1=5 → 5^2=7 → 7^1=6 → 6^2=4। শেষে 4-ই থাকে — 1 আর 2 জোড়ায় জোড়ায় কেটে গেছে।
দুটো একলা সংখ্যা হলে? সব XOR করলে পাও a ^ b — কিন্তু আলাদা করবে কীভাবে? কৌশল: a ^ b-এর যেকোনো set bit মানে "এই ঘরে a আর b আলাদা"। সেই bit ধরে পুরো array-কে দুই দলে ভাগ করো — a এক দলে, b অন্য দলে, আর প্রতিটা জোড়া একসাথে এক দলেই পড়বে। এবার দুই দলে আলাদা আলাদা XOR চালাও — দুটো উত্তর বেরিয়ে আসবে।
def two_unique(nums):
xor_all = 0
for x in nums:
xor_all ^= x
low = xor_all & (-xor_all) # lowest set bit আলাদা করা (আরেকটা classic trick!)
a = b = 0
for x in nums:
if x & low: a ^= x # দল 1
else: b ^= x # দল 2
return a, b
x & (-x) দিয়ে lowest set bit বের করা — এটাও মনে রাখার মতো (two's complement-এর উপহার)।
5. Subset generation — প্রতিটা সংখ্যাই একটা checklist¶
n টা element-এর প্রতিটার জন্য দুটো option: নেবো / নেবো না। এই হ্যাঁ-না গুলো লিখলে একটা n-bit সংখ্যা হয়! তাই 0 থেকে 2^n - 1 পর্যন্ত প্রতিটা সংখ্যা = একটা আলাদা subset।
arr = [a, b, c] bit 2 = c, bit 1 = b, bit 0 = a
mask binary subset
0 000 {}
1 001 {a}
2 010 {b}
3 011 {a, b}
4 100 {c}
5 101 {a, c}
6 110 {b, c}
7 111 {a, b, c}
def all_subsets(arr):
n = len(arr)
result = []
for mask in range(1 << n): # 0 .. 2^n - 1
subset = [arr[i] for i in range(n) if (mask >> i) & 1]
result.append(subset)
return result
Dry run (mask = 5 = 101): bit 0 জ্বলছে → a নাও; bit 1 নেভানো → b বাদ; bit 2 জ্বলছে → c নাও → {a, c} ✓
Complexity: O(2^n × n) — তাই n ≤ 20-এর আশেপাশে হলেই এই পথ খোলা।
6. Gray code — এক ধাপে এক সুইচ¶
সাধারণ binary counting-এ 3 → 4 মানে 011 → 100 — তিনটা bit একসাথে বদলায়। Gray code এমন একটা সাজানো ক্রম যেখানে পরপর দুটো সংখ্যায় ঠিক 1টা bit বদলায়। Formula অবিশ্বাস্য রকম ছোট:
i : gray
0 : 000
1 : 001 ← শেষ bit বদলালো
2 : 011 ← মাঝের bit বদলালো
3 : 010
4 : 110
5 : 111
6 : 101
7 : 100 ← প্রতি ধাপে ঠিক একটাই বদল!
Intuition: n আর n >> 1 XOR করা মানে "প্রতিটা bit-কে তার বাঁ পাশের bit-এর সাথে তুলনা" — এতে carry-র ঢেউটা একটা single flip-এ নেমে আসে। Rotary encoder, K-map — hardware-এ এর বিশাল ব্যবহার।
7. Range AND = common binary prefix¶
5 AND 6 AND 7 — পরপর অনেক সংখ্যার AND কী দেয়? ছবি দেখো:
পরপর সংখ্যায় নিচের bit গুলো এত ঘনঘন বদলায় যে কোথাও না কোথাও 0 পড়েই। টিকে থাকে শুধু common prefix — l আর r-এর binary-র উপরের যে অংশ মেলে। তাই algorithm: l আর r দুটোকেই ডানে shift করতে থাকো যতক্ষণ না সমান হয়; কয় ঘর সরালে মনে রাখো, শেষে আবার বাঁয়ে ফিরিয়ে দাও।
8. Maximum XOR pair — উপরের bit থেকে greedy (trie teaser)¶
দুটো সংখ্যার XOR বড় করতে চাইলে কোন bit-টা সবচেয়ে দামি? অবশ্যই সবচেয়ে উপরেরটা — কারণ উপরের একটা 1, নিচের সবগুলো 1-এর চেয়েও বড় (1000 > 0111)। তাই greedy: উপরের bit থেকে নেমে এসে প্রতি ধাপে জিজ্ঞেস করো — "এই bit-টা কি উত্তরে 1 হতে পারে?" পারলে রেখে দাও, পরের bit-এ যাও।
Hash set দিয়ে check করার চালাক উপায়: যদি ans-র এই prefix = a_prefix ^ b_prefix সম্ভব হয়, তাহলে কোনো prefix p-এর জন্য p ^ (ans_candidate) ও set-এ থাকবে (কারণ a ^ b = c ⟺ a ^ c = b)।
def max_xor_pair(nums):
ans = 0
for bit in range(31, -1, -1):
mask_top = ans | (1 << bit) # এই bit সহ চাই
prefixes = {x >> bit << bit & ~0 | 0 for x in nums} # ধারণার খাতিরে
prefixes = {x & (~((1 << bit) - 1)) for x in nums} # উপরের অংশটুকু রাখা
if any((p ^ mask_top) in prefixes for p in prefixes):
ans = mask_top # হ্যাঁ! bit টা পাওয়া গেল
return ans
(পরিষ্কার version problem note-এ আসবে।) এই "প্রতি bit-এ branch" চিন্তাটাই binary trie — প্রতিটা সংখ্যা trie-তে ঢোকাও, query-র সময় প্রতি ধাপে উল্টো bit-এর দিকে যেতে চেষ্টা করো। Trie-র formal পরিচয় পরে; এখানে শুধু গন্ধটা নাও।
9. Bitmask DP teaser — পুরো set একটা int-এ¶
ধরো 4টা শহর visit করতে হবে, আর জানতে চাও "কোন কোন শহর ঘোরা হয়ে গেছে"। List রাখতে পারো — কিন্তু {0, 2} ঘোরা হয়েছে মানে তো শুধু 0101 = 5! পুরো visited set একটা ছোট্ট int।
লাভটা কোথায়? DP-র state হিসেবে int ব্যবহার করা যায় — dp[mask][last] মানে "mask-এর শহরগুলো ঘুরে last-এ দাঁড়িয়ে আছি, খরচ কত?" এটাই Traveling Salesman-এর বিখ্যাত O(2^n × n^2) সমাধান। এই level-এ আমরা শুধু দরজাটা খুলব — পুরো ঘর ঘোরা হবে 12-dynamic-programming-এ।
এক নজরে cheat sheet¶
check ith bit : (n >> i) & 1
set ith bit : n | (1 << i)
clear ith bit : n & ~(1 << i)
toggle ith bit : n ^ (1 << i)
lowest set bit মোছা : n & (n - 1)
lowest set bit রাখা : n & (-n)
power of two? : n > 0 and n & (n - 1) == 0
সব subset : for mask in range(1 << n)
gray code : n ^ (n >> 1)
এই টেবিলটা মুখস্থ নয় — প্রতিটা লাইনের পেছনের ছবিটা মনে রাখো। ছবি মনে থাকলে formula নিজেই ফিরে আসে।