Bit Manipulation: Master Low-Level Operations for High-Level Interviews

Why Bit Manipulation Matters in Interviews

Bit manipulation is the art of using bitwise operations to solve problems at the binary level. While it might seem like low-level wizardry, interviewers from FAANG and top tech companies frequently test these skills because they:

Demonstrate deep computer science understanding: You know how computers actually work
Enable space-time trade-offs: Many problems solvable in O(1) space vs O(n) with other approaches
Show optimization mindset: Bitwise ops are often 10-100x faster than arithmetic operations
Test mathematical thinking: Bit patterns reveal elegant mathematical properties

Common interview scenarios where bit manipulation shines:

Finding unique elements (XOR magic)
Subset generation (bitmask enumeration)
Space optimization (bit arrays, bloom filters)
Fast arithmetic (multiplication/division by powers of 2)

Binary Number Fundamentals

Before diving into operations, let’s visualize how numbers are represented in binary:

Decimal to Binary (8-bit representation):

5 in binary:
  Position:  7  6  5  4  3  2  1  0
  Bit:       0  0  0  0  0  1  0  1
  Value:     0  0  0  0  0  4  0  1  = 5

13 in binary:
  Position:  7  6  5  4  3  2  1  0
  Bit:       0  0  0  0  1  1  0  1
  Value:     0  0  0  0  8  4  0  1  = 13

Key insight: Each position represents 2^i

Core Bitwise Operations

1. AND (&): Both bits must be 1

  5:  00000101
& 3:  00000011
  ─────────────
  1:  00000001

Use cases: Check if bit is set, clear bits, extract bits

2. OR (|): At least one bit must be 1

  5:  00000101
| 3:  00000011
  ─────────────
  7:  00000111

Use cases: Set bits, combine flags

3. XOR (^): Bits must be different

  5:  00000101
^ 3:  00000011
  ─────────────
  6:  00000110

Use cases: Toggle bits, find unique elements, swap without temp variable

4. NOT (~): Flip all bits

~5:  11111010 (in 8-bit two's complement)

Use cases: Create masks, invert flags

5. Left Shift (<<): Multiply by 2^n

5 << 1:  00000101 -> 00001010 (5 * 2 = 10)
5 << 2:  00000101 -> 00010100 (5 * 4 = 20)

6. Right Shift (>>): Divide by 2^n

5 >> 1:  00000101 -> 00000010 (5 / 2 = 2)
5 >> 2:  00000101 -> 00000001 (5 / 4 = 1)

Interactive Visualizer: Set and Clear Bits

See how bit operations work step by step:

Setting a Bit with OR

Step 1 of 4

Original number: 5

Number: 5

Clearing a Bit with AND

Step 1 of 4

Original number: 7

Number: 7

Essential Bit Manipulation Patterns

Pattern 1: Individual Bit Operations

Pattern 2: Brian Kernighan’s Algorithm (Count Set Bits)

Key insight: n & (n-1) always removes the lowest set bit!

Example: n = 12 (binary: 1100)

Step 1: 12 & 11
  1100  (12)
& 1011  (11)
  ────
  1000  (8)   <- removed lowest set bit

Step 2: 8 & 7
  1000  (8)
& 0111  (7)
  ────
  0000  (0)   <- removed lowest set bit

Count: 2 set bits

Pattern 3: Power of 2 Check

A number is a power of 2 if and only if it has exactly one bit set.

8:   00001000  -> 8 & 7 = 00001000 & 00000111 = 0 ✓
12:  00001100  -> 12 & 11 = 00001100 & 00001011 = 8 ✗

Formula: n > 0 && (n & (n-1)) == 0

Pattern 4: Get/Isolate Lowest Set Bit

12:  00001100
-12: 11110100  (two's complement)
─────────────
&:   00000100  (isolates bit at position 2)

Formula: n & (-n)

LeetCode Problems: From Basic to Advanced

Problem 1: Single Number (LC 136)

Problem: Given a non-empty array where every element appears twice except one, find that single element.

Key Insight: XOR has magical properties:

a ^ a = 0 (same numbers cancel out)
0 ^ a = a (XOR with 0 is identity)
XOR is commutative and associative

Example: [4, 1, 2, 1, 2]

  4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

Complexity:

Time: $O(n)$ - single pass
Space: $O(1)$ - no extra space (vs $O(n)$ with HashSet)

Problem 2: Counting Bits (LC 338)

Problem: For every number from 0 to n, count the number of 1s in its binary representation.

Key Insight: Use dynamic programming with bit manipulation!

Pattern:
0: 0000 -> 0 bits
1: 0001 -> 1 bit
2: 0010 -> 1 bit  (same as 1, right shift removes 0)
3: 0011 -> 2 bits (same as 1, plus 1)
4: 0100 -> 1 bit  (same as 2, right shift removes 0)
5: 0101 -> 2 bits (same as 2, plus 1)
6: 0110 -> 2 bits (same as 3, right shift removes 0)
7: 0111 -> 3 bits (same as 3, plus 1)

Formula: result[i] = result[i >> 1] + (i & 1)

Complexity:

Time: $O(n)$ - one pass with constant work per iteration
Space: $O(1)$ - excluding output array

Problem 3: Reverse Bits (LC 190)

Problem: Reverse the bits of a 32-bit unsigned integer.

Example:

Input:  00000010100101000001111010011100
Output: 00111001011110000010100101000000

Approach: Process each bit from right to left, building result from left to right.

Complexity:

Time: $O(1)$ - always 32 iterations
Space: $O(1)$

Problem 4: Hamming Distance (LC 461)

Problem: Find the number of positions where bits differ between two integers.

Key Insight: XOR gives us exactly the positions where bits differ!

Example: x = 1 (0001), y = 4 (0100)

  0001  (1)
^ 0100  (4)
  ────
  0101  (5)

Count set bits in 5: 2 positions differ

Complexity:

Time: $O(1)$ - maximum 32 bits
Space: $O(1)$

Problem 5: Subsets using Bitmask (LC 78)

Problem: Generate all possible subsets of a set.

Key Insight: Each subset can be represented by a bitmask!

For n elements, there are $2^n$ subsets
Each number from 0 to $2^n - 1$ represents a unique subset
If bit i is set, include element i

Visual Example: nums = [1, 2, 3]

Mask   Binary   Subset
  0    000      []
  1    001      [1]
  2    010      [2]
  3    011      [1, 2]
  4    100      [3]
  5    101      [1, 3]
  6    110      [2, 3]
  7    111      [1, 2, 3]

Complexity:

Time: $O(n \cdot 2^n)$ - generate $2^n$ subsets, each takes O(n)
Space: $O(1)$ - excluding output

Interview Tips and Common Pitfalls

What Interviewers Expect You to Know

Explain bitwise operations clearly
- Don’t just write code; explain WHY each operation works
- Draw binary representations if needed
Recognize patterns
- XOR for finding unique elements
- n & (n-1) for removing lowest bit
- n & (-n) for isolating lowest bit
- Bitmask for subset enumeration
Discuss trade-offs
- “Bit manipulation gives us O(1) space vs O(n) with HashSet”
- “Works for 32/64-bit integers but may overflow”

Common Mistakes to Avoid

Forgetting operator precedence

// WRONG: & has lower precedence than ==
if (n & 1 == 0)  // Parsed as: n & (1 == 0)

// CORRECT: Use parentheses
if ((n & 1) == 0)

Signed vs unsigned shifts (Java/JavaScript)

-1 >> 1   // -1 (arithmetic shift, sign-extends)
-1 >>> 1  // 2147483647 (logical shift, zero-fills)

Not considering negative numbers
- Two’s complement representation can be tricky
- Test with negative inputs!
Off-by-one errors with bit positions
- Remember: bits are 0-indexed from the right
- Position 0 is the least significant bit

Edge Cases to Test

Zero: n = 0
Powers of 2: n = 1, 2, 4, 8, ...
All bits set: n = -1 (or 0xFFFFFFFF)
Single bit set at different positions
Negative numbers (if applicable)

When NOT to Use Bit Manipulation

While powerful, bit manipulation isn’t always the answer:

Code readability suffers: If your team isn’t comfortable with bit ops, a HashSet solution might be better for maintainability
Problem constraints allow simpler solutions: If n ≤ 1000 and time isn’t critical, a O(n) space solution is fine
Integer overflow concerns: Bit manipulation works within fixed bit-width (32 or 64 bits)
The problem doesn’t naturally map to bits: Don’t force bit manipulation where it doesn’t fit

Complexity Summary

Most bit manipulation operations:

Time: $O(1)$ for single operations, $O(k)$ for k-bit numbers (often k=32, so still O(1))
Space: $O(1)$ - operates on primitive values

Trade-offs:

Pro: Extremely fast, space-efficient, elegant
Con: Less readable, harder to debug, fixed precision

Key Takeaways for Interviews

🎯 Master these patterns:

XOR for finding unique elements (a ^ a = 0)
Brian Kernighan’s algorithm (n & (n-1) removes lowest bit)
Power of 2 check (n > 0 && (n & (n-1)) == 0)
Bitmask for subset enumeration

🎯 Essential operations to memorize:

Set bit: n | (1 << i)
Clear bit: n & ~(1 << i)
Toggle bit: n ^ (1 << i)
Check bit: (n & (1 << i)) != 0

🎯 Always explain:

Why bit manipulation is appropriate for this problem
The mathematical property you’re exploiting
Time/space trade-offs vs alternative approaches

🎯 Practice drawing:

Binary representations during interviews
Helps visualize and communicate your thinking

Remember: Bit manipulation questions test both your understanding of computer fundamentals and your ability to find elegant, optimized solutions. When you master these patterns, you’ll impress interviewers with solutions that are both fast and space-efficient! 🚀