一． 位操作基础

位运算是指按二进制进行的运算。在系统软件中，常常需要处理二进制位的问题。

C语言提供了6个位操作运算符：与、或、异或、取反、左移和右移。

这些运算符只能用于整型操作数，即只能用于带符号或无符号的char,short,int与long类型

注意以下几点：

  1. 在这6种操作符，只有~取反是单目操作符，其它5种都是双目操作符。
  2. 位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错。
  3. 对于移位操作，在微软的VC6.0和VS2008编译器都是采取算术称位即算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补0即可，但在右移中逻辑移位的高位补0而算术移位的高位是补符号位。如下面代码会输出-4和3。
  1. int a = -15, b = 15;  
  2. printf("%d %d\n", a >> 2, b >> 2); // -4 3

解析：

十进制 二进制 运算 结果
-15 1111 0001 11
11 1100		 -4
15 0000 1111 00
00 0011		 3 
  1. 5>>2 是指将5的二进制右移2位，即0000 0101 变成 0000 0001 变成十进制 1  
  2. 5<<2 是指将5的二进制左移2位，即0000 0101 变成 0001 0100 变成十进制 20

打印二进制数据

为了方便理解写了一个打印二进制

  1. void binDis(int data) {
  2.     int i = 32;
  3.     while (i--)
  4.     {
  5.         if (data & (1 << i)) {
  6.             printf("1");
  7.         }
  8.         else {
  9.             printf("0");
  10.         }
  12.         if (i % 8 == 0) {
  13.             printf(" ");
  14.         }
  15.     }
  16.     printf("\n");
  17. }
  19. int xx = 0xff;
  20. binDis(xx);         // 00000000 00000000 00000000 11111111
  21. xx = xx << 8;
  22. binDis(xx);         // 00000000 00000000 11111111 00000000

二． 常用位操作小技巧

下面对位操作的一些常见应用作个总结，有判断奇偶、交换两数、变换符号及求绝对值。这些小技巧应用易记，应当熟练掌握。

1．判断奇偶

只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。

因此可以用 if ((a & 1) == 0) 代替 if (a % 2 == 0) 来判断a是不是偶数。

下面程序将输出0到100之间的所有奇数。

  1. for(int i = 0; i < 100; i++) {
  2.     if (i & 1) {
  3.         printf("i = %d\n", i);
  4.     }
  5. }

求100以内二的幂数

  1. /*
  2. -128 1000 0001
  4. -2   1111 1110
  5. -    1000 0001
  6. ==============
  7.          1111 1101 反码
  8.          1000 0010 原码
  9. -1   1111 1111 补码 (反码+1)
  10.          1111 1110 反码 -1
  11.          1000 0001 原码 1变0 0变1 符号位不变
  13. -20  1000 0000 0001 0100 原码
  14.          1111 1111 1110 1011 反码
  15.          1111 1111 1110 1100 补码
  17. 2的幂表(n=1-200)2幂表
  18. 2^n   (n=1~500)
  20. 2^1=2
  21. 2^2=4
  22. 2^3=8
  23. 2^4=16
  24. 2^5=32
  25. 2^6=64
  26. 2^7=128
  27. 2^8=256
  29. 2的幂次方
  30. 1    0000 0001
  31. 2    0000 0010
  32. 4    0000 0100
  33. 8    0000 1000
  34. 16   0001 0000
  35. 32   0010 0000
  36. 64   0100 0000
  37. 128  1000 0000
  38. 如果n是2的幂数的话，那么n的二进制形式中只能有一个1存在，而 n-1 则有2的对数个连续的 1；
  39. 所以，判断一个数是否是2的幂数的代码如下：
  41. */
  43. void isPoverOfTwo() {
  44.     for (int i = 2; i < 70; i++) {
  45.         if ((i & (i - 1))==0) { //等于0 就是2幂数
  46.             printf("i = %d\n", i);
  47.         }
  48.         /*
  49.         & 两个位都为1时，结果才为1 ，当 i =2时
  51.         2    0000 0010 
  52.         1    0000 0001 &
  53.         -----------------
  54.              0000 0000    
  55.         3    0000 0011 i=3  
  56.         2    0000 0010 &
  57.         -----------------
  58.              0000 0010 所以3不是
  60.         3    0000 0011 i=4
  61.         4    0000 0100 &
  62.         -----------------
  63.              0000 0000    
  65.         */
  67.     }
  68. }

2．交换两数

  1. //一般写法
  2. void Swap(int &a, int &b)  
  3. {  
  4.     if (a != b)  
  5.     {  
  6.         int c = a;  
  7.         a = b;  
  8.         b = c;  
  9.     }  
  10. }
  12. //位写法
  13. void Swap(int *p1, int *p2)
  14. {
  15.     if (*p1 != *p2) {
  16.         *p1 = *p1 ^ *p2;
  17.         *p2 = *p1 ^ *p2;
  18.         *p1 = *p1 ^ *p2;
  19.     }
  20. }
  22. char *s1 = "Hello";
  23. char *s2 = "World";
  24. printf("%s %s\n", s1, s2);  // Hello World
  25. Swap(&s1, &s2);
  26. printf("%s %s\n", s1, s2);  // World Hello

可以这样理解：

  1. 第一步 a^=b 即a=(a^b);
  2. 第二步 b^=a 即b=b(ab)，由于运算满足交换律，b(ab)=bb^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。
  3. 第三步 a^=b 就是a=ab，由于前面二步可知a=(ab)，b=a，所以a=ab即a=(ab)^a。故a会被赋上b的值。

再来个实例说明下以加深印象。

int a = 13, b = 6;

a的二进制为 13=8+4+1=1101(二进制)

b的二进制为 6=4+2=0110(二进制)

  1. 第一步 a^=b a = 1101 ^ 0110 = 1011;
  2. 第二步 b^=a b = 0110 ^ 1011 = 1101;即b=13
  3. 第三步 a^=b a = 1011 ^ 1101 = 0110;即a=6

3．变换符号

变换符号就是正数变成负数，负数变成正数。

如对于-11和11，可以通过下面的变换方法将-11变成11

1111 0101(二进制) –取反-> 0000 1010(二进制) –加1-> 0000 1011(二进制)

同样可以这样的将11变成-11

0000 1011(二进制) –取反-> 0000 0100(二进制) –加1-> 1111 0101(二进制)

因此变换符号只需要取反后加1即可。

  1. int SignReversal(int a)
  2. {
  3.     return ~a + 1;
  4. }
  7. int aa = 7, bb = -12345;
  8. printf("%d  %d\n", SignReversal(aa), SignReversal(bb));  // -7 12345

4．求绝对值

位操作也可以用来求绝对值，对于负数可以通过对其取反后加1来得到正数。

对-6可以这样： 1111 1010(二进制) –取反->0000 0101(二进制) -加1-> 0000 0110(二进制)来得到6。

因此先移位来取符号位，int i = a >> 31;要注意如果a为正数，i等于0，为负数，i等于-1。

然后对i进行判断——如果i等于0，直接返回

  1. //by MoreWindows( http://blog.csdn.net/MoreWindows )  
  2. int my_abs(int a)  
  3. {  
  4.     int i = a >> 31;  
  5.     return i == 0 ? a : (~a + 1);  
  6. }

现在再分析下。对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值。所以可以对上面代码优化下：

  1. [cpp] view plain copy
  2. //by MoreWindows( http://blog.csdn.net/MoreWindows )  
  3. int my_abs(int a)  
  4. {  
  5.     int i = a >> 31;  
  6.     return ((a ^ i) - i);  
  7. }

注意这种方法没用任何判断表达式，而且有些笔面试题就要求这样做，因此建议读者记住该方法（_讲解过后应该是比较好记了）。