Bitwise Operation

Posted on May 22, 2018

在计算机刚出现时的远古年代（其实也就几十年）， CPU ，内存和网络带宽都是非常珍贵的资源，在处理或者发送数据时，为了尽可能地节约资源，程序员都需要尽可能控制数据的大小，例如布尔值能用一个比特表示就绝不使用一个字节。

一般网络协议的头部通过指定特定比特来表示特定的意思，还有在很多 low-level 的系统编程中，位运算也非常常见。所以，位运算可以说是程序员的必备技能了，下面让我们来看几种基本的位运算吧。

type op struct{}

type BitwiseOperation interface {
    AND(byte, byte) byte
    ANDNOT(byte, byte) byte
    OR(byte, byte) byte
    XOR(byte. byte) byte 
    NOT(byte) byte  
    SHIFT_LEFT(byte, uint) byte
    SHIFT_RIGHT(byte, uint) byte
}

& (AND)

AND 运算符可以有选择性地将数的某位清零，除此之外，还可以检测数的奇偶性（1 & a == 1）。

  0xAC // 10101100
& 0xF0 // 11110000
= 0xA0 // 10100000
          ^ ^

1
2
3

func (op *bitwiseOp) AND(x byte, y byte) byte {
    return x & y
}

&^ (AND NOT)

与 AND 类似，AND NOT 也可以将特定的位清0，但是 AND NOT 的语义更加符合正常思维，写起来也更加直观。

   0xAB // 10101011
&^ 0x03 // 00000011
=  0xA8 // 10101000
           ^ ^ ^

1
2
3

func (op *op) ANDNOT(x byte, y byte) byte {
    return x &^ y
}

| (OR)

OR 操作可以有选择性地将一个字节的某几个比特设为1。

  0x00 // 00000000
| 0xC4 // 11000100
= 0xC4 // 11000100
          ^^   ^

1
2
3

func (op *op) OR(x byte, y byte) byte {
    return x | y
}

^ （XOR | NOT）

Binary ^ (XOR)

使用 XOR 可以将位从一个值切换到另一个（toggle），除此之外，XOR 还可以用于比较两个数的符号是否相同。当 (a ^ b) ≥ 0 时，表示两个整数a，b具有相同的符号（或当 (a ^ b) < 0 时表示符号相反）。

  0xCEFF // 1100111011111111
^ 0xFF00 // 1111111100000000
= 0x31FF // 0011000111111111
              ^^   ^^^^^^^^^

1
2
3

func (op *op) XOR(x byte, y byte) byte {
    return x ^ y
}

Unary ^ (NOT)

与其他语言（c / c ++，Java，Python，Javascript等）不同，Go没有专门的取反位运算符，但它可以用 ^ 来表示 NOT，也就是按位取反。

1
2
3

^ 0x0F // 00001111
= 0xF0 // 11110000
          ^^^^

1
2
3

func (op *op) NOT(x byte) byte {
    return ^x
}

SHIFT

Shift 操作可以和 & | &^ 这三个操作符组合起来使用。

a | ( 1<< 2)

| 与 << 运算符组合可以用于设置a中的第n位。

a & (1 << 2)

或者将 ＆ 和 << 运算符组合来测试第n位是否被设置。

a &^ (1 << 2)

使用 ＆^ 和 <<，我们可以取消设置值的第n位。

使用左右移位运算符还可以完成效率更高的乘法和除法。

>> (Shift Right)

     0x78 // 01111000
              ^^^^
>> 1 0x3C // 00111100  
               ^^^^
>> 2 0x1E // 00011110
                ^^^^
>> 3 0x0F // 00001111
                 ^^^^

1
2
3

func (op *op) SHIFT_RIGHT(x byte, n uint) byte {
    return x >> n
}

<< (Shift Left)

     0x03 // 00000011
                   ^^
<< 1 0x60 // 00000110
                  ^^
<< 2 0xC0 // 00001100
                 ^^
<< 3 0x18 // 00011000
                ^^

1
2
3

func (op *op) SHIFT_LEFT(x byte, n uint) byte {
    return x << n
}

bitset

了解了基本的位操作后，我们可以用它来实现 bitset ，使用 bitset 存储布尔值相对 map[uint]bool 来说更加高效。 bitset 可以在很多场景下使用，比方说你是一个旅店老板，就可以使用 bitset 来存储每个房间的状态，如果房间被占用了，则将相应的比特位设置为1，如果房间为空，则相应的比特位设置为0。

uint64
+----------------------------------------------------------------+
|................x................................x..............|
+----------------------------------------------------------------+
uint64
+----------------------------------------------------------------+
|...................................x............................|
+----------------------------------------------------------------+
uint64
+----------------------------------------------------------------+
|...............x................................................|
+----------------------------------------------------------------+
uint64
+----------------------------------------------------------------+
|...................x..........x..........x......................|
+----------------------------------------------------------------+

type bitset []uint64

func newBitset(bits uint) bitset {
    extra := uint(0)
    if bits % 64 != 0 {
        extra = 1
    }
    chunks := bits/64 + extra
    return bitset(make([]uint64, chunks))
}

1
2
3

func bitsetIndex(pos uint) (uint, uint) {
    return pos / 64, pos % 64
}

func (b bitset) set(pos uint) bitset {
    major, minor := bitsetIndex(pos)
    b[major] |= (1 << minor)
    return b
}

func (b bitset) clear(pos uint) bitset {
    major, minor := bitsetIndex(pos)
    b[major] &^= (1 << minor)
    return b
}

func (b bitset) get(pos uint) bool {
    major, minor := bitsetIndex(pos)
    return b[major] & (1 << minor) != 0
}

func (b bitset) popcnt() uint {
    total := uint(0)
    for _, v := range b {
        v = (v&0x5555555555555555) + ((v&0xAAAAAAAAAAAAAAAA) >> 1)
        v = (v&0x3333333333333333) + ((v&0xCCCCCCCCCCCCCCCC) >> 2)
        v = (v&0x0F0F0F0F0F0F0F0F) + ((v&0xF0F0F0F0F0F0F0F0) >> 4)
        v *= 0x0101010101010101
        total += uint((v >> 56) & 0xFF)
    }
    return total
}

func (b bitset) clone() bitset {
    dataCopy := make([]uint64, len(b))
    copy(dataCopy, b)
    return bitset(dataCopy)
}

func (b bitset) hash() uint64 {
    hash := uint64(b.popcnt())
    for _, v := range b {
        hash ^= v
    }
    return hash
}

func (b bitset) equals(b2 bitset) bool {
    if len(b) != len(b2) {
        return false
    }
    for i := range b {
        if b[i] != b2[i] {
            return false
        }
    }
    return true
}