# Level 4 — Bit Manipulation (সংখ্যার ভেতরের সুইচবোর্ড)

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> প্রতিটা integer আসলে 0 আর 1-এর একটা সারি — অনেকগুলো সুইচ পাশাপাশি লাগানো একটা switchboard। এই level-এ আমরা শিখব সেই সুইচগুলো একটা একটা করে দেখতে, জ্বালাতে, নেভাতে আর উল্টাতে। আর শিখব XOR-এর সেই magic, যেটা দিয়ে এক লাইনে এমন problem solve হয় যেগুলো loop দিয়ে করতে গেলে মাথা ঘুরে যায়।

## এই level এ কী শিখবে?

Decimal-এ আমরা 10-এর ঘর গুনি (একক, দশক, শতক)। Binary-তে গুনি 2-এর ঘর: `8 4 2 1`। এই চোখটা একবার তৈরি হলে `13 = 1101` দেখে আর ভয় লাগে না — বরং মনে হয় "ও, 8 + 4 + 1"।

মূল idea গুলো:

- **Binary representation** — সংখ্যাকে bit-এর সারি হিসেবে দেখা, place value-র টেবিল
- **5টা primitive operation** — ith bit কে check / set / clear / toggle করা, সবকিছুর মূলে `mask = 1 << i`
- **`n & (n - 1)` trick** — সবচেয়ে নিচের set bit এক ঝটকায় মুছে ফেলা → popcount, power of two check
- **XOR-এর ধর্ম** — self-inverse (`a ^ a = 0`), order matters না → জোড়ার ভিড়ে একলা সংখ্যা খুঁজে বের করা
- **Subset generation** — 0 থেকে 2^n - 1 পর্যন্ত প্রতিটা সংখ্যা = একটা subset-এর ছবি
- **Gray code, range AND, maximum XOR** — bit-চিন্তার আরো গভীর প্রয়োগ
- **Bitmask DP teaser** — একটা পুরো visited set কে একটা int-এ ভরে ফেলা

## কেন এই level দরকার?

**Competitive programming (CP) এ:** Codeforces-এ XOR-based problem একটা আলাদা genre — প্রায় প্রতি contest-এই কিছু না কিছু থাকে। Subset enumeration আর bitmask DP ছাড়া অনেক constructive আর DP problem-এ হাতই দেওয়া যায় না। `n ≤ 20` দেখলেই অভিজ্ঞ contestant-এর মাথায় বাজে: "bitmask!"

**Interview এ:** Single Number, Number of 1 Bits, Power of Two — এগুলো common interview pattern; warm-up হিসেবে প্রায়ই আসে। আর Subsets problem-টা bitmask দিয়ে solve করতে পারলে interviewer বোঝে তুমি binary-তে স্বচ্ছন্দ।

**পরের ধাপে:** Trie দিয়ে maximum XOR (এই level-এর শেষ problem-এ teaser আছে), segment tree-র index গণিত, hashing-এর bit mixing — সবখানে bit-এর হাত আছে।

## Prerequisites

- [Level 0: Absolute Basics](../00-absolute-basics/README.md) — `%` আর `//` দিয়ে digit ভাঙা (binary-তে একই কাজ base 2-তে হয়)
- Python-এর `&`, `|`, `^`, `~`, `<<`, `>>` operator-গুলোর নাম শোনা থাকলে ভালো — না জানলেও সমস্যা নেই, এখানেই শিখবে
- Level 3-এর combinatorics ঘুরে আসা থাকলে subset counting (2^n) আরো natural লাগবে

## Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

- [ ] যেকোনো ছোট সংখ্যার binary form মাথায় বের করতে পারি (place value টেবিল দিয়ে)
- [ ] `mask = 1 << i` বানিয়ে ith bit check / set / clear / toggle — চারটাই না দেখে লিখতে পারি
- [ ] `n & (n - 1)` কেন lowest set bit মোছে — ছবি এঁকে ব্যাখ্যা করতে পারি
- [ ] Power of two check এক লাইনে লিখতে পারি, আর `n = 0` edge case-টা মনে আছে
- [ ] XOR-এর self-inverse ধর্ম দিয়ে Single Number ব্যাখ্যা করতে পারি
- [ ] দুটো unique number-এর ক্ষেত্রে "lowest set bit দিয়ে দুই দলে ভাগ" idea-টা বুঝি
- [ ] 0 থেকে 2^n - 1 loop চালিয়ে সব subset generate করতে পারি
- [ ] Gray code-এর `n ^ (n >> 1)` formula জানি আর "পরপর সংখ্যায় 1 bit বদলায়" property-টা verify করতে পারি
- [ ] Range AND = common binary prefix — এই intuition টা ধরতে পারি
- [ ] Bitmask DP-তে state মানে কী — অন্তত ধারণা আছে (পুরো মাস্টারি পরে আসবে)

## Problem list

মোট 14টা problem — 8টা Easy, 4টা Medium, 2টা Hard।

### Easy

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 053 | [Binary Representation](problems/053-binary-representation.md) | base conversion | Classic exercise |
| 054 | [Check ith Bit](problems/054-check-ith-bit.md) | mask & | Classic exercise |
| 055 | [Set ith Bit](problems/055-set-ith-bit.md) | mask \| (OR) | Classic exercise |
| 056 | [Clear ith Bit](problems/056-clear-ith-bit.md) | mask & ~ | Classic exercise |
| 057 | [Toggle ith Bit](problems/057-toggle-ith-bit.md) | mask ^ | Classic exercise |
| 058 | [Count Set Bits](problems/058-count-set-bits.md) | n&(n-1) loop | LeetCode Number of 1 Bits — <https://leetcode.com/problems/number-of-1-bits/> (related: Counting Bits — <https://leetcode.com/problems/counting-bits/>) |
| 059 | [Power of Two](problems/059-power-of-two.md) | n&(n-1)==0 | LeetCode — <https://leetcode.com/problems/power-of-two/> |
| 060 | [Odd One Out using XOR](problems/060-odd-one-out-xor.md) | XOR cancel | LeetCode Single Number — <https://leetcode.com/problems/single-number/> |

### Medium

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 061 | [Find Two Unique Numbers](problems/061-find-two-unique-numbers.md) | XOR partition | LeetCode Single Number III — <https://leetcode.com/problems/single-number-iii/> |
| 062 | [Subset Generation using Bits](problems/062-subset-generation-bits.md) | bitmask enumeration | LeetCode Subsets — <https://leetcode.com/problems/subsets/> |
| 064 | [Gray Code](problems/064-gray-code.md) | n^(n>>1) | LeetCode — <https://leetcode.com/problems/gray-code/> |
| 065 | [AND/OR/XOR Range Tricks](problems/065-and-or-xor-range-tricks.md) | common prefix | LeetCode Bitwise AND of Numbers Range — <https://leetcode.com/problems/bitwise-and-of-numbers-range/> |

### Hard

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 063 | [Bitmask DP Intro](problems/063-bitmask-dp-intro.md) | state as mask | USACO Guide — <https://usaco.guide/gold/dp-bitmasks> |
| 066 | [Maximum XOR Pair](problems/066-maximum-xor-pair.md) | greedy by bit / trie | LeetCode — <https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/> |

পুরো tracker table (status সহ) আছে [problems/README.md](problems/README.md)-তে।

## Recommended order

1. **053** — আগে binary পড়তে শেখো; এটাই বর্ণমালা
2. **054 → 055 → 056 → 057** — 5টা primitive পরপর; প্রতিটা আগেরটার এক ধাপ পরের ভাই
3. **058 → 059** — `n & (n - 1)` trick দুই রূপে: গোনা আর চেনা
4. **060 → 061** — XOR-এর গল্প: আগে একলা একজন, তারপর একলা দুজন
5. **062** — subset generation; এখানে এসে bit আর set মিলে যায়
6. **064 → 065** — bit pattern-এর সৌন্দর্য: gray code আর common prefix
7. **066** — greedy by bit; trie-র দরজায় টোকা
8. **063** — সবশেষে bitmask DP intro; এটা সবচেয়ে কঠিন, তাড়াহুড়ো নেই

## Common mistakes (সাধারণ ভুল)

1. **`&` আর `and` গুলিয়ে ফেলা** — Python-এ `and` হলো logical, `&` হলো bitwise। `5 and 3` দেয় `3`, কিন্তু `5 & 3` দেয় `1`। Bit-এর কাজে সবসময় `&`, `|`, `^`।
2. **Operator precedence ফাঁদ** — `n & 1 == 0` মানে আসলে `n & (1 == 0)`! Python-এ `==` আগে চলে। সবসময় bracket দাও: `(n & 1) == 0`।
3. **`1 << i` ভুলে `i << 1` লেখা** — `1 << 3 = 8` (mask), কিন্তু `3 << 1 = 6` (double)। Mask মানে "1 কে i ঘর বাঁয়ে ঠেলা"।
4. **`n & (n - 1)`-এ `n = 0` ভুলে যাওয়া** — `0 & -1 = 0`, তাই power of two check-এ `n > 0` শর্ত না দিলে 0-ও "power of two" হয়ে যাবে!
5. **Python-এর `~`-তে অবাক হওয়া** — Python-এ int unbounded, তাই `~5 = -6` (two's complement-এর ধারণায়)। Clear bit করতে `n & ~(1 << i)` ঠিকই কাজ করে, কিন্তু `bin(~5)` print করে ঘাবড়ে যেও না।
6. **Subset loop-এ range ভুল** — `range(1 << n)` দরকার, `range(n)` না। 3টা element মানে 8টা subset, 3টা না!
7. **XOR দিয়ে সব duplicate problem solve করতে চাওয়া** — XOR cancel তখনই কাজ করে যখন duplicate গুলো **জোড়ায়** আসে। তিনবার করে এলে অন্য কৌশল লাগে (bit count mod 3)।
8. **Shift-এ negative বা বিশাল amount** — `1 << -1` Python-এ ValueError। আর `1 << 10**6` Python-এ চলে গেলেও memory খাবে; C++-এ undefined behavior।

## পরের level এ যাওয়ার আগে checklist

- [ ] 5টা primitive (check / set / clear / toggle / lowest-bit-clear) কাগজে না দেখে লিখেছি
- [ ] `n & (n - 1)` দিয়ে popcount-এর dry run করেছি অন্তত একটা সংখ্যায় (যেমন 13)
- [ ] Single Number-এর XOR solution কাউকে (বা নিজেকে জোরে জোরে) বুঝিয়ে বলেছি
- [ ] 062 দিয়ে `[1, 2, 3]`-এর 8টা subset হাতে লিখে mask-এর সাথে মিলিয়েছি
- [ ] 0 থেকে 7 পর্যন্ত gray code টেবিল নিজে বানিয়ে "1 bit বদলায়" property চোখে দেখেছি
- [ ] Bitmask DP-র "state = কোন কোন জিনিস নেওয়া হয়েছে" idea-টা অন্তত একবার পড়ে বুঝেছি — পুরো solve না হলেও ঠিক আছে

সব টিক দিতে পারলে — চলো [Level 5: Prefix, Difference, Contribution](../05-prefix-difference-contribution/README.md)-এ। সেখানে bit ছেড়ে আবার যোগফলের জগতে — কিন্তু এবার "আগে থেকে হিসেব করে রাখা"-র জাদু নিয়ে।

## Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে [source-map.md](source-map.md)-তে।