LeetCode’s Number Complement Explained

Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation.

Please try on your own before reading on.

Before solving this problem, we need to understand a few concepts in bitwise manipulation.

XOR (^) Finding the complement of a number:

So, apparently

5 → 101

Complement of 5 → 010

And 101 ^ 010 = 111

Therefore,

A ^ B = C

A ^ A ^ B = A ^ C

0 ^ B = A ^ C

B = A ^ C

B is the complement of A in this case and that is what we want to achieve.

So given N is the input, to find N’s complement, B = N ^ 1111… (as many times as the number of digits in N’s bit representation)

So if N = 5, 5’s bit representation is 101, that’s 3 digits. Therefore to find 5’s complement, we have to 101 ^ 111 = 010 → 2.

Now how do we get the 111…

Get the number of digits in N’s bit representation