How to Compute the Number Complement for Integers?

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation.

Example 1:
Input: 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: 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.

If we continous divide the number by two and do the modulo (by two as well), we will virtually extract each bit. We then can compute the value of the complement at that bit and add it to the result.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public int findComplement(int num) {
        int r = 0, x = 1;
        while (num > 0) {
            r += (1 - num % 2) * x;
            num /= 2;
            x *= 2;
        }
        return r;
    }
}

class Solution {
    public int findComplement(int num) {
        int r = 0, x = 1;
        while (num > 0) {
            r += (1 - num % 2) * x;
            num /= 2;
            x *= 2;
        }
        return r;
    }
}

We can use the logic AND (&1) to replace the modulo (%2), the XOR i.e. exclusive OR to replace (1 – num % 2), and the logical shift (<<1) to replace the multiplication (*2) for better performance.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public int findComplement(int num) {
        int r = 0, x = 1;
        while (num > 0) {
            r += ((num & 1) ^ 1) * x;
            num /= 2;
            x <<= 1;
        }
        return r;
    }
}

class Solution {
    public int findComplement(int num) {
        int r = 0, x = 1;
        while (num > 0) {
            r += ((num & 1) ^ 1) * x;
            num /= 2;
            x <<= 1;
        }
        return r;
    }
}

In Javascript, we can use toString(2) to get the binary in string, then we can get the array by split(“”). Then we can use the map function to turn each bit (from 0 to 1 and from 1 to 0). Once we have transformed the array, we can join it to a string and convert it to numerical value e.g. the complement by using function parseInt(x, 2) – the binary radix.

1
2
3
4
5
6
7
8

/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    const binary = num.toString(2).split("");
    return parseInt(binary.map( b => b == '0' ? '1' : '0' ).join(""), 2);
};

/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    const binary = num.toString(2).split("");
    return parseInt(binary.map( b => b == '0' ? '1' : '0' ).join(""), 2);
};

Also, we can get the least power-of-two integer e.g. x which is bigger than the input number, then the answer will be x-1-num. For example, when input is “110”, the least power-of-two integer bigger than “110” is “1000”. “1000” – “1” is “111”. And “111” – “110” is the complement, i.e. “001”

1
2
3
4
5
6
7
8
9
10

class Solution {
    public int findComplement(int num) {
        int x = 1, r = num;
        while (r > 0) {
            r /= 2;
            x <<= 1;
        }
        return x - 1 - num;
    }
}

class Solution {
    public int findComplement(int num) {
        int x = 1, r = num;
        while (r > 0) {
            r /= 2;
            x <<= 1;
        }
        return x - 1 - num;
    }
}

In C++, we have many intrinsic functions and the __builtin_clz counts the number of leading zeros. For example, the following 32-bit integer (4 bytes) has 12 leading zeros.

0000 0000 0000 1111 0000 0001 0000 1111

Thus __builtin_clz(x) returns 32.

Now, once we have the number of leading zeors e.g. r, we can get x easily by 2^(32 – r – 1). We need to convert this number to unsigned integer as it may overflow when r = 0 (no leading zeros).

1
2
3
4
5
6
7

class Solution {
public:
    int findComplement(int num) {
        int r = __builtin_clz(num);
        return (unsigned int)(2 << (32 - r - 1)) - 1 - num;
    }
};

class Solution {
public:
    int findComplement(int num) {
        int r = __builtin_clz(num);
        return (unsigned int)(2 << (32 - r - 1)) - 1 - num;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —