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.
1#include <stdio.h>
2
3int bitwiseComplement(int n){
4 if (n == 0) return 1;
5 int mask = 0;
6 unsigned int m = n;
7 while (m) {
8 mask = (mask << 1) | 1;
9 m >>= 1;
10 }
11 return (~n) & mask;
12}
13
14int main() {
15 int n = 5;
16 printf("%d", bitwiseComplement(n));
17 return 0;
18}The function bitwiseComplement checks if the input number is zero, in which case it returns 1 as the complement of 0 is 1. For other numbers, it calculates a mask with all bits set to 1 up to the most significant bit of the number. The complement is then calculated by XORing this mask with the number, flipping all its bits.
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
This C function calculates (2^x - 1) by left-shifting the mask variable until it is larger than n, then uses XOR to find the complement of n. It's a compact design that minimizes operations while still achieving the same result.