Code Implementation

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1
        mask = 0
        temp = n
        while temp > 0:
            mask = (mask << 1) | 1
            temp >>= 1
        return n ^ mask
      

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n == 0) return 1;
        int mask = 0, temp = n;
        while (temp > 0) {
            mask = (mask << 1) | 1;
            temp >>= 1;
        }
        return n ^ mask;
    }
};
      

class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) return 1;
        int mask = 0, temp = n;
        while (temp > 0) {
            mask = (mask << 1) | 1;
            temp >>= 1;
        }
        return n ^ mask;
    }
}
      

var bitwiseComplement = function(n) {
    if (n === 0) return 1;
    let mask = 0, temp = n;
    while (temp > 0) {
        mask = (mask << 1) | 1;
        temp >>= 1;
    }
    return n ^ mask;
};
      

Problem Description

Given a non-negative integer n, return the complement of its base-10 representation. The complement of an integer is created by flipping all the bits in its binary representation (turning 0s into 1s and 1s into 0s), but only considering the bits up to the most significant 1. For example, the complement of 5 (which is 101 in binary) is 010 (which is 2 in decimal).

• Input: A single non-negative integer n.
• Output: The base-10 integer that results from flipping all bits of n up to its highest set bit.
• Constraints: 0 <= n <= 10^9
• There is always exactly one valid complement for each input.

Thought Process

At first glance, this problem seems to ask us to simply flip all bits of a number. However, in most programming languages, flipping all bits (using the bitwise NOT operator ~) affects all 32 or 64 bits, not just the bits used by n. We only want to flip the bits up to the most significant 1 in n's binary representation.

For example, for n = 5 (101 in binary), flipping all bits in a 32-bit integer would result in a large negative number, but we only want 010 (which is 2). So, we need a way to create a mask that covers just the bits in n.

The brute-force approach would be to convert n to a binary string, flip each bit, and convert back to decimal. But this involves string manipulation and is less efficient. A more optimal approach is to use bitwise operations to construct the mask and perform the flip.

Solution Approach

Let's break down the steps to solve this problem efficiently using bitwise operations:

1. Handle the special case: If n is 0, its binary representation is 0, and its complement should be 1.
2. Build a mask: We want a mask that has the same number of bits as n, all set to 1. For example, if n = 5 (101), the mask should be 111 (which is 7).
   • Start with mask = 0 and temp = n.
   • While temp > 0, shift mask left by 1 and add 1 (mask = (mask << 1) | 1), and shift temp right by 1 (temp >>= 1).
   • This loop continues until temp becomes 0, at which point mask will have all bits set to 1 up to the highest bit of n.
3. Flip the bits: Use XOR (^) between n and mask to flip just the bits we care about.
   • For example, n = 5 (101) and mask = 7 (111), so 5 ^ 7 = 2.
4. Return the result: The result of n ^ mask is the complement we want.

This approach uses only bitwise operations and a simple loop, making it efficient and easy to implement in any language.

Example Walkthrough

Let's walk through an example with n = 10:

• Step 1: n = 10 in binary is 1010.
• Step 2: Build the mask:
  • temp = 10, mask = 0 → mask = 1, temp = 5
  • temp = 5, mask = 1 → mask = 3, temp = 2
  • temp = 2, mask = 3 → mask = 7, temp = 1
  • temp = 1, mask = 7 → mask = 15, temp = 0
  Now, mask = 15 (1111 in binary).
• Step 3: Compute n ^ mask:
  • 10 ^ 15 = 5
  • In binary: 1010 ^ 1111 = 0101 (which is 5)
• Result: The complement of 10 is 5.

Time and Space Complexity

• Brute-force approach:
  • Convert n to a binary string, flip each bit, and convert back.
  • Time complexity: O(k), where k is the number of bits in n (up to 32 for 32-bit integers).
  • Space complexity: O(k), for the binary string and flipped result.
• Optimized bitwise approach (this solution):
  • Building the mask takes O(k) time, where k is the number of bits in n.
  • Space complexity is O(1), since we only use a few integer variables.
  • For all practical purposes, this is extremely efficient since k is at most 32 or 64.

Summary

To find the complement of a base-10 integer, we focus on flipping only the bits up to the most significant 1. The key insight is to construct a bitmask that matches the length of n's binary representation and use XOR to flip the relevant bits. This approach is both efficient and elegant, relying solely on bitwise operations and a simple loop. It avoids unnecessary string manipulation and works in constant space, making it suitable for large inputs.