# Bit Manipulation — Part 1: The Pattern

Bit manipulation treats integers as arrays of bits and works on all of them at once with single CPU instructions. In interviews it appears in three ways: **XOR tricks** (find the unique element, swap without a temp), **bit counting and masks** (popcount, powers of two, flags), and **bitmasks as sets** (all subsets of n ≤ 20 items, DP over subsets). The operators are few; knowing what each identity does is the whole topic.

![22 in binary with the effect of common bit operations](diagrams/01-bits.svg)

## 1. The Operators

| Op | Meaning | Use |
|---|---|---|
| `a & b` | AND | test/clear bits (masks) |
| `a \| b` | OR | set bits |
| `a ^ b` | XOR | toggle; `x ^ x = 0`, `x ^ 0 = x` |
| `~a` | NOT | invert (in two's complement `~a = −a − 1`) |
| `a << k` | shift left | multiply by 2ᵏ, build masks `1 << k` |
| `a >> k` | shift right | divide by 2ᵏ (arithmetic: keeps the sign) |
| `a >>> k` | unsigned shift (JS/TS, Java) | treat as unsigned 32-bit |

## 2. Essential Identities

```typescript
function bitDemo(n: number): number[] {
  let c = 0, x = n;
  while (x) { x &= x - 1; c++; }   // popcount by dropping lowest bits
  return [
    n & 1,
    (n >> 2) & 1,
    n | (1 << 3),
    n & ~(1 << 0),
    n ^ (1 << 1),
    n & (n - 1),
    n & -n,
    c,
  ];
}
```

```python
def bit_demo(n):
    return [
        n & 1,                 # lowest bit: odd?
        (n >> 2) & 1,          # bit 2
        n | (1 << 3),          # set bit 3
        n & ~(1 << 0),         # clear bit 0
        n ^ (1 << 1),          # toggle bit 1
        n & (n - 1),           # drop the lowest set bit
        n & -n,                # isolate the lowest set bit
        bin(n).count("1"),     # popcount
    ]
```

- `n & (n − 1)` **drops the lowest set bit**: counting bits in O(set bits), and `n > 0 and n & (n − 1) == 0` tests **power of two**.
- `n & −n` **isolates the lowest set bit** (used in Fenwick trees).
- XOR of a value with itself cancels: XOR everything to find the element that appears once.
- `(mask >> i) & 1` reads bit i; iterate `mask` from 0 to `2ⁿ − 1` to enumerate all subsets.

## 3. Language Differences (Important)

| | Python | JavaScript / TypeScript | C# |
|---|---|---|---|
| integer size | **unbounded** (no overflow) | numbers are doubles; bitwise ops convert to **32-bit signed** | `int` 32-bit, `long` 64-bit |
| negative numbers | infinite leading 1s; mask with `& 0xFFFFFFFF` to emulate 32-bit | `x >>> 0` converts to unsigned 32-bit | `uint`/`ulong` for unsigned |
| popcount | `bin(n).count("1")`, `n.bit_count()` (3.10+) | loop or manual | `BitOperations.PopCount` |

This matters for problems like Reverse Bits and Sum of Two Integers: a JS solution must finish with `>>> 0` to return an unsigned value, and Python needs an explicit 32-bit mask.

## Under the Hood: Two's Complement

Negative integers are stored as **two's complement**: `−x = ~x + 1`. That's why `n & −n` isolates the lowest set bit: `−n` flips every bit above the lowest 1 and keeps that 1. CPUs implement AND/OR/XOR/shift in one cycle and have dedicated instructions for popcount (`POPCNT`) and leading/trailing zero counts; databases use bitmaps for fast filtering (bitmap indexes, Roaring bitmaps), and Bloom filters and permission flags are bitsets.

## Common Pitfalls

1. **Operator precedence:** `n & 1 == 0` parses as `n & (1 == 0)` in many languages. Use parentheses.
2. **JS 32-bit conversion:** `2 ** 32 | 0` is 0; use `>>> 0` for unsigned results.
3. **Python negatives:** `-1 >> 1` is still −1 and loops never end without a mask.
4. **Shifting by ≥ width** is undefined or wraps (C#/Java mask the shift count to 5 or 6 bits).
5. **Using bitmasks for n > ~25:** 2ⁿ subsets explode.

## Quick Reference

```text
test bit i: (n >> i) & 1 · set: n | (1<<i) · clear: n & ~(1<<i) · toggle: n ^ (1<<i)
drop lowest 1: n & (n-1) · lowest 1: n & -n · power of 2: n > 0 && (n & (n-1)) == 0
XOR: a^a = 0, a^0 = a (find the unique element)
JS unsigned: x >>> 0 · Python 32-bit: x & 0xFFFFFFFF
```