PATTERN 22 OF 22

Bit Manipulation

Use bitwise operators (AND, OR, XOR, shifts) to solve problems involving single-number detection, duplicate/missing finding, bit counting, and arithmetic without operators — all in O(1) space.

Time: O(n) for array-based XOR problems, O(1) for single-value bit operations

Space: O(1) — bit manipulation uses no extra data structures

Learn & Reference

Understanding the Pattern

Bit Manipulation Pattern

Bit manipulation operates directly on the binary representation of integers. By using bitwise operators instead of arithmetic or data structures, you can solve certain problems in O(1) space and often O(n) time — far more efficiently than hash-based approaches.

Decimal 13 = Binary 1101
         AND (&)  OR (|)  XOR (^)  NOT (~)
1 op 1:    1       1       0        0/1
1 op 0:    0       1       1
0 op 0:    0       0       0

Core Bitwise Operators

| Operator | Symbol | What It Does | |----------|--------|-------------| | AND | & | Both bits must be 1 | | OR | \| | At least one bit is 1 | | XOR | ^ | Bits must differ (1 if different) | | NOT | ~ | Flip all bits | | Left shift | << | Multiply by 2^k (shift bits left) | | Right shift | >> | Divide by 2^k (shift bits right) |

The Power of XOR

XOR is the workhorse of bit manipulation. Key properties:

a ^ a = 0 — any number XOR itself is 0
a ^ 0 = a — any number XOR 0 is itself
XOR is commutative and associative — order doesn't matter

This means if you XOR all elements where every number appears twice except one, all pairs cancel out and the unique number remains.

[4, 1, 2, 1, 2]
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4

Bit Masking

A bitmask uses individual bits as boolean flags. Common operations on the k-th bit:

Check bit k:    (n >> k) & 1        or  n & (1 << k)
Set bit k:      n | (1 << k)
Clear bit k:    n & ~(1 << k)
Toggle bit k:   n ^ (1 << k)

Counting Set Bits (Brian Kernighan's Algorithm)

The trick n & (n - 1) clears the lowest set bit. Repeat until n becomes 0 to count all set bits in O(number of set bits) time.

n = 1011 (11)
n & (n-1) = 1011 & 1010 = 1010  → count = 1
n & (n-1) = 1010 & 1001 = 1000  → count = 2
n & (n-1) = 1000 & 0111 = 0000  → count = 3

Power of 2 Check

A power of 2 has exactly one set bit: n > 0 && (n & (n - 1)) == 0.

  8 = 1000    →  8 & 7 = 1000 & 0111 = 0000  ✓ power of 2
 10 = 1010    → 10 & 9 = 1010 & 1001 = 1000  ✗ not power of 2

Sum Without Arithmetic Operators

XOR gives the sum without carries. AND followed by left shift gives the carry. Repeat until carry is 0.

a = 5 (101), b = 3 (011)
sum = 101 ^ 011 = 110      carry = (101 & 011) << 1 = 010
sum = 110 ^ 010 = 100      carry = (110 & 010) << 1 = 100
sum = 100 ^ 100 = 000      carry = (100 & 100) << 1 = 1000
sum = 000 ^ 1000 = 1000    carry = 0  → done! answer = 8

Common Mistakes

Operator precedence — Bitwise operators have lower precedence than comparison operators in most languages. Always use parentheses: (n & 1) == 0, not n & 1 == 0 (which is n & (1 == 0)).
Signed vs unsigned right shift — In Java, >> is arithmetic (preserves sign bit), >>> is logical (fills with 0). Using the wrong one on negative numbers gives unexpected results.
Integer overflow with shifts — 1 << 31 overflows a 32-bit signed int. Use 1L << 31 in Java or ensure proper types.
XOR on empty arrays — XOR of zero elements is 0, which may be a valid number. Always check array length.
Forgetting negative numbers — In two's complement, ~n = -(n+1). Bit tricks that assume positive inputs may break with negatives.
Off-by-one in bit positions — Bits are 0-indexed from the right. Bit 0 is the least significant bit (1 << 0 = 1), not bit 1.

When to Use

Find the single number that appears once (all others appear twice) — XOR all elements

Detect missing or duplicate numbers — XOR expected range with actual values

Check if a number is a power of 2 — `n & (n-1) == 0`

Count the number of set bits (Hamming weight / popcount)

Add two numbers without using + or - operators

Problems that say O(1) extra space and involve integer properties

Toggling, setting, or clearing specific flags

Problems where every element appears k times except one

Keywords: bitwise, binary representation, single number, without arithmetic

Template

1# --- XOR: Find Single Number ---
2# Every element appears twice except one. Find it.
3def single_number(nums):
4    result = 0
5    for num in nums:
6        result ^= num
7    return result
8
9# --- Count Set Bits (Brian Kernighan) ---
10def count_set_bits(n):
11    count = 0
12    while n:
13        n &= n - 1  # Clear the lowest set bit
14        count += 1
15    return count
16
17# --- Bit Masking: Check / Set / Clear / Toggle ---
18def check_bit(n, k):
19    return (n >> k) & 1
20
21def set_bit(n, k):
22    return n | (1 << k)
23
24def clear_bit(n, k):
25    return n & ~(1 << k)
26
27def toggle_bit(n, k):
28    return n ^ (1 << k)
29
30# --- Power of 2 Check ---
31def is_power_of_two(n):
32    return n > 0 and (n & (n - 1)) == 0

{ }

Syntax Reference

1# === Bitwise Operators ===
2a & b            # AND
3a | b            # OR
4a ^ b            # XOR
5~a               # NOT (inverts all bits)
6a << k           # Left shift by k (multiply by 2^k)
7a >> k           # Right shift by k (divide by 2^k)
8
9# === Built-in Functions ===
10bin(n)           # Binary string: bin(13) → '0b1101'
11int('1101', 2)  # Parse binary string: → 13
12n.bit_length()  # Number of bits needed: (13).bit_length() → 4
13n.bit_count()   # Count set bits (Python 3.10+): (13).bit_count() → 3
14
15# === Common Bit Tricks ===
16n & (n - 1)      # Clear lowest set bit
17n & (-n)         # Isolate lowest set bit
18n & 1            # Check if odd (last bit)
19(n >> k) & 1     # Get k-th bit
20n | (1 << k)     # Set k-th bit
21n & ~(1 << k)    # Clear k-th bit
22n ^ (1 << k)     # Toggle k-th bit

📋

Common Recipes

1# Recipe 1: Single Number (XOR)
2def single_number(nums):
3    result = 0
4    for num in nums:
5        result ^= num
6    return result
7
8# Recipe 2: Count Set Bits (Brian Kernighan)
9def count_bits(n):
10    count = 0
11    while n:
12        n &= n - 1  # Clear lowest set bit
13        count += 1
14    return count
15
16# Recipe 3: Is Power of 2
17def is_power_of_two(n):
18    return n > 0 and (n & (n - 1)) == 0
19
20# Recipe 4: Add Without Plus (Sum of Two Integers)
21def get_sum(a, b):
22    mask = 0xFFFFFFFF
23    while b & mask:
24        carry = (a & b) << 1
25        a = a ^ b
26        b = carry
27    return a & mask if b > 0 else a

O(n)

Complexity

Operation	Time	Space
Single Number (XOR all)	O(n)	O(1)
Count Set Bits (Kernighan)	O(log n)	O(1)
Count Set Bits (built-in)	O(1)	O(1)
Power of 2 Check	O(1)	O(1)
Sum Without Arithmetic	O(log n)	O(1)
Get/Set/Clear/Toggle Bit	O(1)	O(1)

Watch Out

✗Operator precedence — Bitwise operators have lower precedence than comparison operators in most languages. Always use parentheses: `(n & 1) == 0`, not `n & 1 == 0` (which is `n & (1 == 0)`).
✗Signed vs unsigned right shift — In Java, `>>` is arithmetic (preserves sign bit), `>>>` is logical (fills with 0). Using the wrong one on negative numbers gives unexpected results.
✗Integer overflow with shifts — `1 << 31` overflows a 32-bit signed int. Use `1L << 31` in Java or ensure proper types.
✗XOR on empty arrays — XOR of zero elements is 0, which may be a valid number. Always check array length.
✗Forgetting negative numbers — In two's complement, `~n = -(n+1)`. Bit tricks that assume positive inputs may break with negatives.
✗Off-by-one in bit positions — Bits are 0-indexed from the right. Bit 0 is the least significant bit (`1 << 0 = 1`), not bit 1.

PRACTICE PROBLEMS

Design-Focused DSA