Solution Explanation: Complement of Base 10 Integer

The problem asks to find the complement of a given integer n. The complement is obtained by flipping all the bits in the binary representation of the number (0s become 1s and 1s become 0s). The solution uses bit manipulation for efficient computation.

Approach

The core idea is to iterate through the bits of the input number n and generate the complement bit by bit. Here's a breakdown:

1. Handle the base case: If n is 0, its complement is 1. This is a special case we handle upfront.

2. Iterative bit manipulation: We use a while loop to process the bits of n. Inside the loop:

   • (n & 1) extracts the least significant bit (LSB) of n.
   • (n & 1 ^ 1) XORs the LSB with 1, effectively flipping the bit (0 becomes 1, 1 becomes 0).
   • << i left-shifts the flipped bit by i positions, placing it in its correct position in the result ans.
   • n >>= 1 right-shifts n by 1, discarding the processed LSB and moving to the next bit.
   • i += 1 increments the shift counter i.

3. Return the complement: After the loop completes, ans holds the binary representation of the complement, which is then returned.

Code Explanation (Python)

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1
        ans = i = 0
        while n:
            ans |= ((n & 1 ^ 1) << i)  # Flip bit and place it in ans
            i += 1
            n >>= 1  # Move to next bit
        return ans
 

The Python code directly implements the steps outlined above. The other languages (Java, C++, Go, TypeScript, Rust) follow a very similar structure, adapting the syntax to their respective languages.

Time and Space Complexity

• Time Complexity: O(log n). The while loop iterates once for each bit in the binary representation of n. The number of bits is proportional to log₂(n).
• Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size. We only need a few variables to store the intermediate results (ans, i, n).

Example Walkthrough (n = 5)

Let's trace the execution for n = 5:

1. n is not 0, so the base case is skipped.
2. The binary representation of 5 is 101.
3. The loop iterates three times (number of bits):
   • Iteration 1: n & 1 is 1, n & 1 ^ 1 is 0, 0 << 0 is 0, ans remains 0, n becomes 2.
   • Iteration 2: n & 1 is 0, n & 1 ^ 1 is 1, 1 << 1 is 2, ans becomes 2, n becomes 1.
   • Iteration 3: n & 1 is 1, n & 1 ^ 1 is 0, 0 << 2 is 0, ans remains 2, n becomes 0.
4. The loop terminates, and the function returns ans, which is 2 (the complement of 5).

This example demonstrates how the algorithm efficiently computes the bitwise complement.