关于C/C++中的位运算技巧

本篇文章讲述在学习CSAPP位运算LAB时的一些心得。

1. 移位运算的小技巧

C/C++对于移位运算具有不同的策略，对于无符号数，左右移位为逻辑移位，也就是直接移位；对于有符号数，采用算术移位的方式，即左移仍为直接移位，右移时新产生的位用符号位补足。这种设计的目的是保证右移永远代表除以二，在不考虑溢出的情况下，左移永远代表乘以二；这里涉及到的一个规律是，二进制负数的左侧实际上有无数个1；二进制正数的左侧实际上有无数个0；

此外，当移位的长度大于等于数据的位数时，如果使用一个变量来代表移动的位数，则编译器会放弃这一移位操作；如果使用一个立即数作为移动的位数，则编译器会移动到底。

利用算术移位的特性，可以非常简单的实现一些功能，例如，检测一个数字是否可以被n位二进制表示成补码（这不仅仅要求长度要小于n，更要求表示之后的数字大小不能发生变化，如果原本是一个正数，表示之后的符号位必须仍然保持是0）：

例一：检测一个整型数是否能够被n位二进制数表示

1. intfitsBits(intx,intn) {
2. intr, c;
3. c = 33 + ~n;//c = 33 + ~n = 33 + (-n - 1) = 32 - n
4. r = !(((x << c) >> c) ^ x);
5. returnr;
6. }
   通过左移相应的位数再移回来看是否发生改变，就能很容易的知道这个数字能否被n位二进制补码表示。这里涉及到的一个规律是，二进制负数的左侧实际上有无数个1。简单考虑一个四位数字0011，显然其不能被2位数字表示但能被3位数字表示，当左移两位再移回来时，由于第二位的1左移后变成了符号位，结果应该是1111，而左移一位在移回来时仍然是0011。

这种方案也可以应用在右移当中用于查看是否发生了舍弃末尾。

例二：位运算实现除以2的n次幂：

1. intdivpwr2(intx,intn) {
2. return((x >> 31) & !!(x ^ ((x >> n) << n))) + (x >> n);
3. }
   对于正数，位运算实现除以二的n次幂非常简单，只需要单纯的移位即可；但是对于负数情况则略有不同，例如对于-7 = 1001b，其右移一位的结果是-4 = 1100b；然而实际上结果应该是-3；这是由于移位时末尾被舍去了导致的。也就是说，通过位运算实现的除法永远是向下取整，然而除法的规则应该是对于正数向下取整而对于负数则要向上取整，因此这里采用(x ^ ((x >> n) << n))的方式检测是否有某些数字在移位的过程中被忽略，也就是是否不能整除，如果不能整除则进行加一操作；这里还使用了两次！！操作，是利用了逻辑非的缩位特性实现的。

此外，当我们无法得到0xFFFFFFFF时，也可以利用移位运算生成一个全1数字，((1 << 31) >> 31)；

2. ！运算的缩位特性

！x = 1当且仅当x=0；否则x = 1；因此可以使用！！x直接实现缩位或的效果。

1. intbang(intx) {
2. return(~((x >> 31) | (((~x) + 1) >> 31))) & 1;
3. }
   bang函数通过不含！的运算实现了！操作，从中可以更好的体现出它的缩位特性。

3. 分组运算的技巧（二分——组合）

对于每个数据类型进行的操作是和数据的长度相关的。然而，当我们了解了很多关于数据类型的知识后，我们可以更好的利用运算的特性来加速，例如下面这一问题——不使用循环和条件语句统计一个二进制数中1的个数：

最直观的想法其实就是，左移一位后检查末尾是否为1，如果是的话总数就加一，重复31次；然而由于题目中限制不能用循环，如果只是简单的拆成很多条语句显然是很滑稽的。这时候可以考虑分组运算，例如下面的算法以四个为一组，分别统计出来个数，再进行加和。

1. intbitCount(intx) {
2. inta = 0x11 | (0x11 << 8);
3. intb = a | (a << 16);
4. intsum = x & b;
5. sum = sum + ((x >> 1) & b);
6. sum = sum + ((x >> 2) & b);
7. sum = sum + ((x >> 3) & b);
8. sum = sum + (sum >> 16);
9. a = 0xF | (0xF << 8);
10. sum = (sum & a) + ((sum >> 4) & a);
11. return((sum + (sum >> 8)) & 0x3F);
12. }
    在加和时实际上也采用了分组的技巧，这种类似于分治的思想成功地把一个O(n)的问题简化为了O(logn)的问题。

此外还有一例，用单纯的逻辑运算和+实现logn：

实际上我们是要找到最高位的1所在的位置即可，所以这是一个搜索问题，对于位运算，除了最简单的线性搜索之外，比较容易实现的方法就是二分搜索。把二分搜索的方法应用到位运算中，并且注意这里边始终是优先取高位（因为qr是使用高位得到的），经过5次一定能找到结果。

1. intilog2(intx) {
2. intexp = 0;
3. intcx = x;
4. intrx = x >> 16;
5. intqr = (!!rx);
6. qr = (qr << 31) >> 31;
7. rx = (qr & rx) | ((~qr) & cx);
8. exp = exp + ((qr & 16) | (~qr & 0));
10. cx = rx;
11. rx = rx >> 8;
12. qr = (!!rx);
13. qr = (qr << 31) >> 31;
14. rx = (qr & rx) | (~qr & cx);
15. exp = exp + ((qr & 8) | (~qr & 0));
17. cx = rx;
18. rx = rx >> 4;
19. qr = (!!rx);
20. qr = (qr << 31) >> 31;
21. rx = (qr & rx) | (~qr & cx);
22. exp = exp + ((qr & 4) | (~qr & 0));
24. cx = rx;
25. rx = rx >> 2;
26. qr = (!!rx);
27. qr = (qr << 31) >> 31;
28. rx = (qr & rx) | (~qr & cx);
29. exp = exp + ((qr & 2) | (~qr & 0));
31. cx = rx;
32. rx = rx >> 1;
33. qr = (!!rx);
34. qr = (qr << 31) >> 31;
35. rx = (qr & rx >> 1) | (~qr & cx);
36. exp = exp + ((qr & 1) | (~qr & 0));
37. returnexp;
38. }
    原文链接: https://www.cnblogs.com/shawnChi/p/5952045.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍