Complement of Base 10 Integer: Bit Flipping with XOR

You are given a non-negative integer n. Your task is to return its complement: the number you get when you flip every bit in its binary representation. This is LeetCode 1009: Complement of Base 10 Integer.

Example: n = 5 (binary 101) has complement 010 = 2.

Why this problem matters

Bit manipulation problems can feel niche at first, but the techniques behind them show up constantly in systems programming, cryptography, graphics, and networking. The complement operation in particular is one of the most fundamental bitwise transformations. Knowing how to flip bits efficiently using XOR is a skill that transfers directly to problems involving toggling flags, computing checksums, and working with bitmasks in general.

This problem also gives you practice constructing a bitmask, which is one of the core building blocks in bit manipulation. Many harder problems, like finding the single number in an array, computing bitwise AND over a range, or reversing bits, rely on your ability to build masks of specific shapes. If you can confidently create a mask of all 1s that matches the bit length of an arbitrary number, you have a tool that applies far beyond this single problem.

Finally, LeetCode 1009 is a great warm-up for understanding XOR at a deeper level. XOR has the unique property that x XOR 1 = NOT x for a single bit. Once you internalize that, the solution to this problem becomes almost obvious, and you will start seeing XOR opportunities in other problems like Single Number, Missing Number, and bitwise range queries.

The key insight

To flip every bit of n, you need a number where every bit position that n occupies is set to 1. When you XOR n with this mask, every 0 in n becomes 1, and every 1 becomes 0. That is exactly the complement.

The challenge is constructing the right mask. You cannot just use 0xFFFFFFFF (all 32 bits set to 1) because that would flip leading zeros too. For example, 5 is 101 in binary, but in a 32-bit representation it is 00000000000000000000000000000101. Flipping all 32 bits would give you a huge number, not 2.

You need a mask with exactly as many 1-bits as n has bits. For n = 5 (3 bits), the mask is 111 = 7. For n = 10 (4 bits, 1010), the mask is 1111 = 15.

Algorithm steps:

1. Find the number of bits in n
2. Create a mask of all 1s with that many bits (2^bits - 1)
3. XOR n with the mask

The solution

def bitwise_complement(n):
    if n == 0:
        return 1
    mask = 1
    while mask <= n:
        mask <<= 1
    return (mask - 1) ^ n

The function starts by handling the edge case where n = 0. The complement of 0 is 1 (the only bit is 0, and flipping it gives 1).

For all other values, the mask starts at 1 and keeps shifting left until it exceeds n. At that point, mask is the smallest power of 2 that is strictly greater than n. Subtracting 1 from a power of 2 gives a number with all lower bits set to 1. For example, if n = 5, the mask shifts to 8 (1000), and 8 - 1 = 7 (111). XOR-ing 5 (101) with 7 (111) gives 2 (010).

This approach avoids needing to calculate log2(n) or count bits explicitly. The while loop naturally finds the right power of 2 by doubling until it passes n.

Let's trace through a second example to solidify the logic. Take n = 10, which is 1010 in binary (4 bits). The mask starts at 1, then shifts to 2, 4, 8, and finally 16. Now mask = 16 (10000), and 16 - 1 = 15 (1111). XOR-ing 10 (1010) with 15 (1111) gives 5 (0101). You can verify: flipping each bit of 1010 does indeed give 0101.

Here is the same solution in Java and TypeScript for reference:

public int bitwiseComplement(int n) {
    if (n == 0) return 1;
    int mask = 1;
    while (mask <= n) mask <<= 1;
    return (mask - 1) ^ n;
}

function bitwiseComplement(n: number): number {
    if (n === 0) return 1;
    let mask = 1;
    while (mask <= n) mask <<= 1;
    return (mask - 1) ^ n;
}

The logic is identical across languages. The only thing that changes is syntax.

Visual walkthrough

Each step card shows a single phase of the algorithm. You start by converting the decimal number to binary, then construct a mask of the same width, XOR the two together, and read out the decimal result. The entire operation touches each bit exactly once.

Notice how the mask is the crucial piece. Without it, you would not know which bits to flip. The mask acts as a template that says "these are the bit positions that matter." Every position in the mask is 1, so XOR flips every corresponding bit in the original number. Positions outside the mask (the leading zeros) are left untouched because they are not part of the number's binary representation.

Complexity analysis

Time is O(log n) because the while loop doubles the mask on each iteration, and it takes at most floor(log2(n)) + 1 doublings to exceed n. Each iteration does constant work (a comparison and a left shift), so the total time is proportional to the number of bits in n.

Space is O(1) because you only use a single integer variable for the mask. No arrays, no recursion, no auxiliary data structures.

The building blocks

1. XOR for bit flipping

XOR has a special property: for any single bit b, b XOR 1 = NOT b. That means XOR-ing with 1 flips a bit from 0 to 1 or from 1 to 0. When you XOR an entire number with a mask of all 1s, every bit in the number gets flipped simultaneously.

This property is why XOR shows up in so many bit manipulation problems. It is the bitwise equivalent of a toggle switch. Some other useful XOR properties to remember:

• x XOR 0 = x (XOR with 0 leaves bits unchanged)
• x XOR x = 0 (XOR with itself cancels out)
• XOR is commutative and associative

The cancellation property (x XOR x = 0) is the foundation of the Single Number problem, where every element appears twice except one. The toggle property (x XOR 1 = NOT x) is the foundation of this complement problem.

2. Constructing a bitmask

Building a mask of all 1s with a specific width is a pattern you will use repeatedly. The general formula is (1 << k) - 1, where k is the number of bits you want. Shifting 1 left by k positions gives you a power of 2 with a single 1-bit at position k. Subtracting 1 flips that bit to 0 and sets all lower bits to 1.

For example:

• k = 3: 1 << 3 = 8 (1000), 8 - 1 = 7 (111)
• k = 4: 1 << 4 = 16 (10000), 16 - 1 = 15 (1111)
• k = 1: 1 << 1 = 2 (10), 2 - 1 = 1 (1)

This mask construction technique appears in problems involving bit ranges, subset enumeration, and permission flags. Once it becomes second nature, you will reach for it automatically whenever you need a contiguous block of 1-bits.

Edge cases

• n = 0: The complement is 1. Binary 0 flips to 1. This is a special case because 0 has zero bits in its binary representation, but by convention the complement of 0 is defined as 1. You must handle this before the while loop, since mask = 1 would immediately exceed 0 and the loop would never execute.

• n = 1: Binary 1, complement is 0. The mask is 1, and 1 XOR 1 = 0. The while loop runs once (mask goes from 1 to 2), and 2 - 1 = 1. Then 1 XOR 1 = 0.

• Power of 2: For example, n = 4 (100). The mask is 111 = 7, and 4 XOR 7 = 3 (011). The leading 1 flips to 0, and the trailing zeros flip to 1s. This pattern holds for any power of 2: the complement always has the form where every bit except the highest is set.

• All 1s in binary: For example, n = 7 (111). The mask is also 111, so 7 XOR 7 = 0. When every bit is already 1, flipping them all gives 0. This is the "inverse" of the n = 0 edge case.

• Large numbers: The algorithm works the same regardless of magnitude. For n = 1000000 (20 bits), the mask is 2^20 - 1 and the XOR produces the correct complement. The while loop runs 20 times, which is still very fast.

From understanding to recall

The complement problem is easy to understand once you see the XOR trick, but that does not mean you will remember how to construct the mask when you need it six months from now. The difference between "I learned this once" and "I can write it from memory under time pressure" comes down to deliberate practice.

Spaced repetition is the most efficient way to bridge that gap. You write the mask construction loop from scratch today, then again in a few days, then a week later. Each time, the retrieval gets faster and the pattern locks deeper into long-term memory. By the time you encounter a harder problem that needs a bitmask, like isolating a range of bits or toggling specific flags, the building block is already automatic. You spend your mental energy on the new problem, not on re-deriving fundamentals.

Related posts

• Number of 1 Bits - Counting set bits using n & (n-1). Both problems require you to think about individual bits, and the mask construction here complements the bit-clearing technique there.
• Single Number - XOR cancellation pattern. While this problem uses XOR to flip bits, Single Number uses XOR to cancel duplicates. Together they cover the two most important XOR applications.
• Reverse Bits - Another bit-by-bit transformation. Reverse Bits requires you to extract and place individual bits, while this problem flips them all at once with a mask.

If you want to build lasting fluency with bit manipulation, not just familiarity, CodeBricks breaks these patterns into drillable building blocks and schedules them with spaced repetition so you actually retain them. Understanding a technique once is not the same as being able to deploy it under pressure.