Algorithm_Item_07.md

位运算的刷题之旅（一）：位运算符基础方法

介绍

先说明一下几种位运算符的用法。

符号	描述	运算规则
&	与	两个位都为 1 时，结果才为 1
|	或	两个位都为 0 时，结果才为 0
^	异或	两个位相同时为 0 ，相异为 1
~	取反	0 变 1，1 变 0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补 0
>>	右移	各二进位全部右移若干位，对无符号数，高位补 0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补 0（逻辑右移）

运算性质：

异或的几条性质:

1. 交换律

2. 结合律 (a ^ b ) ^ c == a ^ ( b ^ c )

3. 对于任何数 x，都有 x ^ x = 0，x ^ 0 = x

4. 自反性: a ^ b ^ b = a ^ 0 = a;

举例说明

• & 与运算 两个位都是 1 时，结果才为 1，否则为 0，如

  1 0 0 1 1  &  1 1 0 0 1 = 1 0 0 0 1 
  

• | 或运算 两个位都是 0 时，结果才为 0，否则为 1，如

  1 0 0 1 1  |  1 1 0 0 1  =  1 1 0 1 1 
  

• ^ 异或运算，两个位相同则为 0，不同则为 1，如

  1 0 0 1 1  ^  1 1 0 0 1  =  0 1 0 1 0 
  

• ~ 取反运算，0 则变为 1，1 则变为 0，如

  ~ 1 0 0 1 1 = 0 1 1 0 0
  

• << 左移运算，向左进行移位操作，高位丢弃，低位补 0，如

  int a = 8;
  a << 3;
  移位前：0000 0000 0000 0000 0000 0000 0000 1000
  移位后：0000 0000 0000 0000 0000 0000 0100 0000
  

• >> 右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位,如

  unsigned int a = 8;
  a >> 3;
  移位前：0000 0000 0000 0000 0000 0000 0000 1000
  移位后：0000 0000 0000 0000 0000 0000 0000 0001
  
  int a = -8;
  a >> 3;
  移位前：1111 1111 1111 1111 1111 1111 1111 1000
  移位前：1111 1111 1111 1111 1111 1111 1111 1111
  

常见操作

1. 乘除

数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2

int a = 2;
a >> 1; ---> 1
a << 1; ---> 4

2. 交换两个数

void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

3. 判断奇偶数

if(0 == (a & 1)) {
 //偶数
}

4. 正负交换

int reversal(int a) {
  return ~a + 1;
}

5. 计算位 1 的个数

count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}  

6. 求绝对值

int abs2(int a) {
  int i = a >> 31;
  return ((a^i) - i);
}

7. 清零

如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。

a & 0 = 0;

8. 取一个数的指定位

比如取数 X = 1010 1110 的低 4 位，只需要另找一个数 Y，令Y的低4位为1，其余位为 0，即 Y = 0000 1111，然后将X与Y进行按位与运算（X & Y = 0000 1110）即可得到 X 的指定位。