# Bit Manipulation — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/bit-manipulation

> मुख्य bitwise तरकीबें — bits की जांच, सेट और साफ़ करना — compact, तेज़ समाधान के लिए।

## मुख्य operators

`&` (AND) bits जांचता है, `|` (OR) bits सेट करता है, `^` (XOR) bits toggle करता है, `~` सभी bits पलटता है, और `<<`/`>>` bits shift करते हैं — 2 की घातों से गुणा/भाग। ये एक ही CPU cycle में चलते हैं, इसलिए bit trick बेहद तेज़ होते हैं।

## आम recipes

Position `i` पर एक bit check/set/clear करें, और classic `n & (n-1)` trick जो सबसे कम set bit हटा देता है — set bits गिनने या 2 की घात जांचने में उपयोगी।

```python
def get_bit(n, i):
    return (n >> i) & 1

def set_bit(n, i):
    return n | (1 << i)

def clear_bit(n, i):
    return n & ~(1 << i)

def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)   # drops the lowest set bit
        count += 1
    return count

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
```

Output:

```
count_set_bits(11)      # 11 = 0b1011 -> 3
is_power_of_two(16)     # True
```

## अकेला number खोजने के लिए XOR

XOR खुद का उलटा है: `x ^ x = 0` और `x ^ 0 = x`। हर element को XOR करने से जोड़े कट जाते हैं, केवल अकेला value बचता है।

```python
def single_number(nums):
    result = 0
    for x in nums:
        result ^= x
    return result
```

Output:

```
single_number([4, 1, 2, 1, 2])  # 4
```

## जब bits काम आते हैं

DP में **subsets** दिखाने के लिए bitmasks इस्तेमाल करें (जैसे Travelling Salesman), visited states को compact रखें, या booleans के छोटे `set` को गति के लिए एक integer से बदलें।