Problem Description

The problem asks you 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:

• The integer 5 has binary representation "101"
• After flipping all bits: 0 becomes 1, 1 becomes 0, 0 becomes 1
• This gives us "010", which equals the integer 2

Given an integer n, you need to return its complement.

The solution works by iterating through each bit of the input number n. For each bit position i:

• It extracts the current bit using n & 1
• Flips it using XOR with 1 (which gives 0 if the bit is 1, and 1 if the bit is 0)
• Places this flipped bit at the correct position in the answer using left shift << i
• Combines it with the existing answer using OR operation |=
• Moves to the next bit by right shifting n by 1

The special case where n = 0 is handled separately, returning 1 since the complement of 0 (all zeros) would be 1 (a single one).

Intuition

To find the complement of a number, we need to flip every bit in its binary representation. The key insight is that we can process the number bit by bit from right to left.

Think about how we normally read binary numbers - each bit position has a specific value (powers of 2). When building the complement, we want to preserve these positions but flip the actual bit values.

The natural approach is to:

1. Look at each bit of the original number
2. Flip it (if it's 1 make it 0, if it's 0 make it 1)
3. Place this flipped bit in the same position in our result

To flip a bit, we can use XOR with 1: bit ^ 1. This works because:

• 0 ^ 1 = 1 (flips 0 to 1)
• 1 ^ 1 = 0 (flips 1 to 0)

We build the answer incrementally by processing one bit at a time. We extract the rightmost bit using n & 1, flip it, then position it correctly in our answer using left shift. After processing each bit, we right shift n to move to the next bit.

The special case of n = 0 needs separate handling because our loop wouldn't execute (since 0 has no 1 bits to process), but we know the complement of 0 should be 1.

This bit-by-bit construction ensures we only flip the bits that actually exist in the original number's representation, avoiding the issue of flipping leading zeros that aren't part of the number.

Solution Approach

The solution uses bit manipulation to construct the complement bit by bit.

First, we handle the edge case: if n is 0, we immediately return 1 since the complement of 0 is 1.

For all other cases, we initialize two variables:

• ans = 0: This will store our final complement value
• i = 0: This tracks the current bit position we're processing

The main algorithm processes n bit by bit using a while loop that continues as long as n is not zero:

1. Extract and flip the current bit: (n & 1 ^ 1)

   • n & 1 extracts the rightmost bit of n
   • ^ 1 flips this bit (XOR with 1 inverts the bit)

2. Position the flipped bit: << i

   • Left shift the flipped bit by i positions to place it at the correct position in the result

3. Add to the answer: ans |= ...

   • Use OR operation to set this bit in our answer

4. Move to the next bit:

   • Increment i to track the next bit position
   • Right shift n by 1 (n >>= 1) to process the next bit

The loop naturally terminates when all bits of n have been processed (when n becomes 0 after all the right shifts).

For example, with n = 5 (binary 101):

• Iteration 1: Process bit 1, flip to 0, place at position 0
• Iteration 2: Process bit 0, flip to 1, place at position 1
• Iteration 3: Process bit 1, flip to 0, place at position 2
• Result: 010 which is 2 in decimal

This approach ensures we only process the actual bits in the number's representation, avoiding issues with leading zeros.

Example Walkthrough

Let's trace through the algorithm with n = 5 (binary: 101).

Initial State:

• n = 5 (binary: 101)
• ans = 0 (binary: 000)
• i = 0

Iteration 1:

• Current rightmost bit of n: n & 1 = 101 & 001 = 1
• Flip the bit: 1 ^ 1 = 0
• Position it: 0 << 0 = 0
• Update answer: ans = 000 | 000 = 000
• Move to next bit: n = 101 >> 1 = 010 (which is 2), i = 1

Iteration 2:

• Current rightmost bit of n: n & 1 = 010 & 001 = 0
• Flip the bit: 0 ^ 1 = 1
• Position it: 1 << 1 = 010
• Update answer: ans = 000 | 010 = 010
• Move to next bit: n = 010 >> 1 = 001 (which is 1), i = 2

Iteration 3:

• Current rightmost bit of n: n & 1 = 001 & 001 = 1
• Flip the bit: 1 ^ 1 = 0
• Position it: 0 << 2 = 000
• Update answer: ans = 010 | 000 = 010
• Move to next bit: n = 001 >> 1 = 000 (which is 0), i = 3

Loop Terminates (n = 0)

Final Result: ans = 010 (binary) = 2 (decimal)

We successfully flipped 101 to 010, converting 5 to its complement 2.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the given decimal number. This is because the while loop iterates through each bit of the number n. Since n is right-shifted by 1 position in each iteration (n >>= 1), the loop runs for the number of bits in n, which is approximately log₂(n) times.

The space complexity is O(1). The algorithm only uses a constant amount of extra space with variables ans and i, regardless of the input size. No additional data structures that scale with input size are used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting the Special Case for n = 0

Issue: Without handling n = 0 separately, the while loop never executes (since the condition n > 0 is false), resulting in returning 0 instead of the correct answer 1.

Incorrect Code:

def bitwiseComplement(self, n: int) -> int:
    result = 0
    bit_position = 0
  
    while n > 0:  # This loop never runs when n = 0
        flipped_bit = (n & 1) ^ 1
        result |= flipped_bit << bit_position
        bit_position += 1
        n >>= 1
  
    return result  # Returns 0 for input 0, but should return 1

Solution: Always check for the edge case where n = 0 at the beginning of the function.

Pitfall 2: Using Fixed-Width Bit Manipulation

Issue: Attempting to use a fixed number of bits (like 32 bits) and XORing with a mask can lead to unnecessary leading 1s in the result.

Incorrect Code:

def bitwiseComplement(self, n: int) -> int:
    # Wrong approach: XOR with all 1s for 32 bits
    return n ^ 0xFFFFFFFF  # This gives wrong answer for small numbers

For n = 5 (binary 101), this would XOR with 11111111111111111111111111111111, giving 11111111111111111111111111111010 instead of just 010.

Solution: Process only the actual bits present in the number by iterating through them, as shown in the correct solution.

Pitfall 3: Incorrect Operator Precedence

Issue: Forgetting that bitwise AND (&) has lower precedence than XOR (^) without parentheses can lead to incorrect bit extraction.

Incorrect Code:

flipped_bit = n & 1 ^ 1  # This is interpreted as n & (1 ^ 1) = n & 0

This evaluates as n & (1 ^ 1) which equals n & 0, always giving 0.

Solution: Use proper parentheses to ensure correct evaluation order:

flipped_bit = (n & 1) ^ 1  # Extract bit first, then flip

Pitfall 4: Using Signed Integer Operations Incorrectly

Issue: In some languages, using the NOT operator (~) directly can cause issues with signed integers, producing negative numbers due to two's complement representation.

Incorrect Code:

def bitwiseComplement(self, n: int) -> int:
    return ~n  # This returns negative numbers in Python

For n = 5, ~5 returns -6 in Python, not 2.

Solution: Build the complement bit by bit, or if using NOT operator, mask the result appropriately to get only the relevant bits.

# Alternative correct approach using mask
def bitwiseComplement(self, n: int) -> int:
    if n == 0:
        return 1
    mask = n
    mask |= mask >> 1
    mask |= mask >> 2
    mask |= mask >> 4
    mask |= mask >> 8
    mask |= mask >> 16
    return n ^ mask