Documentation for Bitwise Complement Function

Intuition

The goal of the bitwiseComplement function is to compute the bitwise complement of a given non-negative integer n. The bitwise complement of a number is obtained by flipping all the bits in its binary representation. For example:

• The binary representation of 5 is 101. Its complement would be 010, which is 2.
• The binary representation of 0 is an edge case, and its complement is defined as 1.

Approach

To achieve the bitwise complement, the function:

1. Handles the special case where n is 0, returning 1, since the binary representation is 0 and its complement is 1.
2. Iteratively divides n by 2 to retrieve its binary digits using modulus to find the remainder (rem).
3. For each bit, it computes its complement (using XOR with 1, i.e., rem ^ 1) and accumulates the result into ans by converting the position of the bit back into decimal using powers of 2.
4. Finally, it returns the accumulated result, which represents the bitwise complement of n.

Step-by-Step Dry Run

Consider an example where n = 5.

Initialization

• rem: To hold the current bit
• ans: To accumulate the result (initialized to 0)
• i: To keep track of the current bit position (initialized to 0)

Handling Special Case

1. Check if n == 0:
   • If true, return 1. (In this case n is not 0.)

While Loop Execution

Now, we enter the while loop since n is not 0.
The loop continues until n becomes 0.

First Iteration

• Current n: 5 (binary 101)
• Calculate rem: 5 % 2 = 1 (this is the least significant bit (LSB))
• Compute complement: rem ^ 1 = 0
• Update ans: ans = ans + (0) * pow(2, 0) = 0
• Update n: n /= 2 => n = 2
• Increment i: i = 1

Second Iteration

• Current n: 2 (binary 10)
• Calculate rem: 2 % 2 = 0
• Compute complement: rem ^ 1 = 1
• Update ans: ans = 0 + (1) * pow(2, 1) = 2
• Update n: n /= 2 => n = 1
• Increment i: i = 2

Third Iteration

• Current n: 1 (binary 1)
• Calculate rem: 1 % 2 = 1
• Compute complement: rem ^ 1 = 0
• Update ans: ans = 2 + (0) * pow(2, 2) = 2
• Update n: n /= 2 => n = 0
• Increment i: i = 3

Exit Loop

The loop exits as n is now 0.

Final Output

The function returns the value of ans, which is 2. This result is the bitwise complement of 5.

Additional Notes

• The use of pow(2, i) can be replaced with bit shifting for better efficiency.
• The overall time complexity is O(log n), as it processes each bit.
• The space complexity is O(1), using only a fixed amount of space for variables.

Code

class Solution {
public:
    int bitwiseComplement(int n) {
        
        int rem, ans=0,i=0;

        if(n==0)
            return 1;

        while(n){
         
            rem = n % 2;
            ans = ans + (rem ^ 1) * pow(2, i);
            i++;
            n /= 2;

        }

        return ans;
    }
};

This documentation can serve as a reference for understanding how the bitwiseComplement function operates, enabling you to recall its functionality and logic in the future.