每天进步一点点🤏

数字的补数

  • 1326 字

数字的补数

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
对整数的二进制表示取反（0 变 1 ,1 变 0）后,再转换为十进制表示,可以得到这个整数的补数
例如,整数 5 的二进制表示是 "101" ,取反后得到 "010" ,再转回十进制表示得到补数 2 
给你一个整数 num ,输出它的补数

示例 1：
输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位）,其补数为 010。所以你需要输出 2

示例 2：
输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位）,其补数为 0。所以你需要输出 0

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
思路:
循环num 除以2取余数,余数为0对应的补数是1,根据除以2的次数作为2的次方
累加每次结果得到答案

代码:
/**
 * @param Integer $num
 *
 * @return Integer
 */
function findComplement($num)
{
    $res = 0;
    $i   = 0;
    while ($num) {
        $mod = $num % 2;

        if ($mod === 0) {
            // 取模=0则补位数=1,$i是除以2的次数
            $res |= 1 << $i;
        }
        $i++;

        $num = intdiv($num, 2);
    }

    return $res;
}

进阶:获取到num位数的掩码,在使用异或运算
/**
 * @param Integer $num
 *
 * @return Integer
 */
function findComplement($num)
{
    // 相当于取最高位以下全是1的掩码
    $n = $num;//1000 0000 0000 0000 0000 0000 0000 0000
    $n |= $n >> 1;//1100 0000 0000 0000 0000 0000 0000 0000
    $n |= $n >> 2;//1111 0000 0000 0000 0000 0000 0000 0000
    $n |= $n >> 4;//1111 1111 0000 0000 0000 0000 0000 0000
    $n |= $n >> 8;//1111 1111 1111 1111 0000 0000 0000 0000
    $n |= $n >> 16;//1111 1111 1111 1111 1111 1111 1111 1111

    // 异或位运算
    return $n ^ $num;
}