Complement of Base 10 Integer

Complement of Base 10 Integer

What is this problem about?

The Complement of Base 10 Integer interview question asks you to find the "bitwise complement" of a given integer N. The complement is formed by changing every 0 to a 1 and every 1 to a 0 in its binary representation. For example, 5 in binary is 101. Its complement is 010, which is 2 in base 10. Crucially, we only care about the bits up to the most significant bit of the original number.

Why is this asked in interviews?

Companies like Amazon and Google use this Bit Manipulation interview pattern to test a candidate's comfort level with binary operations. It requires understanding bitwise NOT (~), AND (&), and XOR (^). It also tests whether you can create a "mask" to isolate the specific bits you want to flip.

Algorithmic pattern used

The most common approach is using an XOR Mask.

1. Calculate how many bits are in the binary representation of N.
2. Create a "mask" of the same length consisting of all 1s. For example, if N=5 (101), the mask is 7 (111).
3. The complement is N XOR mask. Alternatively, you can find the smallest power of 2 greater than N, subtract 1 to get the mask, and then perform the XOR.

Example explanation

N = 10

1. Binary of 10 is 1010.
2. The number of bits is 4.
3. Create a mask of 4 ones: 1111 (which is 15 in decimal).
4. Perform XOR: 1010 ^ 1111 = 0101.
5. Binary 0101 is 5 in decimal. Result: 5.

Common mistakes candidates make

• Using the Standard NOT: In many languages, ~N flips all bits in a 32-bit or 64-bit integer, including the sign bit, leading to a negative number instead of the expected complement.
• Handling 0: The binary of 0 is "0", so its complement is "1". Some algorithms that use loops to find the bit length might fail on 0.
• Complexity: Writing a loop to build the binary string and then another loop to flip it, which is much slower than bitwise operations.

Interview preparation tip

To quickly find a mask of all 1s for a number N, you can use the property that mask = (1 << number_of_bits) - 1. Just be careful with potential overflow if N is very large.