学会位运算，助力开发高性能

手撕位运算

0x00 -- 位运算概览

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

---

0x01 -- 按位与 &

运算规则：0&0=0 0&1=0 1&1=1

俩位相同为1，否则为0

3&5 = 1
3 0000 0011
5 0000 0101
& 0000 0001

用途

• 清零

如果想将一个单元清0，即让这个数的各个位都为0，就让这个数去与一个各位都为0的数值按位与。结果为0

• 取一个数的指定位

举个🌰:

a = 1010 1110, 取a的低四位。只需要找一个b，把b的低四位设置为1，其余为0，即

b= 0000 1111 .

&= 0000 1110. 就可以得到a的指定部分， 这个过程中b也就是a的（mask）所谓的掩码。

• 判断奇偶

只要根据末尾是0还是1来判断是否是奇偶数。

是0就是偶数，是1就是奇数。因此可以代替if (a % 2) == 0

替换为if(a&1==0)来判断a是否为偶数。

0x02 -- 按位与 ｜

运算规则：0｜0=0 0｜1=1 1｜1=1

只要其中一位是1， 结果就位1.

3|5 = 7
3 0000 0011
5 0000 0101
| 0000 0111

用途

• 用来对一个数据的某些位设置位1

举个🌰:

a = 1010 1110, 设置a的低四位为1。只需要找一个b，把b的低四位设置为1，其余为0，即

b= 0000 1111 .

|= 1010 1111. 就可以得到按位与后的结果，

0x03 -- 按位异或 ^

运算规则：0^0=0 0^1=1 1^0=1 1^1=0

参加元算的俩个数，相同的位为0，不同的位为1；

异或的几条性质:

1. 交换律

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

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

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

用途

• 翻转指定位

  举个🌰:

  a = 1010 1110, 翻转a的低四位。只需要找一个b，把b的低四位设置为1，其余为0，即

  b= 0000 1111 .

  ^= 1010 0001. 就可以得到按位异或后的结果。 就把a的低四位按位翻转了。

• 与0相异或值不变

   1010 1110
   0000 0000
  ^1010 1110
     a 3 0000 0011
     b 4 0000 0100
     a^b 0000 0111 a
     
     b 4 0000 0100
     b^a 0000 0111 a
             0000 0011 b
  

• 交换俩个数

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

0x05 -- 按位取反 ~

运算规则: ~1=0 ~0=1

使a的最低位为0，可以表示为：a & ~1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。因为“ ~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

0x06 -- 左移运算符 <<

使a的最低位为0，可以表示为：a & ~1。~1的值为 1111 1111 1111 1110，再按"与"运算，最低位一定为0。因为“ ~”运算符的优先级比算术运算符、关系运算符、逻辑运算符和其他运算符都高。

0x07 -- 右移运算符 >>

定义：将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。

例如：a=a>>2 将a的二进制位右移2位，左补0 或者 左补1得看被移数是正还是负。

操作数每右移一位，相当于该数除以2。

综合应用

比如有两个int类型变量x、y,首先要求x+y的和，再除以2，但是有可能x+y的结果会超过int的最大表示范围，所以位运算就派上用场啦。

(x&y)+((x^y)>>1);

---

对于一个大于0的整数，判断它是不是2的几次方

`((x&(x-1))==0)&&(x!=0)；

---

求绝对值

int abs( int x ) { 
   int y ; 
   y = x >> 31 ; 
   return (x^y)-y ;        //or: (x+y)^y 
}

---

取模运算，采用位运算实现：

a % (2^n) 等价于 a & (2^n - 1)

---

乘法运算 采用位运算实现

a * (2^n) 等价于 a << n

---

除法运算转化成位运算

a / (2^n) 等价于 a>> n

---

求相反数

(~x+1)

---

a % 2 等价于 a & 1