How to Compute the Number Complement for Integers?

  • 时间:2020-10-05 13:36:40
  • 分类:网络文摘
  • 阅读:103 次

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) —

推荐阅读:
已知圆面积求阴影部分的面积  整个路程是多少km  箕子碑原文及翻译  桐叶封弟辨原文及翻译  驳复仇议原文及翻译  柳子厚墓志铭原文及翻译  祭鳄鱼文原文及翻译  《古文观止》中十大经典金句—人生的行动指南  祭十二郎文原文及翻译  送温处士赴河阳军序原文及翻译 
评论列表
添加评论