Bit Manipulation

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.

1The Operators

2Essential Identities

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,
  ];
}

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.

3Language Differences (Important)

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.

⚠️ 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

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

Six problems on XOR cancellation, bit counting, bit DP, unsigned reversal and addition from logic gates.

1Single Number (LeetCode 136)

🟢 Easy. Every element appears twice except one. Find it in O(n) time and O(1) space.

[4,1,2,1,2] → 4

Approach. XOR all numbers: pairs cancel (x ^ x = 0) and XOR is commutative and associative, so only the single number remains.

Complexity. O(n) time, O(1) space.

function singleNumber(nums: number[]): number {
  return nums.reduce((acc, x) => acc ^ x, 0);
}

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

2Number of 1 Bits (LeetCode 191)

🟢 Easy. Return the number of set bits in the binary representation of a non-negative integer.

11 = 1011₂ → 3

Approach. Repeatedly drop the lowest set bit with n &= n − 1 and count iterations: the loop runs once per set bit, not once per bit position.

Complexity. O(number of set bits) time.

function hammingWeight(n: number): number {
  let count = 0;
  n = n >>> 0;                 // treat as unsigned 32-bit
  while (n) { n = (n & (n - 1)) >>> 0; count++; }
  return count;
}

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

3Counting Bits (LeetCode 338)

🟢 Easy. Return an array ans where ans[i] is the number of 1 bits in i, for 0 ≤ i ≤ n, in O(n).

n = 5 → [0,1,1,2,1,2]

Approach. DP on bits: i >> 1 drops the last bit, which is i & 1, so bits[i] = bits[i >> 1] + (i & 1).

Complexity. O(n) time.

function countBits(n: number): number[] {
  const bits = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);
  return bits;
}

def count_bits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

4Missing Number (LeetCode 268)

🟢 Easy. nums contains n distinct numbers from 0..n. Return the missing one.

[3,0,1] → 2

Approach. XOR every index 0..n with every value: each present number cancels with its index, leaving the missing one. (The sum formula n(n+1)/2 − sum also works; XOR avoids overflow in fixed-width languages.)

Complexity. O(n) time, O(1) space.

function missingNumber(nums: number[]): number {
  let result = nums.length;
  nums.forEach((x, i) => { result ^= i ^ x; });
  return result;
}

def missing_number(nums):
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result

5Reverse Bits (LeetCode 190)

🟢 Easy. Reverse the bits of a 32-bit unsigned integer.

00000010100101000001111010011100 → 00111001011110000010100101000000

Approach. 32 times: shift the result left, append the input's lowest bit, shift the input right. In JavaScript, finish with >>> 0 so the result is read as unsigned; in Python, results stay within 32 bits because you only append 32 bits.

Complexity. O(32) time.

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = ((result << 1) | (n & 1)) >>> 0;
    n >>>= 1;
  }
  return result;
}

def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

6Sum of Two Integers (LeetCode 371)

🟠 Medium. Return a + b without using + or −.

a = 2, b = 3 → 5

Approach. XOR adds without carries; (a & b) << 1 computes the carries. Repeat until there are no carries. In Python, integers are unbounded, so mask to 32 bits on every step and convert back to a signed value at the end; in JS/TS, the | 0 semantics of bitwise ops already work in 32 bits.

Complexity. O(32) iterations.

function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

def get_sum(a, b):
    MASK, MAX = 0xFFFFFFFF, 0x7FFFFFFF
    while b & MASK:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
    a &= MASK
    return a if a <= MAX else ~(a ^ MASK)   # back to signed 32-bit

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: algo_bit_manipulation_theory_1.md, algo_bit_manipulation_theory_2.md · generated by tools/build_lessons.py