Sponsored
Sponsored
This approach involves calculating a mask of the same bit length as the number and then using XOR to flip all the bits. The mask is calculated as a sequence of 1s of the same length as the binary representation of the number. For any number 'n', the mask would be computed as (1 << number_of_bits) - 1.
Time Complexity: O(log(n)) as we are shifting bits for the length of the number.
Space Complexity: O(1) since we are using a constant space.
1def bitwiseComplement(n):
2 if n == 0:
3 return 1
4 mask = 0
5 m = n
6 while m:
7 mask = (mask << 1) | 1
8 m >>= 1
9 return (~n) & mask
10
11print(bitwiseComplement(5))This Python function uses the same approach as previously discussed solutions. A mask of 1s is created, and the complement of n is computed by XOR against this mask.
In this approach, instead of calculating a mask using shifts, we use mathematical expressions. We calculate the highest power of 2 greater than n, subtract 1 to get a mask with all 1s up to the highest bit set in n. This mask is then XORed with n for the result.
Time Complexity: O(log(n)) for shifting mask while determining the next power of 2.
Space Complexity: O(1) as only simple variables are used.
1
The Python function builds the mask by setting a loop condition within power boundaries, performing all computations efficiently through combined mathematical and bitwise logic.