每天进步一点点🤏

颠倒二进制位

  • ~2.34K 字

颠倒二进制位

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
颠倒给定的32位无符号整数的二进制位。

示例 1：
输入：n = 43261596
输出：964176192

解释：
整数	二进制
43261596	00000010100101000001111010011100
964176192	00111001011110000010100101000000

示例 2：
输入：n = 2147483644
输出：1073741822

解释：
整数	二进制
2147483644	01111111111111111111111111111100
1073741822	00111111111111111111111111111110

解法1

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
49
50
51
52
53
54
55
56
57
58
59
思路:
颠倒相当于把12345678的顺序变成87654321
使用位运算分治, 12->21,1234->2143->4321,12345678->21436587->43218765->87654321
只要把位置按1->2->4->8->16的顺序交换,就可以获取颠倒的32位二进制数

代码:
/**
 * @param Integer $n
 *
 * @return Integer
 */
function reverseBits($n)
{
    // 第一次换位,奇数位和偶数位交换
    $n = $this->reverseBitsStep($n);
    // 第二次换位,前两位和后两位交换
    $n = $this->reverseBitsStep($n, 2);
    // 第三次换位,前四位和后四位交换
    $n = $this->reverseBitsStep($n, 4);
    // 第四次换位,前八位和后八位交换
    $n = $this->reverseBitsStep($n, 8);

    // 第五次换位,前十六位和后十六位交换,完成翻转
    return $this->reverseBitsStep($n, 16);
}

function reverseBitsStep($n, $m = 1)
{
    switch ($m) {
        case 1:
            // 掩码：01010101010101010101010101010101（二进制）
            $m1 = 0x55555555;
            break;
        case 2:
            // 掩码：00110011001100110011001100110011（二进制）
            $m1 = 0x33333333;
            break;
        case 4:
            // 掩码：00001111000011110000111100001111（二进制）
            $m1 = 0x0f0f0f0f;
            break;
        case 8:
            // 掩码：00000000111111110000000011111111（二进制）
            $m1 = 0x00ff00ff;
            break;
        case 16:
            // 掩码：00000000111111110000000011111111（二进制）
            $m1 = 0x0000ffff;
            break;
    }

    // 以$m=1为例子,相当于$n向右移动一位,并且将偶数位的值保留
    $part1 = ($n >> $m) & $m1;
    // 先保留偶数位的值,在将偶数位的值移动到奇数位
    $part2 = ($n & $m1) << $m;

    // 合并两个部分,达成$m位的换位效果
    return $part1 | $part2;
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
思路:
每次取最后一位数组放到新二进制值的第一位,然后原始值向右移动一位,直到原始值为0

代码:
/**
 * @param Integer $n
 *
 * @return Integer
 */
function reverseBits($n)
{
    // 32位为0的二进制数
    $res = 0x00000000;
    for ($i = 0; $i < 32 && $n > 0; $i++) {
        // $n & 1相当于只取最后一位,<< (32 - $i - 1)表示向左移动
        $res = $res | ($n & 1) << (32 - $i - 1);
        // 向右移动一位,将最后一位挤掉
        $n = $n >> 1;
    }

    return $res;
}