OneCompiler

1009. Complement of Base 10 Integer (Best approach)

1651

Let's break down the bitwiseComplement function in the provided C++ code step by step, explaining the intuition, approach, and a dry run for clarity.

Intuition

The bitwise complement of a number is obtained by flipping its bits: changing every 0 to 1 and every 1 to 0. For example:

  • The bitwise complement of 5 (which is 101 in binary) is 2 (which is 010 in binary).
  • The bitwise complement of 0 is defined as 1 in this function.

Approach

  1. Handle the Special Case: If n is 0, return 1 immediately since the complement of 0 is 1.
  2. Initialize Variables: Use ans to store the result (the complement) and bitPosition to track the current bit position.
  3. Iterate Over Bits: Use a loop to process each bit of n until n becomes 0.
    • For each bit:
      • Compute the complement of the least significant bit (LSB) using the expression ((n & 1) ^ 1).
      • Shift this complemented bit to its correct position using << bitPosition.
      • Use the bitwise OR (|=) to add this bit into the result ans.
    • Right shift n to process the next bit and increment bitPosition.
  4. Return Result: Once all bits are processed, return ans.

Step-by-Step Dry Run

Let’s dry run the function with an example. Consider n = 5.

Binary Representation

  • 5 in binary is 101.

Step-by-Step Execution

  1. Initial State:

    • n = 5 (binary: 101)
    • ans = 0 (binary: 0)
    • bitPosition = 0

  2. First Iteration:

    • Check n > 0: True
    • Compute complement of LSB: ((n & 1) ^ 1)
      • n & 1 gives 1 (LSB of 101),
      • 1 ^ 1 gives 0.
    • Shift left: 0 << 0 gives 0.
    • Update ans: ans |= 0 → ans = 0.
    • Right shift n: n >>= 1 → n = 2 (binary: 10).
    • Increment bitPosition: bitPosition = 1.

  3. Second Iteration:

    • Check n > 0: True
    • Compute complement of LSB: ((n & 1) ^ 1)
      • n & 1 gives 0 (LSB of 10),
      • 0 ^ 1 gives 1.
    • Shift left: 1 << 1 gives 2 (binary: 10).
    • Update ans: ans |= 2 → ans = 2 (binary: 10).
    • Right shift n: n >>= 1 → n = 1 (binary: 1).
    • Increment bitPosition: bitPosition = 2.

  4. Third Iteration:

    • Check n > 0: True
    • Compute complement of LSB: ((n & 1) ^ 1)
      • n & 1 gives 1 (LSB of 1),
      • 1 ^ 1 gives 0.
    • Shift left: 0 << 2 gives 0.
    • Update ans: ans |= 0 → ans = 2.
    • Right shift n: n >>= 1 → n = 0.
    • Increment bitPosition: bitPosition = 3.

  5. Exit Loop:

    • Check n > 0: False (exit loop).

  6. Return Result:

    • Return ans, which is 2.

Conclusion

The function effectively computes the bitwise complement of a given integer by iterating through each bit, flipping it, and reconstructing the result bit by bit. The approach is efficient and straightforward, leveraging bitwise operations for clarity and performance.