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.
1public class Solution {
2 public int bitwiseComplement(int n) {
3 if (n == 0) return 1;
4 int mask = 0;
5 int m = n;
6 while (m != 0) {
7 mask = (mask << 1) | 1;
8 m >>= 1;
9 }
10 return (~n) & mask;
11 }
12
13 public static void main(String[] args) {
14 Solution sol = new Solution();
15 int n = 5;
16 System.out.println(sol.bitwiseComplement(n));
17 }
18}By creating a mask with all bits set to 1, bitwise operations are done against the negation of n to get the complement. This approach efficiently handles the bitwise calculations through shifts and masking.
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 Java implementation uses the approach of identifying the mask via powers of two, then calculating the complement by XORing n against the mask. It minimizes operations to derive the precise mask needed.