Number Complement: Flipping Bits with XOR

LeetCode Number Complement (Problem 476) asks you to flip every bit in a positive integer's binary representation. Given num = 5, its binary is 101. Flipping each bit gives 010, which is 2. Return 2.

The complement of a number is defined by flipping all the bits in its binary representation, but only the significant bits. Leading zeros do not count.

The problem

You are given a positive integer num. Return its complement -- the number you get when every 1 becomes 0 and every 0 becomes 1 in its binary form. Only the significant bits matter (no leading zeros).

Why this problem matters

Bit flipping is one of the most fundamental operations in low-level programming. It shows up in networking (subnet masks), cryptography (one-time pads), and error detection (checksums). In interviews, this problem tests whether you understand XOR and how to construct bitmasks on the fly.

The problem looks trivial at first glance, but the trick is building a mask that covers exactly the right number of bits. That skill transfers directly to harder problems like Bitwise AND of Numbers Range and Maximum XOR of Two Numbers in an Array.

The key insight

XOR with 1 flips a bit. 1 ^ 1 = 0 and 0 ^ 1 = 1. So if you XOR your number with a mask of all 1s that has the same bit length, every bit gets flipped.

The question becomes: how do you build that mask? If num has k significant bits, the mask is (1 << k) - 1. For num = 5 (binary 101), k = 3, so the mask is (1 << 3) - 1 = 7 (binary 111). Then 5 ^ 7 = 2.

That is the entire algorithm. Find the bit length, build the mask, XOR.

The code

def findComplement(num):
    bit_length = num.bit_length()
    mask = (1 << bit_length) - 1
    return num ^ mask

Python's bit_length() method gives you the number of significant bits directly. If you want to avoid that built-in, you can compute it manually:

def findComplement(num):
    mask = 1
    while mask < num:
        mask = (mask << 1) | 1
    return num ^ mask

This second version builds the mask by repeatedly shifting left and setting the lowest bit until the mask is at least as large as num. For num = 5, the mask grows from 1 to 11 to 111, which equals 7.

Why this works

XOR has a clean property: XOR with 1 always flips a bit, and XOR with 0 always preserves it. When you XOR num with a mask of all 1s, every significant bit in num gets flipped. The mask is exactly the right width because we compute it from the bit length of num.

The expression (1 << k) - 1 works because shifting 1 left by k positions gives you a 1 followed by k zeros (a power of two). Subtracting 1 turns that into k ones. For example, 1 << 3 = 1000 in binary, and 1000 - 1 = 0111.

Visual walkthrough

Let's trace through num = 5 step by step. Watch how we find the binary representation, build the mask, and XOR to get the complement.

Complexity analysis

Computing the bit length takes O(log n) since you need to count the number of bits. The mask construction and XOR are both O(1) for fixed-width integers. In practice, for 32-bit integers, everything runs in constant time.

No extra data structures are needed. You use one variable for the mask and one XOR operation.

Building blocks

XOR flips bits when paired with 1. This is the core property. a ^ 1 = NOT a for a single bit. When you XOR an entire number with a mask of all 1s, you effectively negate every significant bit. This pattern appears in problems like Hamming Distance and Single Number.

Mask construction with (1 << k) - 1. This idiom creates a number with k consecutive 1-bits. It is one of the most common bitmask patterns in competitive programming. You will use it again in problems involving subsets, range queries on bits, and permission flags.

Bit length determines the mask width. The number of significant bits in num tells you exactly how wide your mask needs to be. Going too wide would flip bits that do not exist in the original number. Going too narrow would leave some bits unflipped.

Edge cases

num = 1: Binary is 1. Bit length is 1, mask is 1. 1 ^ 1 = 0. The complement of 1 is 0.

Powers of two: If num = 8 (binary 1000), bit length is 4, mask is 1111 (15). 8 ^ 15 = 7 (binary 0111). All the trailing zeros become ones.

All bits set: If num = 7 (binary 111), mask is also 111. 7 ^ 7 = 0. When every bit is already 1, flipping them all gives 0.

Large numbers: The algorithm works for any positive integer. For num = 2^31 - 1 (all 31 bits set), the complement is 0. The mask construction handles this cleanly since (1 << 31) - 1 is the same value.

From understanding to recall

The mental model is three words: length, mask, XOR. Find the bit length of the number, build a mask of that many 1s, and XOR them together. That is the entire solution.

The recall anchor: "mask of all 1s, then XOR." If you can pull that phrase from memory, the code writes itself in about 15 seconds.

Practice this problem from a blank editor a few times over the next week. By the second or third attempt, you should be writing the solution faster than you can read the problem statement. That is when you know you own the pattern.

Related posts

• Hamming Distance - XOR and bit counting
• Number of 1 Bits - Counting set bits with Kernighan's trick
• Reverse Bits - Bit-by-bit reversal pattern