Problem Description

You need to find the complement of a given integer. The complement is obtained by flipping all the bits in the binary representation of the number - changing all 0s to 1s and all 1s to 0s.

For example, if you have the integer 5:

• Its binary representation is "101"
• After flipping all bits, you get "010"
• This equals the integer 2

Given an integer num, your task is to return its complement.

The solution uses bit manipulation with XOR operation. Here's how it works:

1. First, find the bit length of num using num.bit_length(). This tells us how many bits are needed to represent the number.

2. Create a mask with all bits set to 1 for the same length as num. This is done by calculating (1 << num.bit_length()) - 1:

   • 1 << num.bit_length() shifts 1 left by the bit length, giving us a power of 2
   • Subtracting 1 gives us a number with all bits set to 1 up to that position

3. XOR the original number with this mask using num ^ mask. The XOR operation flips bits where the mask has 1s, effectively giving us the complement.

For example with num = 5 (binary 101):

• Bit length is 3
• 1 << 3 gives us 1000 (binary) = 8 (decimal)
• 8 - 1 gives us 111 (binary) = 7 (decimal)
• 5 ^ 7 = 101 ^ 111 = 010 = 2

Intuition

When we need to flip bits, the XOR operation naturally comes to mind because of its unique property: a ^ 1 = ~a (flips the bit) and a ^ 0 = a (keeps the bit unchanged).

To flip all bits in a number, we need to XOR it with a mask that has 1s in all positions where our number has bits. But how do we create such a mask?

Let's think about what we need:

• If our number is 101 (3 bits), we need a mask 111
• If our number is 1101 (4 bits), we need a mask 1111

The pattern is clear - we need a mask with all 1s that has the same bit length as our original number.

To create this mask, we can use a clever trick:

1. Find how many bits our number uses (bit length)
2. Create a number that's one power of 2 higher than what we can represent with those bits
3. Subtract 1 from it

Why does this work? Consider num = 5 (binary 101, 3 bits):

• 1 << 3 creates 1000 (binary), which is 8
• When we subtract 1 from any power of 2, we get all 1s in the bits below it
• 1000 - 1 = 0111 (all three lower bits are 1)

Now when we XOR our original number with this mask:

• 101 ^ 111 = 010
• Each bit gets flipped because it's XORed with 1

This approach elegantly handles numbers of any size without needing to manually count or manipulate individual bits.

Solution Approach

The solution uses bit manipulation to efficiently compute the complement. Here's the step-by-step implementation:

Step 1: Find the bit length of the number

We use num.bit_length() to determine the position of the highest bit set to 1 in the binary representation of num. This tells us how many bits we need to consider.

For example:

• 5 in binary is 101, so bit_length() returns 3
• 1 in binary is 1, so bit_length() returns 1

Step 2: Construct the mask

We create a mask with all bits set to 1 up to the bit length position using the formula (1 << num.bit_length()) - 1:

• 1 << k shifts 1 left by k positions, giving us 2^k
• Subtracting 1 from 2^k gives us a number where all bits from position 0 to k-1 are set to 1

For num = 5:

• 1 << 3 = 8 (binary: 1000)
• 8 - 1 = 7 (binary: 111)

Step 3: Apply XOR operation

Finally, we XOR the original number with the mask: num ^ mask

The XOR operation has the property that:

• 0 ^ 1 = 1 (flip from 0 to 1)
• 1 ^ 1 = 0 (flip from 1 to 0)

Since our mask has all 1s in the relevant positions, every bit in num gets flipped.

For num = 5:

• 5 ^ 7 = 101 ^ 111 = 010 = 2

The complete solution in one line:

return num ^ ((1 << num.bit_length()) - 1)

This approach has O(1) time complexity for the bit operations and O(1) space complexity as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through finding the complement of num = 10:

Step 1: Convert to binary and find bit length

• 10 in binary is 1010
• 10.bit_length() returns 4 (we need 4 bits to represent 10)

Step 2: Create the mask

• Calculate 1 << 4:
  • Start with 1 (binary: 0001)
  • Shift left 4 positions: 10000 (decimal: 16)
• Calculate 16 - 1 = 15
• 15 in binary is 1111 (our mask with all 1s)

Step 3: Apply XOR to flip the bits

• Perform 10 ^ 15:

  1010  (10 in binary)
^ 1111  (15 in binary - our mask)
------
  0101  (5 in binary)

Each bit position:

• Position 3: 1 ^ 1 = 0 (flipped from 1 to 0)
• Position 2: 0 ^ 1 = 1 (flipped from 0 to 1)
• Position 1: 1 ^ 1 = 0 (flipped from 1 to 0)
• Position 0: 0 ^ 1 = 1 (flipped from 0 to 1)

Result: The complement of 10 is 5

Let's verify with another quick example, num = 1:

• Binary: 1 (1 bit needed)
• Mask: (1 << 1) - 1 = 2 - 1 = 1 (binary: 1)
• XOR: 1 ^ 1 = 0
• The complement of 1 is 0 ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(log num), where num is the input integer. This is because the bit_length() method needs to determine the number of bits required to represent num, which takes O(log num) time. The bit shift operation 1 << num.bit_length() and the XOR operation are both O(1) operations on the resulting values.

The space complexity is O(1). The algorithm only uses a constant amount of extra space regardless of the input size. The intermediate calculations (bit length, shifted value, and XOR result) all use fixed space that doesn't scale with the input.

Common Pitfalls

1. Handling Edge Case of num = 0

The most significant pitfall occurs when num = 0. The bit_length() method returns 0 for the input 0, which leads to:

• mask = (1 << 0) - 1 = 1 - 1 = 0
• 0 ^ 0 = 0

This returns 0 as the complement, but intuitively, the complement of 0 should be 1 (flipping the bit 0 gives 1).

Solution: Add a special case check for num = 0:

def findComplement(self, num: int) -> int:
    if num == 0:
        return 1
    mask = (1 << num.bit_length()) - 1
    return num ^ mask

2. Integer Overflow in Other Languages

While Python handles arbitrary-precision integers, in languages like Java or C++, left-shifting can cause integer overflow for large values of num. For example, if num has 31 bits, 1 << 31 might overflow in a 32-bit signed integer.

Solution: Use appropriate data types or alternative approaches:

# Alternative approach using string manipulation (works universally)
def findComplement(self, num: int) -> int:
    binary = bin(num)[2:]  # Get binary string without '0b' prefix
    complement = ''.join('1' if bit == '0' else '0' for bit in binary)
    return int(complement, 2)

3. Misunderstanding the Problem - Leading Zeros

A common misconception is thinking we need to flip ALL 32 bits (or 64 bits) of the integer representation, including leading zeros. This would give incorrect results:

• For num = 5 (binary: 101), if we flip all 32 bits, we'd get a very large negative number
• The problem asks to flip only the significant bits (those needed to represent the number)

Solution: Ensure you're only creating a mask for the actual bit length of the number, not a fixed-width mask:

# WRONG: Using fixed 32-bit mask
# mask = 0xFFFFFFFF  # Don't do this!

# CORRECT: Using dynamic mask based on bit_length
mask = (1 << num.bit_length()) - 1

4. Not Considering Alternative Bit Manipulation Approaches

While the XOR approach is elegant, there's another intuitive approach using the property that num + complement = mask:

Alternative Solution:

def findComplement(self, num: int) -> int:
    # Find the smallest number with all 1s that is >= num
    mask = num
    mask |= mask >> 1
    mask |= mask >> 2
    mask |= mask >> 4
    mask |= mask >> 8
    mask |= mask >> 16
    # Now mask has all bits set up to the highest bit in num
    return mask - num

This approach progressively fills all bits to the right of the highest set bit, creating the appropriate mask without using bit_length().