Bit-কে বাক্স ধরে দেখা¶
13-এর চারটি bit¶
বাঁ থেকে bit 3, 2, 1, 0
চিহ্নিত ঘর: 1চিহ্নিত ঘর: 10চিহ্নিত ঘর: 1ওজন যথাক্রমে 8, 4, 2, 1। জ্বলা তিনটি bit-এর ওজন যোগ করি; 2 নিই না।
অর্থ: 8+4+1=13। i=1-এর mask 0010।
| কাজ | হিসাব | ফল |
|---|---|---|
| check bit 1 | 1101 & 0010 |
0000: bit বন্ধ |
| set bit 1 | 1101 \| 0010 |
1111 = 15 |
| clear bit 2 | 1101 & 1011 |
1001 = 9 |
| toggle bit 0 | 1101 ^ 0001 |
1100 = 12 |
টেবিলের clear-mask চার bit-এ দেখানো হয়েছে। Python-এ আসল expression n & ~(1 << 2)।
n & (n-1) কেন একটি bit সরায়¶
flowchart LR
A["13: 1101"] -->|"AND 12: 1100"| B["12: 1100"]
B -->|"AND 11: 1011"| C["8: 1000"]
C -->|"AND 7: 0111"| D["0: 0000"]তিন ধাপে 0; তাই 13-তে তিনটি set bit।
Mask থেকে subset:¶
| mask | bit 1 = B | bit 0 = A | subset |
|---|---|---|---|
| 00 | নেই | নেই | খালি |
| 01 | নেই | আছে | {A} |
| 10 | আছে | নেই | {B} |
| 11 | আছে | আছে | {A,B} |
সদস্যসংখ্যা n হলে mask আছে 2^nটি। তাই n=40 হলে সরাসরি সব mask চালানো সাধারণত ছোট কাজ নয়।
XOR-এ জোড়া বাতিল ও Gray code¶
flowchart LR
A["4 XOR 1 XOR 4 XOR 2 XOR 2"] --> B["(4 XOR 4) XOR (2 XOR 2) XOR 1"]
B --> C["0 XOR 0 XOR 1 = 1"]এই সমস্যার শর্ত: একটি মান একবার, বাকিগুলো দুবার আসে। সেই শর্ত ছাড়া XOR-এর ফলকে অনন্য মান বলা যাবে না।
দুই bit-এর সম্পূর্ণ Gray cycle:
flowchart LR
A["00"] -->|"bit 0 বদলায়"| B["01"]
B -->|"bit 1 বদলায়"| C["11"]
C -->|"bit 0 বদলায়"| D["10"]
D -->|"bit 1 বদলায়"| Aপাশাপাশি প্রতিটি জোড়ায় একটিমাত্র bit বদলেছে। সাধারণ binary order-এ 01→10 গেলে দুটি bit বদলাত।