十一、位操作

 

1.位操作基础

基本的位操作符有与、或、异或、取反、左移、右移这6种，它们的运算规则如下：

符号 描 述 运算规则

& 与 两个位都为1时，结果才为1

| 或 两个位都为0时，结果才为0

^ 异或 两个二进数的每一位相同为0，相异为1

~ 取反 0变1，1变0

<< 左移 各二进位全部左移若干位，高位丢弃，低位补0

 右移      各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

Pasted from:
<[http://blog.csdn.net/morewindows/article/details/7354571]{.ul}>

注意一下几点：

1）在这6中操作符，只有~取反是单目操作符，其他5种都是双目操作符

（PS：运算所需[变量]{.ul}为两个的运算符叫做双目运算符·或者要求运算对象的个数是2的运算符称为双目运算符。）

2）位操作只能用于整型数据，对float和double类型进行位操作会被编译器报错

3）对于移位操作，在微软的VC6.0和VS2008编译器都是采取算术称位即算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补0即可，但在右移中逻辑移位的高位补0而算术移位的高位是补符号位。如下面代码会输出-4和3。

  1. int a = -15, b = 15;

  2. printf(“%d %dn”, a >> 2, b >> 2);

因为15=0000 1111（二进制），右移二位，最高位由符号位填充将得到0000
0011，即3， -15 = 1111 0001（二进制）， 右移二位，
最高位由符号位填充将得到1111 1100即-4，即负数在除以2^k^次之后还要-1

4）位操作符的运算优先级比较低，所以尽量使用括号来确保运算顺序，否则很可能会得到莫名其妙的结果。比如要得到像1，3，5，9这些2^i+1的数字。写成int
a = 1 << i + 1;是不对的，程序会先执行i+1，再执行左移操作。应该写成int
a = （1<<i） + 1;

5）另外位操作还有一些复合操作符，如&=、|=、^=、<<=、>>=

2.常用位操作小技巧

1）判断奇偶

只要根据最末位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if((a&1)==0)代替if(a%2
== 0)来判断a是不是偶数

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

  1. for(i = 0; i < 100; ++i)

  2. if(i & 1)

  3. printf(“%d”, i);

  4. putchar(‘n’);

2）交换两数

一般的写法是：

  1. void Swap(int &a, int &b)

  2. {

  3. if(a != b)

  4. {

  5. int c = a;

  6. a = b;

  7. b = c;

  8. }

  9. }

可以用位操作来实现交换两数而不用第三方变量：

  1. void Swap(int &a, int &b)

  2. {

  3. if(a != b)

  4. {

  5. a ^= b;

  6. b ^= a;

  7. a ^= b;

  8. }

  9. }

可以这么理解：

① a^=b即a=(a^b);

② b^=a即b=b^(a^b);
由于^运算满足交换律，b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上a的值

③a^=b就是a=a^b，由于前面二步可知a=(a^b),
b=a，所以a=a^b即a=(a^b)^a。故a会被赋上b的值
再来个示例：int a = 13, b = 6;

a的二进制为1101

b的二进制为110

①a^=b a=
1101^0110=1011;（这个数是一个中间值，ab中任意一个与中间值异或都会变成另外一个）

②b^=a b= 0110^1011= 1101;即b=13

③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 ->
11110101（二进制）

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

  1. int SignReversal(int a)

  2. {

  3. return ~a + 1;

  4. }

4）求绝对值

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

1111 1010（二进制）- 取反 -> 0000 0101（二进制） - 加1 -> 0000
0110（二进制）来得到6

因此先移位来去符号位，int i = a >> 31;
要注意如果a为正数，i等于0，为负数，i等于-1（因为负数右移补的二进制数是1）。然后对i进行判断，如果i等于0，直接返回。否则，返回~a+1

  1. int abs(int a)

  2. {

  3. int i = a >> 31;

  4. return i == 0 ? a : (~a + 1);

  5. }

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

  1. int abs(int a)

  2. {

  3. int i = a >> 31;

  4. return ((a ^ i) - i);

  5. }

3.位操作和空间压缩

1）对一个数二进制码中指定位置放置1

一个整数可以通过将1向左移位后与其相或来达到在指定位置上放置1的效果

  1. int j = 0;

  2. j |= 1 << 10;

  3. printf(“%dn”, j);

2)对一个数二进制码中指定位置判断是1或0

利用指定位置与1相与来判断是否一样

  1. int j = 1 << 10;

  2. if((j & (1 << 10)) != 0)

  3. printf(“指定位上为1”);

  4. else

  5. printf(“指定位上为0”);