# Bit-কে বাক্স ধরে দেখা

## 13-এর চারটি bit

```dsa
kind: array
title: "13 = 8 + 4 + 1"
steps:
  - label: "বাঁ থেকে bit 3, 2, 1, 0"
    values: [1, 1, 0, 1]
    indices: false
    active: [0, 1, 3]
    note: "ওজন যথাক্রমে 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 সরায়

```mermaid
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: {A,B}

| 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

```mermaid
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:

```mermaid
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 বদলাত।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)