Vultr DocsLatest Content

Number Complement

Updated on 04 July, 2025
Number Complement header image

Problem Statement

In digital computing, operations on binary representations of integers are fundamental. A particularly interesting operation is computing the binary complement. Essentially, the binary complement of an integer involves inverting its binary bits; this means transforming every binary '1' into a '0' and vice versa.

For example, consider the integer 5 which in binary form is represented as 101. The complement operation would turn it into 010, which in decimal form translates to 2. Given any integer num, the task is to compute and return its binary complement.

Examples

Example 1

Input:

num = 5

Output:

2

Explanation:

The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2

Input:

num = 1

Output:

0

Explanation:

The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Constraints

  • 1 <= num < 231

Approach and Intuition

To find the complement of an integer num, the process involves:

  1. Computing the binary representation of num.
  2. Flipping each bit of this binary representation from 0 to 1 or from 1 to 0.
  3. Converting the flipped binary back to its decimal form and returning the result.

Let's elaborate on how we can achieve these steps based on the provided examples:

  • For num = 5:

    • Its binary representation is 101.
    • The complement is 010. In decimal, this becomes 2.

  • For num = 1:

    • Its binary is 1.
    • The complement of 1 is 0.

These examples shed light on a specific method:

  • Calculate the number of bits needed to represent num in binary. This affects how much the number is padded before flipping (ensuring leading zeros are accounted for correctly).

  • Invert the bits once you have the full binary representation.

Adhering to these steps ensures correct computational transformation from an integer to its binary complement according to the constraints, which include the numerical limit up to just below (2^{31}).

Solutions

  • Java
java 
class Solution {
  public int bitwiseComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return mask ^ num;
  }
}

The given Java solution computes the bitwise complement of a given integer. This is achieved by inversing each bit of the integer. To determine the bitwise complement efficiently, the solution involves creating a mask that contains the same number of high-order bits as the binary representation of the original number.

Here's how the code achieves this:

  1. Start by assigning the input integer num to the mask.
  2. Next, a series of bitwise or (|) and right shift (>>) operations are used to ensure that all bits less significant than the highest significant ‘1’ are set to '1' in the mask.
  3. This process involves shifting the mask right by 1, 2, 4, 8, and 16 bits successively, each time performing an OR operation with itself.
  4. This ensures the mask has all bits set to 1 up to the most significant 1 bit in the original number.
  5. The final result is obtained by performing an XOR (^) between mask and num, which effectively inverts all bits of num.

The approach leverages bitwise operations to efficiently calculate the result without the need for looping through individual bits. This optimized method ensures that the complement is calculated in a time complexity that is dependent on the bit length of the input number, making it suitable for large integers.

  • Python
python 
class Solution:
    def computeComplement(self, number):
        mask = number
        mask |= (mask >> 1)
        mask |= (mask >> 2)
        mask |= (mask >> 4)
        mask |= (mask >> 8)
        mask |= (mask >> 16)
        return mask ^ number

In the given Python script, the function computeComplement calculates the bitwise complement of an integer. This method involves creating a mask that contains all bits set to 1 up to the most significant bit of the original number. This is achieved through a series of bitwise shifts and OR operations that progressively populate the mask. Finally, compute the complement by performing a bitwise XOR between the mask and the original number. The logic ensures that every bit of the number is flipped, effectively yielding the complement in a binary sense. This technique efficiently handles integers by adjusting the mask to the exact length of significant bits in the number.

Comments

No comments yet.