# Bit Manipulation — Data Structures & Algorithms

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

> Core bitwise tricks — checking, setting, and clearing bits — for compact, fast solutions.

## The core operators

`&` (AND) checks bits, `|` (OR) sets bits, `^` (XOR) toggles bits, `~` flips all bits, and `<<`/`>>` shift bits — multiplying/dividing by powers of two. These run in a single CPU cycle, making bit tricks extremely fast.

## Common recipes

Check/set/clear a bit at position `i`, and the classic `n & (n-1)` trick that drops the lowest set bit — handy for counting set bits or checking powers of two.

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

## XOR to find the lone number

XOR is its own inverse: `x ^ x = 0` and `x ^ 0 = x`. XOR-ing every element cancels out pairs, leaving the single unpaired 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
```

## When bits save the day

Use bitmasks to represent **subsets** in DP (e.g. Travelling Salesman), track visited states compactly, or replace a small `set` of booleans with a single integer for speed.