Visualization Ideas — Bit Manipulation¶
Bit-এর জগতে ছবি আঁকতে পারা মানেই অর্ধেক জেতা। সংখ্যাটাকে মাথায় 0/1-এর সারি হিসেবে দেখতে পারলে প্রতিটা trick নিজে থেকেই বোঝা যায়। এখানে প্রতিটা মূল idea-র আঁকার কৌশল, আর শেষে 3টা worked ASCII example।
প্রতি concept-এর visualization idea¶
1. Binary = place value-র টেবিল (8 4 2 1)¶
কাগজে চারটা (বা আটটা) column আঁকো, মাথায় লেখো 8 4 2 1 — প্রতিটা ঘরের "দাম"। এবার যেকোনো সংখ্যা ভাঙো: কোন কোন ঘরের দাম যোগ করলে সংখ্যাটা হয়? সেই ঘরে 1, বাকিতে 0। এটা একদম দোকানের ক্যাশবাক্স — 8 টাকা, 4 টাকা, 2 টাকা, 1 টাকার কয়েন দিয়ে দাম মেলানো, প্রতিটা কয়েন বড়জোর একবার।
প্রতিদিন এলোমেলো 2-3টা সংখ্যা নিয়ে এই টেবিল ভরো — এক সপ্তাহেই binary "পড়তে" পারবে।
2. Mask 1 << i = টর্চলাইট¶
লম্বা একটা অন্ধকার করিডোর আঁকো, প্রতিটা দরজা = একটা bit। 1 << i মানে শুধু i নম্বর দরজায় টর্চের আলো ফেলা — বাকি সব অন্ধকার। আলো ফেলা ঘরের সাথে & করলে দেখা যায় (check), | করলে জ্বলে (set), ^ করলে উল্টায় (toggle)। Animation idea: টর্চ একটা একটা করে ডান থেকে বাঁয়ে সরছে — 1 << 0, 1 << 1, 1 << 2...
3. n & (n - 1) = সবচেয়ে ডানের জ্বলা বাতি নিভে যাওয়ার frame¶
তিন লাইনের একটা "ফিল্ম frame" আঁকো: উপরে n, মাঝে n - 1, নিচে AND। সবচেয়ে ডানের 1-টা ★ দিয়ে চিহ্নিত করো। দেখবে: n - 1-এ ★ ঘরটা নিভে যায় আর তার ডানের সব 0 জ্বলে ওঠে; AND করলে ★ আর তার ডান পুরোটা সাফ, বাঁ দিক অক্ষত। এই তিন-লাইনের frame-টা যতবার আঁকবে, trick-টা ততই শরীরে ঢুকবে।
4. XOR = জোড়া কেটে যাওয়ার ছবি¶
Array-র সংখ্যাগুলো dot হিসেবে আঁকো। একই সংখ্যার দুটো dot পেলে দাগ টেনে কেটে দাও — XOR ঠিক এটাই করে (a ^ a = 0)। সব জোড়া কাটা শেষে যে dot একা দাঁড়িয়ে, সে-ই উত্তর। Order matters না, তাই দূরের দুটো dot-ও নির্দ্বিধায় জোড়া বাঁধতে পারো।
5. Subset mask টেবিল: 000 → 111¶
একটা টেবিল আঁকো: বাঁয়ে mask (0 থেকে 7), মাঝে binary, ডানে subset। প্রতিটা bit = একটা element-এর হ্যাঁ/না সুইচ। টেবিল ভরতে ভরতে নিজেই দেখবে — 8টা সংখ্যা, 8টা subset, একটাও বাদ নেই, একটাও দুবার নেই। এটা একটা চেকলিস্টের ছবি: তিনটা প্রশ্ন (a নেবে? b নেবে? c নেবে?), প্রতিটার উত্তর 0/1।
6. Gray code = আয়নায় গড়া তালিকা¶
Gray code হাতে বানানোর mirror কৌশল: 1-bit তালিকা 0, 1 নাও। আয়নায় উল্টে নিচে বসাও (1, 0), উপরের অর্ধেকের সামনে 0 আর নিচের অর্ধেকের সামনে 1 লাগাও — পেয়ে গেলে 2-bit gray code। আবার আয়না, আবার prefix — 3-bit। আয়নার সীমানায় শুধু সামনের bit-টা বদলায়, ভেতরে তো mirror copy — তাই প্রতি ধাপে ঠিক 1 bit বদলায় property নিজে থেকেই চলে আসে।
Worked ASCII example 1: clear ith bit (n = 13, i = 2)¶
লক্ষ্য: 13 = 1101-এর bit 2 (দাম 4-এর ঘর) নেভানো
mask = 1 << 2 = 0 1 0 0
~mask = 1 0 1 1 ← mask উল্টালে: target ঘরে 0, বাকি সব 1
n = 1 1 0 1
n & ~mask = 1 0 0 1 = 9
^
শুধু এই ঘরটা জোর করে 0 হলো, বাকিরা & 1 → অক্ষত
& 0 মানে জোর করে নেভানো, & 1 মানে যা আছে তাই — এই দুই স্বভাব মিলেই clear operation।
Worked ASCII example 2: popcount-এর film strip (n = 13)¶
n = 13 = 1 1 0 1 count = 0
frame 1: n = 1 1 0 1 ★ ডানের 1
n-1 = 1 1 0 0
AND = 1 1 0 0 = 12 count = 1
frame 2: n = 1 1 0 0 ★ এবার দাম-4 ঘরের 1
n-1 = 1 0 1 1
AND = 1 0 0 0 = 8 count = 2
frame 3: n = 1 0 0 0
n-1 = 0 1 1 1
AND = 0 0 0 0 = 0 count = 3 → loop শেষ
তিনবার নেভাতে পারলাম → 13-তে 3টা set bit। লক্ষ করো প্রতি frame-এ ঠিক একটা বাতি নেভে — কখনো দুটো না, কখনো শূন্যটা না।
Worked ASCII example 3: subset enumeration (arr = [a, b, c])¶
bit 2 = c, bit 1 = b, bit 0 = a
mask | binary | কে কে আছে | subset
0 | 000 | - - - | {}
1 | 001 | - - a | {a}
2 | 010 | - b - | {b}
3 | 011 | - b a | {a, b}
4 | 100 | c - - | {c}
5 | 101 | c - a | {a, c}
6 | 110 | c b - | {b, c}
7 | 111 | c b a | {a, b, c}
7 পর্যন্ত গুনলেই 2^3 = 8টা subset শেষ — counting আর set generation একই জিনিস হয়ে গেল। mask = 5 ধরে নিজে check করো: (5 >> 0) & 1 = 1 → a আছে; (5 >> 1) & 1 = 0 → b নেই; (5 >> 2) & 1 = 1 → c আছে ✓
নিজে practice করার নিয়ম¶
- নতুন কোনো bit trick দেখলেই আগে ছোট সংখ্যায় (n ≤ 16) binary লিখে হাতে চালাও — 4-bit-এ যা সত্য, 32-bit-এও তাই
n & (n - 1)-এর তিন-লাইন frame-টা সপ্তাহে দু-একবার নতুন সংখ্যায় আঁকো- Subset টেবিলটা
[x, y](2 element) দিয়ে আরেকবার বানাও — 4 row-র ছোট টেবিল, কিন্তু idea একই - Gray code-এর mirror build নিজ হাতে 3-bit পর্যন্ত করো, তারপর
n ^ (n >> 1)দিয়ে মিলিয়ে দেখো — দুটো পথ একই তালিকায় পৌঁছায়