# Concept Notes — Bit Manipulation (ভেতর থেকে বোঝা)

## সহজ করে শুরু: একটি সংখ্যার মধ্যে ছোট ছোট পতাকা

একটি bit হলো 0 বা 1। ডান থেকে শূন্য-ভিত্তিক অবস্থান `i` পরীক্ষা করতে `(n >> i) & 1`। কয়েকটি সদস্যের উপস্থিতি এভাবেই একটি integer-এর মধ্যে রাখা যায়; এই প্রতিনিধিত্বকে bitmask বলে।

**প্রোগ্রামে কোথায় ব্যবহার করবে:** অল্পসংখ্যক permission বা feature flag রাখা, subset enumerate করা এবং ছোট state-ভিত্তিক DP-তে bitmask লাগে। XOR জোড়া সমান মান বাতিল করে অনন্য মান খুঁজতে পারে।

**কৌশল বাছার আগে শর্ত:** Python-এ `~x` শুধু আঁকা চারটি bit উল্টায় না; চার bit-এর ফল চাইলে `(~x) & 15` লিখবে। `n & (n-1) == 0` দিয়ে power of two বলার আগে `n > 0` নিশ্চিত করো।

পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও।

> এই 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`।

```text
place:   8   4   2   1
13    =  1   1   0   1   →  8 + 4 + 0 + 1 = 13
```

তাহলে "13-এর binary কী?" প্রশ্নটা আসলে: "8, 4, 2, 1 — কোনগুলো যোগ করলে 13 হয়?"

Code-এ বের করার নিয়ম Level 0-এর digit extraction-এরই যমজ ভাই — শুধু 10-এর জায়গায় 2:

```python
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`):

```text
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 — একটা টর্চলাইট, যেটা শুধু একটা ঘরে আলো ফেলে।

```text
1 << 0 = 0001    1 << 1 = 0010    1 << 2 = 0100    1 << 3 = 1000
```

এখন পাঁচটা কাজ (i = ডান থেকে গোনা, 0 থেকে শুরু):

```python
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`):

```text
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` করলে কী হয়:

```text
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 ছিল।

```python
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 হয়ে যাবে:

```python
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
```

`n > 0` টা জরুরি — নইলে 0-ও পাশ করে যাবে (common mistake #4 দেখো README-তে)।

## 4. XOR — যে operator নিজের ছায়া মুছে দেয়

XOR (`^`) টেবিল: আলাদা হলে 1, একই হলে 0।

```text
0 ^ 0 = 0    1 ^ 1 = 0    ← একই → কেটে যায়
0 ^ 1 = 1    1 ^ 0 = 1    ← আলাদা → টিকে থাকে
```

XOR-এর magic হলো: একই জিনিস দুইবার XOR করলে কেটে যায়। `a ^ a = 0`, আর `a ^ 0 = a`। তার উপর order matters না (commutative + associative)। তাই:

```text
3 ^ 5 ^ 3 = (3 ^ 3) ^ 5 = 0 ^ 5 = 5
```

জোড়াগুলো নিজে নিজেই বাতিল — যে একলা, সে-ই টিকে থাকে। এটাই **Single Number** problem:

```python
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 চালাও — দুটো উত্তর বেরিয়ে আসবে।

```python
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।

```text
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}
```

```python
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 অবিশ্বাস্য রকম ছোট:

```python
def gray(n):
    return n ^ (n >> 1)

for i in range(8):
    print(i, format(gray(i), '03b'))
```

```text
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 কী দেয়? ছবি দেখো:

```text
5 = 1 0 1
6 = 1 1 0
7 = 1 1 1
AND 1 0 0   ← শুধু সেই bit টিকে থাকে যেটা সবার মধ্যে জ্বলা
```

পরপর সংখ্যায় নিচের bit গুলো এত ঘনঘন বদলায় যে কোথাও না কোথাও 0 পড়েই। টিকে থাকে শুধু **common prefix** — l আর r-এর binary-র উপরের যে অংশ মেলে। তাই algorithm: l আর r দুটোকেই ডানে shift করতে থাকো যতক্ষণ না সমান হয়; কয় ঘর সরালে মনে রাখো, শেষে আবার বাঁয়ে ফিরিয়ে দাও।

```python
def range_and(l, r):
    shift = 0
    while l < r:
        l >>= 1; r >>= 1
        shift += 1
    return l << 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`)।

```python
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।

```python
visited = 0
visited |= (1 << 2)        # শহর 2 ঘোরা হলো
if visited & (1 << 0):     # শহর 0 কি ঘোরা?
    ...
```

লাভটা কোথায়? **DP-র state হিসেবে int ব্যবহার করা যায়** — `dp[mask][last]` মানে "mask-এর শহরগুলো ঘুরে last-এ দাঁড়িয়ে আছি, খরচ কত?" এটাই Traveling Salesman-এর বিখ্যাত O(2^n × n^2) সমাধান। এই level-এ আমরা শুধু দরজাটা খুলব — পুরো ঘর ঘোরা হবে [12-dynamic-programming](../../12-dynamic-programming/README.md)-এ।

## এক নজরে cheat sheet

```text
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 নিজেই ফিরে আসে।