位运算的“凶悍”操作

虽然平时很少用到位运算，但是在某些时候，这些小东西确实能给我们提供很巧妙的解决方案。运算速度快，效率极高，超级凶悍。

本文将用几个栗子来说明位运算的简单粗暴之处。

1.一个用&代替%的栗子

假设有一个数，现在需要取这个数所对应的二进制数的后三位：

代码描述为：

int num = 0x9A;
num & 7;

用二进制来分析一下吧：
0000 0000 0000 0000 0000 0000 1001 1010
& 0000 0000 0000 0000 0000 0000 0000 0111
=0000 0000 0000 0000 0000 0000 0000 0010

进一步想：对于num%8，如果站在二进制数角度考虑，和8取余数，其本质就是取出num所对的二进制数的后三位。这意味着：num%8 = num&7 ！

小朋友，你是否有很多问号？
为什么，别人都在用%，而我却要学用&？

/歪头

呐，我们来回顾一下计算机的两类运算：

• 逻辑运算：由于其可以用非常简单、高速的电子电路实现，因此，运算速度非常快。
• 算数运算：算数运算的加、减法运算的电路需要用到“全加器”这样复杂的电路才能实现，运算速度会比位运算低很多，乘、除法运算速度则更低。

所以，如果能将乘除运算改为同等效力的位运算，那么运算速度会得到很大提升哒！

2.关于异或

首先了解异或规则

异或规则：
A       B        A^B
0       0        0
0       1        1
1       0        1
1       1        1

异或加密

明文： 0100 1101
密钥： 1011 1100
经异或加密
密文： 1111 0001

对于密文，用密钥再次进行异或运算

密文： 1111 0001
密钥： 1011 1100
经异或解密
明文： 0100 1101

基于异或的“局部按位取反”

如果异或规则这样写呢：
A        B        A^B
0        0        0
1        0        1

0        1        1
1        1        0

便得结论：A^00…0 => A 、 A^11…1 => !A

举个栗子，对于任意数num（一字节无符号数），希望对N4 N3 N2这三位按位取反，其他位保持不变。

特别提醒：一个字节的每一个位，按照如下顺序命名：
N7 N6 N5 N4 N3 N2 N1 N0

那么要实现上述要求，只要进行如下计算：

N7 N6 N5 N4 N3 N2 N1 N0
^ 0 0 0 1 1 1 0 0

也就是执行：

  num^0x1C

非常简单干净。

3.“凶悍”的宏

置位

解释置位：设置某一个位为1。

现要求实现一个运算，已知num和i，num表示一个一字节数值，i表示这个字节从左向右的第i位，i取值从0到7，要求将num的第i位置位。

先对一个字节的8个位进行排列：
XXXX XXXX
0123 4567

推导过程：

基于位运算 X|0 = X的事实，将有下面操作：
  XXXX XXXX            i
| 0000 0001    1<<0    7     1<<(7-i)   =>XXXX XXX1
  0000 0010    1<<1    6     1<<(7-i)   =>XXXX XX1X
  0000 0100    1<<2    5     1<<(7-i)   =>XXXX X1XX
  0000 1000    1<<3    4     1<<(7-i)   =>XXXX 1XXX 
  0001 0000    1<<4    3     1<<(7-i)   =>XXX1 XXXX
  0010 0000    1<<5    2     1<<(7-i)   =>XX1X XXXX
  0100 0000    1<<6    1     1<<(7-i)   =>X1XX XXXX
  1000 0000    1<<7    0     1<<(7-i)   =>1XXX XXXX

总结得到 num | (1 << (7-i) )，又因为7-i = i^7 (这个自己去推嗷，很简单的)，所以：

//定义置位宏
#define SET(num,n) ((num) | (1 << (i^7)))

清位

解释清位：设置某一个位为0。

现要求实现一个运算，已知num和i，num表示一个一字节数值，i表示这个字节从左向右的第i位，i取值从0到7，要求将num的第i位清位。

推导过程：

基于 X&1 = X 的事实，将有下列操作：
  XXXX XXXX                        i 
& 1111 1110  ~0000 0001  (~1)<<0   7    =>XXXX XXX0
  1111 1101  ~0000 0010  (~1)<<1   6    =>XXXX XX0X
  1111 1011  ~0000 0100  (~1)<<2   5    =>XXXX X0XX
  1111 0111  ~0000 1000  (~1)<<3   4    =>XXXX 0XXX
  1110 1111  ~0001 0000  (~1)<<4   3    =>XXX0 XXXX
  1101 1111  ~0010 0000  (~1)<<5   2    =>XX0X XXXX
  1011 1111  ~0100 0000  (~1)<<6   1    =>X0XX XXXX
  0111 1111  ~1000 0000  (~1)<<7   0    =>0XXX XXXX

总结得到：num&~(1<<(7-i))，又因为7-i=i^7，所以：

//定义清位宏
#define CLR(num,i) ((num) & ~(1<<(i^7)))

取位

解释取位：取出一个字节从左向右第i位上的值。

如一个数num的8位为：abcd efgh
((abcd efgh)>>0) & 0000 0001 => 0000 000h
((abcd efgh)>>1) & 0000 0001 => 0000 000g
((abcd efgh)>>2) & 0000 0001 => 0000 000f
……
((abcd efgh)>>t) & 1

总结： ( (num)>>(i^7) ) & 1

//定义取位宏
#define GET(num,i) (((num)>>(i^7)) & 1)

如果你读到这里不知道这三个宏在干嘛，很正常，因为它在后面才会应用到具体的实例里，使算法得到极大优化，那时才能感受到它的巧妙。

“凶悍”的宏还有后续，下次再更，溜辽……今天的文章位运算的“凶悍”操作分享到此就结束了，感谢您的阅读。