稍微介绍一点背景
现代的二进制计数系统最早由戈特弗里德·莱布尼茨于1679年设计,由约翰·冯·诺伊曼首次提出在计算机中应用。
而二进制在物理的实现上相比较其它进制在当时有着得天独厚的优势,所以一直沿用至今。其实前苏联人提出过更加高效的三进制计算机Сетунь,但由于历史原因没有被广泛应用,这里也不再进行讨论了,有兴趣的读者可以自行搜索阅读。
本文就重点讨论一下在现代传统计算机中二进制位运算在程序设计中的应用。
为什么要用位运算?
位运算很快。
这需要我们比高级程序语言更低级的地方去思考——汇编语言乃至计算机硬件层次去思考。
如果我们想将该一个有符号整型在数值上乘2,我们有两种选择:
1.调用SHL(逻辑左移)指令
2.调用乘法器
有电路基础的同学一定很清楚,这两者在实现所需要的逻辑门数量上截然不同,后者的复杂度比前者高上了不少。一般情况下,位运算只消耗一个时钟周期,而乘法运算需要消耗3~4个时钟周期。也就很自然的体现了位运算的优势了。
同时,位运算也可以用来压缩内存,降低代码空间复杂度。
这里悄咪咪地给大家安利一本科普读物——《程序是怎样跑起来的》,讲的比较基础,也比较形象。某宝上购买的价格也不是很高。
位运算具体运用实例
乘2除2
int x = 1; x<<1; x>>1;
其实很好理解,但这里更准确的来说应该是整除2,因为奇数的二进制补码表示中末尾一定是1,在逻辑右移的过程中一定会丢失最后一位,这也就造成了得到的结果是整除。
swap(a,b)
a = a ^ b;
b = a ^ b;
a = a ^ b;
abs(x)
int y = x>>31;
return (x+y)^y; //注意,这里只针对32位整型
max(a,b)
int m = (x-y)>>31;
return y&m|x&~m;
average(a,b)
(x&y) + ((x^y)>>1)
判断是否是2的n次幂
x & (x-1) //是则值为0
判断奇偶性
x&1
判断是否相等
!(a^b)
将二进制最后一个0置1
l |= l + 1;
判断是否同号
!((a^b)>>31) //同样只针对32位整型
位压缩
a>>k&1 //读取第 k 位:
~a>>k&1 //读取第 k 位并取反
a &= ~(1<<k) //将第 k 位清 0
a |= 1<<k //将第 k 位置 1
a ^= 1<<k //将第 k 位取反
a ^= ((1<<(k2-k1+1))-1)<<k2 //将第 k1~k2 位反转
!(x&(x-1))&&x //是否恰好只有一个 true
x>>1&x //判断是否有两个相邻的 true
x>>1&x>>2&x //是否有三个相邻的 true
返回从后往前数,到第一个1出现为止的数(二进制下)
i&-i
值得注意的是,由于位运算的运算优先级比较低,最好在实际应用过程中多加几个括号来保证代码不会出错。
参考资料:
- 《骗分导论》——NOI2009河北省代表队论文 李博杰
- 维基百科 https://zh.wikipedia.org/wiki/%E4%BA%8C%E8%BF%9B%E5%88%B6\
- 逻辑左移、逻辑右移、算术左移、算术右移、循环左移、循环右移