Bit Manipulation Pattern | CodeTutor

Bit Manipulation

Easy

4 questions using this pattern

What is Bit Manipulation?

Techniques using binary operations (AND, OR, XOR, NOT, shifts) to solve problems efficiently, often achieving O(1) space where other approaches need O(n).

Think of it like this...

Think of XOR like a light switch. Flip it once (XOR with a number) and the light turns on. Flip it again with the same number and it turns off. Numbers that appear twice "flip twice" and cancel out, leaving only the single number.

Another analogy: imagine each number is a musical note. Playing the same note twice creates silence (destructive interference). When you play all notes together, pairs cancel out, and only the unique note remains audible.

Core Concept

Bit manipulation uses properties of binary operations to solve problems elegantly. The most important operations:

XOR (⊕):

a ⊕ a = 0 — any number XORed with itself is zero
a ⊕ 0 = a — XORing with zero preserves the value
XOR is commutative and associative — order doesn't matter

AND (&):

a & (a-1) removes the lowest set bit
a & 1 checks if a number is odd

OR (|):

a | (1 << k) sets the k-th bit

Shifts:

a << k multiplies by 2^k
a >> k divides by 2^k (floor)

Single Number

Bit Manipulation

def single_number(nums: list[int]) -> int:

    result = 0

    for num in nums:

        result ^= num  # XOR each number

    return result

Variables

nums=[2, 2, 1]

nums

Problem

We have an array where every element appears exactly twice, except for one element that appears only once. Our goal is to find this unique element.

1/19

Visual Walkthrough

XOR Cancellation Example:

nums = [2, 2, 1]

Step 1: result = 0
        0000 XOR 0010 = 0010 (result = 2)

Step 2: result = 2
        0010 XOR 0010 = 0000 (pair cancels!)

Step 3: result = 0
        0000 XOR 0001 = 0001 (result = 1)

Answer: 1 (the single number)

Bit-by-bit XOR:

   0010   (2)
⊕  0010   (2)
--------
   0000   (0) — same bits cancel!

   0000   (0)
⊕  0001   (1)
--------
   0001   (1) — XOR with 0 preserves

Code Template

Use this skeleton as a starting point for problems using this pattern:

python

# XOR all elements - pairs cancel, unique remains
def find_single(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result


# Check if n is a power of 2
def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0


# Count number of 1 bits (Brian Kernighan)
def count_bits(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)  # Remove lowest set bit
        count += 1
    return count


# Get k-th bit (0-indexed from right)
def get_bit(n: int, k: int) -> int:
    return (n >> k) & 1


# Set k-th bit
def set_bit(n: int, k: int) -> int:
    return n | (1 << k)


# Clear k-th bit
def clear_bit(n: int, k: int) -> int:
    return n & ~(1 << k)


# Toggle k-th bit
def toggle_bit(n: int, k: int) -> int:
    return n ^ (1 << k)


# Swap without temp (XOR swap)
def swap(a: int, b: int) -> tuple[int, int]:
    a ^= b
    b ^= a
    a ^= b
    return a, b


# Find two single numbers (all others appear twice)
def find_two_singles(nums: list[int]) -> list[int]:
    # XOR all numbers - result is xor of the two singles
    xor_all = 0
    for num in nums:
        xor_all ^= num

    # Find a bit where the two singles differ
    diff_bit = xor_all & (-xor_all)  # Lowest set bit

    # Partition numbers by this bit and XOR each group
    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num

    return [a, b]

Recognition Signals

Look for these keywords and patterns in problem descriptions:

find the single/unique elementevery element appears twice except oneO(1) extra spaceXORbit manipulationwithout using extra memorypower of 2count bitsbinary representationtoggleswap without temp

When to Use

Finding unique elements when pairs cancel out (XOR)
Checking powers of 2 (n & (n-1) == 0)
Counting set bits (Brian Kernighan's algorithm)
Swapping without temp variable (a ^= b; b ^= a; a ^= b)
Problems requiring O(1) extra space
Toggling or flipping bits

Common Mistakes

Forgetting XOR order doesn't matter

XOR is commutative (a⊕b = b⊕a) and associative ((a⊕b)⊕c = a⊕(b⊕c)). You can process elements in any order and still get the same result.

Fix:

Trust the properties. The order of XOR operations doesn't affect the final result. Focus on the logic, not the sequence.

Using addition instead of XOR

Addition doesn't cancel pairs. 2 + 2 = 4, not 0. XOR is special because a ⊕ a = 0 while a + a = 2a.

Fix:

Remember: XOR cancels identical values, addition accumulates them. Use ^= for pair cancellation, not +=.

Forgetting to handle negative numbers

Pattern Variations

Single Number (pairs cancel)

XOR all elements to find the one that appears once when others appear twice.

Examples: Single Number, Single Number II (modular arithmetic)

Two Single Numbers

Use XOR to find a differing bit, then partition elements to separate the two unique numbers.

Examples: Single Number III

Power of Two

Check if n & (n-1) == 0. Powers of 2 have exactly one set bit.

Examples: Power of Two, Power of Four

Bit Counting

Count set bits using n &= (n-1) to remove lowest bit each iteration.

Examples: Number of 1 Bits, Counting Bits

Bit Masking

Use masks to extract, set, clear, or toggle specific bits.

Examples: Reverse Bits, Bitwise AND of Numbers Range

Learning Path

1Warmup0/3

Start here to build foundational understanding.

Add Two IntegersOptimal

#2235Easy

Number of 1 BitsOptimal

#191Easy

Single NumberOptimal

#136Easy

2Core Practice0/1

Master the pattern with these representative problems.

Sum of Two IntegersOptimal

#371Medium

Related Patterns

Explore similar techniques:

Dynamic Programming

Break problems into overlapping subproblems, storing results to avoid recomputation. This transforms exponential time complexity into polynomial by trading space for time.

Greedy

Make locally optimal choices at each step, hoping to find a global optimum. Greedy algorithms are simple and efficient but only work when the problem has the greedy choice property—local optima lead to global optimum.