Usage of bit operation

位运算的用法

除了逻辑运算，位运算也是编程中常用的运算，但是很多人对于位运算知之甚少。一个原因是因为位运算的用法很零碎，并且有的用法涉及计算机底层的原理所以理解起来比较困难。但是位运算是效率很高的一种运算，特别是在编写单片机的程序时，活用位运算可以节约内存资源和单片机有限的算力。

位运算的定义

1. 按位与（&）

   与字面意思一样，就是将两个二进制数（计算机内存储都是二进制）对应的每一位做与运算

   如：01001101 & 11010011 = 01000001

2. 按位或（|）

   与字面意思一样，就是将两个二进制数对应的每一位做或运算

   如：00110101 | 01010010 = 01110111

3. 按位异或（^）

   与字面意思一样，就是将两个二进制数对应的每一位做异或¹运算

   如：01001110 ^ 00111100 = 01110010

4. 取反（~）

   取反运算是将原来是0的变为1，原来是1的变为0

   如：~010100111 = 101011000

5. 左移（<<）

   左移运算是将原来的数整体向左移动指定位数

   如：11000111 << 1 = 10001110

6. 右移（>>）

   左移运算是将原来的数整体向右移动指定位数

   如：10101011 >> 1 = 01010101

Tips:“&”是偏向于0的，因此常用于置零操作；“|”是偏向于1的，因此常用于置1操作；“^”常用于检测异同；“<<"和“>>”常用于乘除。

位运算的一些性质

1. 与“1”的不变性

   1&1=1 0&1=0

   从上面的两个式子我们可以看出某一位“与”上1，其结果只取决于这一位，即保留了原来的性质

2. 或“0”的不变性

   1|0=1 0|0=0

   从上面的两个式子我们可以看出某一位“或”上1，其结果只取决于这一位，即保留了原来的性质

3. 与“0” = 清零

   1&0=0 0&0=0

   显而易见某一位“与”上0一定为0

4. 或“1” = 置1

   1|1=1 0|1=1

   显而易见某一位“或”上0一定为0

5. 异或“1”的取反性

   0^1=1 1^1=0

   从上面的两个式子我们可以看出某一位“异或”上1，其结果与原来相反

6. 异或“0”的不变性

   0^0=0 1^0=1

   从上面的两个式子我们可以看出某一位“异或”上0，其结果与原来相同

位运算的用法

• 快速乘除2的幂

  由于移位运算的的特点，我们可以发现左移1位的效果就是乘以二，下面给出简单的证明

  $$suppose\quad (x)_{2}=a_{1}a{2}\dots a_{n}=1*a_{n}+2*a_{n-1}+\dots +2^{n-1}a_{1}\\ x<<1=a_{1}a{2}\dots a_{n}0=2*a_{n}+4*a_{n-1}+\dots +2^{n}a_{1}\\ \therefore x<<1=2*x$$

  同理右移1位就是除二，但是这里是整除，因为右移会丢弃最后一位，即奇数会丢失1然后除以二；偶数则是直接除以二。

  移位操作并不局限于乘除2的幂，对于乘法运算，完全可以通过2的幂来组合，如3*x=x<<1+x，不过这样还需要先求乘数的二进制数，反而没有直接计算来的方便。

• 判断一个数的奇偶性

  由于二进制数的特点，奇偶性在二进制数中体现在最后一位是否为1，因此我们可以通过位运算来判断

  $$x\&(1)= 1 \Rightarrow x为奇数\\ x\&(1)= 0 \Rightarrow x为偶数$$

• 判断两个数是否相同

  由异或运算的定义，a^b==0则a与b 相同，反则不同

• 取反第n位

  由位运算的性质，我们可以知道一定要用异或操作，并且我们需要构造一个数，它的第n位为1，其余位为0，那么某个数与它异或后只会取反第n位，所以

  ​

• 置零第n位

  由位运算的性质，我们可以知道一定要用与操作，并且我们要构造一个数，它的第n位是0，其余位是1，那么某个数与它与之后只会置零第n位，所以

  ​

  一般的，置零x的第$a_{1},a_{2}\dots,a_{n}$位 = x&$((~0)$^$((1<<a_{1})+(1<<a_{2})+\dots +(a<<a_{n})))$

• 置1第n位

  与置零类似，这次我们需要用到或操作，并且我们要构造一个数，它的第n位是1，其余位是0，那么某个数与它与之后只会把第n位置1，所以

  ​

  一般的，置1 x的第$a_{1},a_{2}\dots,a_{n}$位 = x|$((1<<a_{1})+(1<<a_{2})+\dots +(a<<a_{n}))$

• 交换两个数

  ​

  第一次取异或后，a保存了a与b每一位的情况，相同的为0，不同的为1；第二次异或时，根据位运算的性质，结果保留了b中与a相同的位，不同的取反，所以b的值变成了a，第三次情况与第二次相同，最后a与b实现了交换。

  ​

  词表达式一步到位，根据右结合的规则不难理解，但是需要指出的是这种方法反而比传统的交换（借助第三变量）效率更低，我们可以通过下面的测试看到其中的原因。

  #include <iostream>
    
  int main()
    {
    	int a = 34, b = 165;
    	a = a ^ b;
    	b = b ^ a;
    	a = a ^ b;
    	printf("%d %d", a, b);
    }

我调试上面的代码并查看反汇编可以看到异或交换进行了六次读写三次异或

但是传统的代码如下，通过反汇编窗口我们发现传统方法只用了六次读写，当然要更快一些。

#include <iostream>
  
int main()
  {
  	int a = 34, b = 165;
  	int temp = a;
  	a = b;
  	b = temp;
  	printf("%d %d", a, b);
  }

当然情况也会因为平台有所差别，上述测试均在VS2017上进行，本人也试过DEV，结果异或交换只要三次读写三次异或，而传统交换需要六次读写，所以，总的来说传统方法还是效率更高，至少也会比异或交换差。

此处顺便提一下另一种不借助第三个变量交换两个值的方法：

​

自行体会，不做解释（懒）

• 取相反数

  由原码和补码的关系我们可以知道

  ​

• 保留第n位，清零其他位

  根据性质，我应该用“&”运算，并且需要构造一个数，它的第n位是1，它的其余位是0

  ​

• 求十进制数的二进制

  因为计算机内存储的都是二进制，所以我们只要将它打印出来就行，通过x&1可以判断x的最后一位是1还是零，只要我们写个循环，每次右移1然后判断最后一位是什么，把结果存入栈，最后从栈中输出就得到了十进制数的二进制形式，或者从高位开始遍历就直接输出。

• 翻转最低位的1

  要翻转最低位的1，前提是我们能找到最低位的1。那么我们该如何“找”到最低位的1呢？就这么找肯定是不行的，我们可以给一个“微小的扰动”——$\pm1$，。由于二进制每一位只能是1或1，所以当我们计算x-1时，x就会向最低位的1借位，从某种意义上我们就找到了最低位的1。我们举个例子看看减一会发生什么

  ​

  可以发现x-1与x最低位1前面的位相同，而最低位1以及后面的位发生反转，根据性质可得计算方法

  ​

  稍作引申，我们可以得到统计某个二进制数1位的数量，我只要不断重复上述操作，每次讲数量++，直到x变为0就得到了1的数量

• 循环左移²/循环右移k位（suppose sizeof(int)=32)

  直接给出循环左移的计算式：

  ​

  其实也很好理解，循环左移一定是要左移的，但是超出部分要放到末尾就相当于右移，最后要把两个结果拼接起来就用“或”运算。

• 二进制加法器

  虽然二进制的加法看似简单，但是如果我们自己来实现也得费一点力，因为我们不仅要将每一位相加还得处理进位的问题。但是如果我们把这两个过程分开考虑，问题就迎刃而解。下面是实现加法器的代码：

  int add(int a,int b){
      //进位为0，运算结束
      if(b==0){
          return a;
      }
      //计算两数之和，忽略进位
      //两二进制数相加，对应为不同结果为1否则为0，符合异或
      int sum=a^b;
      
      //计算进位
      //两二进制数对应位相同产生进位，符合与运算
      //进位应当是高一位置1，故左移一位
      int carry=(a&b)<<1
          
      //递归调用，进位与直接和相加可能产生新的进位
      return add(sum,carry);
  }

• 求平均数

  如果理解了二进制加法器，那么我们也可以找到一种求两个数平均数的方法（取整后的平均数），下面先给出计算的方法：

  ​

  其中的加法可以直接使用上面的二进制加法器，原来和二进制加法器一样，分两部分计算：a+b产生的进位一定是个偶数，所以其均值应为((a&b)<<1)>>1 = a&b；a+b忽略进位的和为a\^b，平均值为(a^b)>>1(这一步运算会发生取整),最后结果就是上面的式子。

注意事项

位运算的使用是有限制的，可以进行位运算的只能是无符号的整型，即char、short、int、long,对于有符号的整型虽然理论上也支持位运算，但是其结果可能因为机器不同而结果不同（主要是由于不同机器对符号位的处理可能有不同规定）。

¹. 异或运算结果为：相同为0，不同为1。 ↩

². 循环左移的意思是，限定的长度下，每一位向左移，超出的补到末尾，举个例子就是游戏中人物超出屏幕会从另一边出来。 ↩