Bit Manipulation — Complete Interview Guide for FAANG Engineers

Why Bit Manipulation?#

Bitwise operations work directly on binary representations, enabling O(1) tricks that would otherwise need loops or extra space. Bit manipulation problems appear at Google, Amazon, Meta, and Microsoft — interviewers use them to test depth of systems thinking and ability to reason at the bit level.

Essential Bit Operations#

The 7 Core Patterns#

Pattern 1 — XOR for Duplicate Cancellation#

XOR of a number with itself = 0. XOR with 0 = identity. Use to find single or missing numbers.

result = 0
for n in nums:
    result ^= n  # all duplicates cancel; single element survives

Pattern 2 — Brian Kernighan (Count Set Bits)#

n & (n-1) removes the lowest set bit. Count iterations until n reaches 0.

count = 0
while n:
    n &= n - 1   # drop the lowest set bit
    count += 1

Pattern 3 — Bitmask DP (Subsets as State)#

State = bitmask of items selected. Iterate over all 2^n masks.

for mask in range(1 << n):
    for i in range(n):
        if mask & (1 << i):
            pass  # item i is in this subset

Pattern 4 — Bitmask Enumeration (Subsets of a Mask)#

Enumerate all subsets of a bitmask in O(2^popcount) using sub = (sub-1) & mask.

sub = mask
while sub:
    process(sub)
    sub = (sub - 1) & mask

Pattern 5 — Two's Complement Tricks#

Negative numbers in two's complement: -n = ~n + 1. n & (-n) isolates the rightmost set bit. Used in BIT (Fenwick Tree) traversal.

Pattern 6 — Bit by Bit Construction#

Build answer bit by bit from MSB to LSB. Common with XOR prefix sums in a trie.

prefix_xor = 0
for n in nums:
    prefix_xor ^= n
    # query trie for max XOR with prefix_xor

Pattern 7 — Bit Reversal / Rotation#

Reverse bits of a 32-bit integer by extracting and shifting one bit at a time.

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

Language-Specific Bit Operations#

Python#

n & m   # AND
n | m   # OR
n ^ m   # XOR
~n      # NOT (bitwise complement)
n << k  # left shift
n >> k  # right shift (arithmetic)
bin(n).count('1')  # popcount

C/C++#

n & m; n | m; n ^ m; ~n; n << k; n >> k;
__builtin_popcount(n);    /* GCC popcount */
__builtin_clz(n);         /* count leading zeros */
__builtin_ctz(n);         /* count trailing zeros */

Java#

n & m; n | m; n ^ m; ~n; n << k; n >> k; n >>> k; // unsigned right shift
Integer.bitCount(n);
Integer.highestOneBit(n);
Integer.numberOfLeadingZeros(n);

JavaScript#

n & m; n | m; n ^ m; ~n; n << k; n >> k; n >>> k;
n.toString(2).split('').filter(x => x === '1').length; // popcount

Complexity Summary#

Common Pitfalls#

1. Overflow with 1 << 31 in C++/Java. Use 1u << 31 (unsigned) or 1L << 31 (long) to avoid signed integer overflow.
2. Python ~n is not 2^32 - 1 - n. Python integers are arbitrary precision; ~n = -(n+1) always.
3. n & (n-1) on n=0 yields 0, not undefined. But calling it in a loop without a guard causes an infinite loop.
4. Forgetting bitmask DP needs 4*n time and 2^n space. Feasible only for n <= 20.
5. Arithmetic vs logical right shift. Python >> is arithmetic (preserves sign). JavaScript >>> is logical (zero-fills).

Problem Index#

Key Takeaways#

• Two XOR identities drive most bit tricks: a ^ a = 0 (cancellation) and a ^ 0 = a (identity).
• n & (n-1) removes the lowest set bit — Brian Kernighan's algorithm counts set bits in O(popcount) iterations.
• n & (-n) isolates the lowest set bit — foundational for Fenwick Trees and bitmask subset enumeration.
• Bitmask DP is feasible for n up to 20; it encodes which items are selected as a single integer state.
• ceil(log2(k)) bitmasks are needed to cancel elements appearing k times — XOR (k=2) uses 1, mod-3 (k=3) uses 2.
• Language-specific overflow rules differ: Python has arbitrary-precision integers; C++/Java need explicit casts for bit 31.
• Bit manipulation often converts O(n) space solutions to O(1) — the space constraint in a problem is your signal to think bitwise.