Bit Manipulation

5 is 0101 in binary. Applying 5 & 4 produces 0100, clearing the lowest set bit. Work with four visible bits before generalizing; choose a width before handling negative values.

Treat an integer as a row of 0/1 switches. Bitwise operators act on many bits at once. A fixed-width word or a fixed alphabet can use constant space. A Python integer representing a growing set still needs space proportional to its number of bits.

Every solution has to respect two principles:

1. Think one bit at a time. &, |, ^ and ~ compute each bit on its own, with no interaction between bits, so once one bit is clear the whole number is clear. Only addition and subtraction let a low bit affect higher ones (carries and borrows), and tricks like x & (x - 1) rely on exactly that.
2. Fix the width and the sign first. Python ints have no width limit, and a negative number behaves as if it had infinitely many 1s on the left. When a problem is defined on 32-bit integers, you truncate with & 0xFFFFFFFF yourself and convert the result back to a signed value at the end.

The article goes in this order, and each step adds exactly one idea:

When to Use This Pattern

Brute force usually needs an extra data structure: a set or a counting dict to find the number that appears once, O(n) space; a set to check a string for repeated characters; recursion to enumerate subsets. Bit manipulation packs facts like "is it present" or "has it appeared an odd or even number of times" into one bit of an integer, and one operation handles every bit.

This works because of the first principle: bits are independent. Take 5 and 3:

Each column only looks at its own two digits, giving 5 & 3 = 1, 5 | 3 = 7 and 5 ^ 3 = 6. Addition is different: 5 + 3 = 8 = 0b1000, and the carry from bit 0 travels all the way to bit 3.

Recognition Checklist

• The problem mentions binary, bits, "no extra space", or "without using + or -"
• Things that come in pairs should cancel out, leaving one
• The universe is small (a character set, n ≤ 20 items), so membership fits in one bit each
• You must process a fixed-width integer bit by bit (reversing, counting)
• Inputs may be negative, or overflow is defined in terms of 32-bit signed integers

Before You Code

Answer these three on paper before writing code. The first matches the second principle and decides whether you need a mask; the second translates the problem into "what happens at each bit", which is the first principle; once those two are answered, the third usually has only one option left.

1. Width and sign: how many bits, and can the value be negative? If the problem says "32-bit unsigned", loop exactly 32 times. If negatives can appear, decide whether Python needs & 0xFFFFFFFF first and a conversion back to negative at the end.
2. What does each bit mean? The i-th binary digit of a number, whether element i is in a set, whether some letter has appeared, or the parity of how many 1s have landed on that bit? Write it as one sentence.
3. Which primitive? XOR cancellation, reading and setting a bit, clearing the lowest 1, set union and intersection, truncating with a mask. If nothing comes to mind, hand-trace a 4-bit example.

Try LC 190 Reverse Bits: reverse the whole 32-bit binary form of an integer (the full statement is in Step 2).

• Width and sign: process all 32 bits. Under the current statement the input is non-negative and even, so after reversing, the top bit (bit 31) is also 0 and the result is never negative. The loop must run exactly 32 times, not while n: zeros in the input's high bits land in the low bits after reversal and still need their places.
• What each bit means: bit 31 − i of the result = bit i of the input.
• Primitive: each round, take the input's lowest bit with n & 1, push it into the lowest bit of the result with res << 1 | bit, then n >>= 1. Round 1 takes bit 0 of the input; 31 more rounds follow, each shifting it left once, so it ends up exactly at bit 31.

Step 2 turns this into code.

Single Number (LeetCode 136)

Given a nonempty integer array with one singleton and every other value occurring exactly twice, return the singleton value in O(n) time and O(1) auxiliary space. Return neither its index nor a generic duplicate result for arbitrary multiplicities.

Input: nums = [4, 1, 2, 1, 2]. Expected: 4.

Rule used: a ^ a = 0 and a ^ 0 = a, and order does not matter, so every pair cancels.

1. Walk it by hand

2. Read the rule off the table

• Every row does the same thing: res ^= num.
• The first time a number appears, its bits turn on in res; the second time, the same bits turn off.
• After all rows, only the number that appears once still has its bits in res.

3. Turn each row into code

def single_number(nums):
    res = 0
    for num in nums:
        res ^= num
    return res

Core Templates

All five steps follow the same routine: answer the three questions, then check against the two principles from the top: is it clear what happens at each bit, and have the width and negatives been handled?

Step 1: XOR Cancellation

Problem: every number in the array appears exactly twice except one; find that one (LC 136).

The input is a nonempty integer array, and negatives are allowed. One value appears exactly once; every other value appears exactly twice. Return the value that appears once.

For example, [4, 1, 2, 1, 2] → 4: 1 and 2 each appear twice, and only 4 appears once.

Use O(n) time and O(1) extra space. The premise is "every other value exactly twice", not "find any value with an odd count".

The three questions:

• Width and sign: any integer, possibly negative. XOR works for negatives too: a negative has infinitely many 1s on the left, and XOR-ing two equal negatives cancels every bit to 0. No mask needed.
• What each bit means: bit k of res = whether the numbers with a 1 at bit k have appeared an odd or even number of times so far.
• Primitive: XOR. a ^ a = 0, a ^ 0 = a, and order doesn't matter, so XOR-ing everything cancels the pairs and leaves the number that appears once.

def single_number(nums):
    res = 0                          # XOR with 0 changes nothing
    for num in nums:
        res ^= num                   # numbers that come in pairs cancel out
    return res


assert single_number([4, 1, 2, 1, 2]) == 4
assert single_number([2, 2, 1]) == 1
assert single_number([-3, 7, 7]) == -3
assert single_number([7]) == 7

Look at nums = [4, 1, 2, 1, 2] bit by bit, counting each bit separately:

res = 100 = 4. Each bit counts its own parity independently, which is the first principle.

One more of the same: Missing Number (LC 268).

The input is an array of length n holding n of the n + 1 numbers 0..n, all distinct, with exactly one missing. Return the missing value, not an index.

For example, [3, 0, 1] → 2: n = 3, and 2 is missing from 0..3. [0] → 1: n = 1, and 1 is missing from 0..1. Either end of the range, 0 or n, can be the missing one.

The follow-up asks for O(n) time and O(1) extra space.

Think first: The last problem relied on values coming in pairs. Here each value appears only once. What could you pair each value with? The array's indices are 0..n−1 and the range is 0..n; which number is the difference?

def missing_number(nums):
    res = len(nums)                  # indices only reach n-1, so seed with n
    for i, num in enumerate(nums):   # i is the index, num the value at that index
        res ^= i ^ num               # XOR the index and the value together
    return res


assert missing_number([3, 0, 1]) == 2
assert missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
assert missing_number([0]) == 1
assert missing_number([]) == 0

Step 1 recap

• What it solves: when every value except the answer appears an even number of times, XOR cancels all of them.
• The key line: res ^= num, with res starting at 0.
• What the variants change: in LC 268 each value appears only once, so the indices 0..n−1 plus an extra n supply the partners.
• Easiest mistake: an incomplete pairing. Forget to seed LC 268 with n and you can't find the answer when n itself is missing.

XOR only tells you whether each bit has an odd or even count of 1s. When the problem needs you to pick out one bit, or set one bit, you need Step 2's reads and writes.

Step 2: Read and Write One Bit, Build Bit by Bit

Problem: LC 190 Reverse Bits; the three questions were answered above.

The input is an integer n. Under the current LeetCode statement, 0 ≤ n ≤ 2³¹ − 2 and n is even. Write n as 32 binary digits (padding the high end with zeros), reverse all of them, and return the resulting integer.

For example, n = 2: the 32-bit form is 000…0010 (bit 1 is set). After reversing, that 1 lands at bit 30, so the result is 2³⁰ = 1073741824. n = 0 returns 0. The padded zeros take part in the reversal; that's the heart of the problem.

The code below is correct for any 32-bit unsigned input, so the asserts also test an odd value and 0xFFFFFFFF. Those come from an older version of the problem; the current statement doesn't require them.

First, the ways to read and write a single bit. Each one builds a mask with only bit i set, 1 << i, and combines it with n in one operation:

Work the first row: n >> 1 shifts 1010 right by one to get 101, whose lowest bit is the old bit 1; & 1 keeps only that lowest bit, giving 1. The clear row: 1 << 3 is 1000, ~ flips it to …0111 (bit 3 is 0, every other bit 1), and ANDing with 1010 clears only bit 3, giving 0010.

Building a result bit by bit uses a different move: instead of computing which position a bit belongs at, shift the result left by one each round and drop the new bit into the lowest position, res = (res << 1) | bit. Bits added earlier get pushed toward the high end by later shifts.

def reverse_bits(n):
    res = 0
    for _ in range(32):              # exactly 32 rounds: reversed high zeros still take places
        res = (res << 1) | (n & 1)   # take n's lowest bit, push it into res's lowest bit
        n >>= 1
    return res


assert reverse_bits(2) == 1073741824            # the example from the statement: bit 1 moves to bit 30
assert reverse_bits(0b00000010100101000001111010011100) == 0b00111001011110000010100101000000
assert reverse_bits(1) == 1 << 31
assert reverse_bits(0) == 0
assert reverse_bits(0xFFFFFFFF) == 0xFFFFFFFF

Pretend the width is only 4, with n = 0b1011:

1011 reversed is 1101. What if you write while n? For 4-bit n = 0b0010, round 1 takes a 0, round 2 takes a 1, n hits 0 and the loop stops, so res = 01 = 1; the right answer is 0100 = 4. The two missing zeros were the input's high bits, which should land in the result's low bits.

One more of the same: Add Binary (LC 67).

The inputs are two binary strings a and b. They are nonempty, contain only '0' and '1', and have no leading zeros except for "0" itself. Return their sum, also as a binary string, not a decimal integer.

For example, "11" + "1" → "100": 3 + 1 = 4, and 4 in binary is 100.

Think first: Reverse Bits took bits one at a time from the low end. Which end of a string holds the lowest digit? At most how many 1s get added at one position, and how do you pull "this digit" and "the carry" out of that sum? Once both strings are used up, what might still be left?

def add_binary(a, b):
    i, j, carry, out = len(a) - 1, len(b) - 1, 0, []   # start at the right end (lowest digit) of each
    while i >= 0 or j >= 0 or carry:     # don't drop the final carry
        total = carry
        if i >= 0:
            total += int(a[i])           # character '0'/'1' becomes integer 0/1
            i -= 1
        if j >= 0:
            total += int(b[j])
            j -= 1
        out.append(str(total & 1))       # this digit
        carry = total >> 1               # the carry
    return "".join(reversed(out))        # out is low to high; reverse and join into a string


assert add_binary("11", "1") == "100"
assert add_binary("1010", "1011") == "10101"
assert add_binary("0", "0") == "0"
assert add_binary("1", "111") == "1000"

Variation: fast exponentiation (LC 50)

The inputs are a real number x and an integer n in the signed 32-bit range, possibly negative. Return the value of xⁿ.

For example, x = 2, n = −2 → 0.25: a negative exponent means a reciprocal, 2⁻² = 1/4, not a negative result. n = 0 returns 1.

The problem rules out undefined cases such as 0 to a non-positive power; the minimum exponent n = −2³¹ must still work.

Think first: Step 2 keeps reading a number's bits from low to high. Write the exponent in binary, say 13 = 1101: which factors does xⁿ split into? How are those factors related, and can each round get the next one from the previous one with a single multiplication? How do you turn a negative exponent into a positive one?

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n             # simultaneous assignment: the right side uses the old values
    res = 1.0
    while n:
        if n & 1:                    # this bit of the exponent is 1, multiply in the current x
            res *= x
        x *= x                       # x becomes the power for the next bit: x, x^2, x^4, ...
        n >>= 1
    return res


assert my_pow(2.0, 10) == 1024.0
assert my_pow(3, 13) == 1594323
assert my_pow(2.0, -2) == 0.25                # the example from the statement
assert my_pow(5.0, 0) == 1.0

Step 2 recap

• What it solves: reading and writing a single bit, and building a result one bit at a time from the low end.
• The key line: res = (res << 1) | (n & 1), then n >>= 1.
• What the variants change: LC 67 replaces "take one bit" with "add three digits and split the sum into this digit and a carry"; LC 50 stops building result bits and instead lets each bit of the exponent decide whether to multiply in the current x.
• Easiest mistake: the loop count. With a fixed width (LC 190) loop exactly 32 times, never while n; LC 67 needs or carry or the top carry is lost.

Step 2 reads one bit at a time, so counting through 32 bits takes 32 rounds. If you only care about the bits that are 1, subtraction's borrow lets you jump straight to the next 1.

Step 3: The Lowest 1 Bit: `x & (x - 1)` and `x & -x`

Problem : count the 1s in the binary form of a non-negative integer ( LC 191 ). The input is a positive integer n (1 ≤ n ≤ 2³¹ − 1). (Pro lesson)

Step 3 recap

What it solves : visiting only the bits that are 1 instead of scanning every bit. The key line : x & (x - 1) clears the lowest 1; (Pro lesson)

Step 4: An Integer as a Set

Problem : return every subset of an array of distinct elements ( LC 78 ). The input is an integer array nums with distinct elements. (Pro lesson)

Variation: Minimum Array End (LC 3133)

The inputs are two positive integers n and x. Build an array of n positive integers that is strictly increasing and whose elements, all toge… (Pro lesson)

Step 4 recap

What it solves : when the universe is small (n ≤ 20, 26 letters, 256 characters), one integer's bits record "is item i present", and set ope… (Pro lesson)

Step 5: Emulating 32 Bits in Python

Problem : add two 32-bit signed integers without + or - ( LC 371 ). The inputs are two integers a and b, possibly negative. (Pro lesson)

Variation: Reverse Integer (LC 7)

The input is a 32-bit signed integer x. Reverse its decimal digits, keep the original sign, and return the resulting integer. (Pro lesson)

Step 5 recap

What it solves : Python ints have no width and negatives have infinitely many 1s on the left; (Pro lesson)

All Five Steps Together

Step What each bit means Core operation What about negatives Representative problems Step 1 Parity of how many 1s landed on this bit res ^=… (Pro lesson)

One Problem, Many Disguises

LC1371 takes lowercase letters and returns the longest contiguous substring length in which each of a/e/i/o/u occurs an even number of times… (Pro lesson)

Common Pitfalls

Writing 1 << k + 1 to mean (1 << k) + 1 . In Python shifts bind looser than + and - , so it computes 1 << (k + 1) . (Pro lesson)

Say It in the Interview

Confirm first whether the input is 32-bit and whether it can be negative, then explain it like this (using LC 371 ): I'd simulate a hardware… (Pro lesson)