如何读懂位运算

[plh97]

经常碰到下面代码感觉无从读起

写一个函数, 将 010101 => 1010101, 二进制 0 -> 1

func bitwiseComplement(N int) int {
    x := N
    x |= 1
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    return x ^ N
}

上面代码比较抽象, 就和我刚学正则似的.实际上上面语言虽然是用golang写的, 但是就算换成熟悉的JavaScript也还是读不懂, 因为涉及了同一行超过两次位运算.

各种位运算一览表

a=01  b = 11    // 二进制
a&b   => 01 
a|b   => 11
a^b   => 10  
~a    => 10
a<<2  => 100
1111 >> 2  => 0011   // 逻辑右移
1111 >>> 2 => 1111   // 算术右移

如何不引入第三个变量的情况下交换两个变量

相关位运算的交换定律以及其他规则引入

a^(b^c) === (a^b)^c
b^b^b === b^(b^b) === b^0 === b

a = a^b
b = a^b
a = a^b

因为 a = a^b,

所以第二行 b=a^b 相当于, b = (a^b)^b => b = a^(b^b) => b = a^0=> b = a

第三行分别将上面两个变量替换 a = a^b => a = (a^b)^b => a = a^(b^b) => a=b^(b^b) =>a=b^0

ok 回到最初那题

func bitwiseComplement(N int) int {
    x := N
    x |= 1
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    return x ^ N
}

思路就是任何一个数 1100 ^ 1111 就能翻转自身01了, 那么要如何找到和1100 长度一样的1111呢.下面代码负责做到这一点.

    x := N
    x |= 1         // 1100  => 1101
    x |= x >> 1    // 1101  => 1101 | 0110 => 1111
    x |= x >> 2    // 1111  => 1111 | 0011 => 1111
    x |= x >> 4    // 1111  => 1111 | 0000 => 1111
    x |= x >> 8
    x |= x >> 16

为什么不需要 x |= x >> 3呢

因为>> + | 自身 实际上是以2的倍数扩张.

1000000000001
1100000000001
1111000000001
1111111100001
1111111111111