Problem

The complement of an integer is the integer you get when you flip all the 0’s to 1’s and all the 1’s to 0’s in its binary representation.

  • For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer num, return its 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.

Solution

Video Explanation

Here is the video explanation of this problem.

Method 1 - Subtract From Number with All Ones Larger Than Given Number 🏆

100110, its complement is 011001, the sum is 111111. So we only need get the min number large or equal to num with all ones, and then do substraction.

Code

Java
class Solution {
    public int findComplement(int num) {
        int n = 0;
        int i = 0;

        while (n < num) {
            n += Math.pow(2, i);
            i++;
        }

        return n - num;
    }
}

Math.pow is slower, so lets use left shift:

public int findComplement(int num) {
	int n = 0;
	while (n < num) {
		n = (n << 1) | 1;
	}
	return n - num;
}

Method 2 - Use Highest One Bit Set 🏆

Before this method read this - Bitwise Not or Negation of 16 Bit Integer

  1. The flipped version of the original input but
  2. Only flip N bits within the range from LEFTMOST bit of 1 to RIGHTMOST.

Code

Java
public int findComplement(int num) {
	return ~num & ((Integer.highestOneBit(num) << 1) - 1);
}

Dry Run

num =  5 =   0...0101(+)
output = 2 = 0...0010(+) 
num+ans=     0...0111(+)

Make number’s complement:

~5 =         1..1010 (-)（all bits inverse）
  • Now we’ve flipped all the bits but it also flipped previously insignificant bits (0s), so to revert them back to 0s, we need to only keep the significant bits and turn off the insignificant bits
  • This can be done by using mask of 1s having size equal to number of bits in num. This mask is (1 « nBits) - 1
  • This is a standard mask in bit manipulation problems
mask = (Integer.highestOneBit(num) << 1) - 1 = 1000-1=0..0111(+)

~num & mask = (1...1010) & (0...0111) = 0...0010 [Ans]

Variant 1

public int findComplement(int num) {
	var nBits = (int) Math.floor((Math.log(num) / Math.log(2)) + 1);
	var mask = (1 << nBits) - 1;
	return ~num & mask;
}

Method 3 - Using Complement and Adition

To find complement of num = 5 which is 101 in binary. First ~num gives ...11111010 but we only care about the rightmost 3 bits. Then to erase the 1s before 010 we can add 1000

Code

Java
public int findComplement(int num) {
	return ~num + (Integer.highestOneBit(num) << 1);
}

Method 4 - Using Xor between number and all ones

We can also do:

  1. Convert the integer to its binary representation.
  2. Flip all the bits in the binary representation.
  3. Convert the resulting binary string back to an integer.

Code

Java
public class Solution {
    public int findComplement(int num) {
        // Find the number of bits in the given number
        int bitLength = Integer.toBinaryString(num).length();

        // Create a mask with all bits set to 1 of the same length as the binary
        // representation of num
        int mask = (1 << bitLength) - 1;

        // XOR num with the mask to flip all bits
        return num ^ mask;
    }
}