
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:
- Computing the binary representation of
num
. - Flipping each bit of this binary representation from
0
to1
or from1
to0
. - 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.
- Its binary representation is
For
num = 1
:- Its binary is
1
. - The complement of
1
is0
.
- Its binary is
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
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:
- Start by assigning the input integer
num
to themask
. - 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.
- This process involves shifting the mask right by 1, 2, 4, 8, and 16 bits successively, each time performing an OR operation with itself.
- This ensures the mask has all bits set to 1 up to the most significant 1 bit in the original number.
- The final result is obtained by performing an XOR (^) between
mask
andnum
, which effectively inverts all bits ofnum
.
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
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.
No comments yet.