Raymond's Notebook
日拱一卒无有尽,功不唐捐终入海
位运算

位运算也称bit运算,而bit犹如计算机的血液,在整个互联网世界流淌。

位运算一般分为6类,大致如下表:

符号描述运算规则
&与(AND)两个位都为1时,结果才为1
|或(OR)两个位都为0时,结果才为0
^异或(XOR)两个位相同为0,不同为1
~取反(NOT)取反 0变1,1变0
<<左移各二进位全部左移若干位,高位丢弃,低位补0
>>右移各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移)

位运算是程序设计中对二进制数的一元和二元操作;在许多古老的微处理器上,位运算比加减运算略快,通常位运算比乘除法运算要快很多。在现代架构中,情况并非如此:位运算的运算速度通常与加法运算相同(仍然快于乘法运算)。

在清楚位运算的基本算法后,我们来讲讲如何利用位运算解决一些有趣的问题:

  • 如何不借助第三方库,计算2的n次方?
    2^n 实际上等于将 1 向左移动 n 个bit位。 2^n = 1 << n

  • 一个n位的二进制无符号数字能够表达的最大十进制数是多少?
    当一个n位二进制数,每个bit位是 1 时,其表达的十进制数最大,也就是等于 = 2^n - 1

  • 如何判断一个十进制数是奇数还是偶数?
    二进制数的最后一位是0,代表偶数;最后一位是1,代表奇数;因此将该十进制数与1进行(AND)与运算,由于1的高位全部是0,计算结果相当于截掉了十进制的高位,仅剩下最末一个bit位,判断该位是0或者1,即可判断该十进制数是偶数还是奇数。 因此可以用if ((a & 1) == 0) 代替if (a % 2 == 0)来判断a是不是偶数。

  • 如何计算一个十进制无符号数中,bit位是1的个数?
    这个问题有很多解法,我们今天尝试用位运算来计算1的个数,基本思路是这样,将该十进制数与1进行AND运算,得到最末一个bit位,然后对该值进行累加;然后将该十进制数向右移动1位,丢弃最末已经统计过的bit位,最后循环执行以上操作,直到十进制数等于0;这里有个隐含的定理,就是将一个十进制数不断向右移动,最终结果为0。
    实现代码如下:

    func hammingWeight(num uint32) int {
      var k int
      for num > 0 {
          k = k + int(num & 1)
          num = num >> 1
      }
      return k
    }
  • 如何采用异或运算进行加密和解密?
    XOR运算有如下一个定式:a ^ b ^ b = a ,如果我们将b看作密钥,将该密钥和被加密数据 a进行异或运算,将得到的值传递给对方;对方将所得值与密钥 b 再次进行XOR运算,所得的结果就是最初的被加密值: a 。

  • 给予一串二进制数字,如何获取某N位的值?
    该问题经常用于获取二进制数字中存储的特殊数据,比如在某些bit位存储一些业务数据,在上次博客中提到的分布式id,就需要在int64中存储时间戳,workerid, 机器id等数据。 那么如何获取某N位的二进制数据呢?通常的做法是将该N位通过移位操作移动到最低位,然后用一个低N位全部是1的二进制数与原数字进行AND操作,所得的结果就是某N位二进制数字的值(十进制表示)。那么如何获得N位bit位全部是1的值呢?其实很简单,N个bit能够表示的最大值是 2^n - 1, 当他表示最大值时,每个bit位都是1,因此将一个无符号十进制与 (2^n - 1) 进行AND运算,就可以得到低N位的数值。

  • 如何不使用中间变量交换两个无符号整数值?
    我们知道XOR运算有个定式:a ^ b ^ b = a ,因此实现代码如下:

    func swap(a *uint32, b *uint32) {
      if a != b {
          *a = *a ^ *b
          *b = *a ^ *b
          *a = *b ^ *a
      }
    }