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

প্রতিটা 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 — % আর // দিয়ে 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	base conversion	Classic exercise
054	Check ith Bit	mask &	Classic exercise
055	Set ith Bit	mask \| (OR)	Classic exercise
056	Clear ith Bit	mask & ~	Classic exercise
057	Toggle ith Bit	mask ^	Classic exercise
058	Count Set Bits	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	n&(n-1)==0	LeetCode — https://leetcode.com/problems/power-of-two/
060	Odd One Out using XOR	XOR cancel	LeetCode Single Number — https://leetcode.com/problems/single-number/

Medium¶

#	Problem	Pattern	Source
061	Find Two Unique Numbers	XOR partition	LeetCode Single Number III — https://leetcode.com/problems/single-number-iii/
062	Subset Generation using Bits	bitmask enumeration	LeetCode Subsets — https://leetcode.com/problems/subsets/
064	Gray Code	n^(n>>1)	LeetCode — https://leetcode.com/problems/gray-code/
065	AND/OR/XOR Range Tricks	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	state as mask	USACO Guide — https://usaco.guide/gold/dp-bitmasks
066	Maximum XOR Pair	greedy by bit / trie	LeetCode — https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/

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

Recommended order¶

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

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

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

Source map¶

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