由于本人在阅读 FFmpeg 的源代码过程中，发现有很多的位运算相关内容。但是，由于本人半路出家对于这些基础知识不扎实且不成体系，因而在此记录本人遇到的和百度发现的。下方会附上原文链接。

位运算实现四则运算

  • 乘除法：这个相对简单，就是简单的左移右移
1
2
3
int a = 2;
a >> 1; ---> 1
a << 1; ---> 4
  • 加减法：此方法在某些特殊值域范围内有效，目前阅读 FFmpeg 代码发现 8192 与其它值能
    有效保证此结构。请注意自己区分。
1
2
3
int a = 1, b = 2, c = -1;
a | b;  ---> 3
a | c;  ---> 0

位运算交换两数

1
2
3
a ^= b;
b ^= a;
a ^= b;

位运算判断奇偶

只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数

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

位操作求绝对值

整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作

1
2
3
4
int abs(int a) {
  int i = a >> 31;
  return i == 0 ? a : (~a + 1);
}

上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任何数与 0 异或都会保持不变，与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 0xffffffff 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)

1
2
3
4
int abs2(int a) {
  int i = a >> 31;
  return ((a^i) - i);
}

位操作的高低位交换

给定一个 16 位的无符号整数，将其高 8 位与低 8 位进行交换，求出交换后的值，如：

1
2
3
4
5
6
34520的二进制表示：
10000110 11011000

将其高8位与低8位进行交换，得到一个新的二进制数：
11011000 10000110
其十进制为55430

从上面移位操作我们可以知道，只要将无符号数 a>>8 即可得到其高 8 位移到低 8 位，高位补 0；将 a<<8 即可将 低 8 位移到高 8 位，低 8 位补 0，然后将 a>>8 和 a<<8 进行或操作既可求得交换后的结果。

1
2
unsigned short a = 34520;
a = (a >> 8) | (a << 8);

位操作统计二进制中 1 的个数

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：

  • 第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000
  • 第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000
  • 第三次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000
    我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：
1
2
3
4
5
count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}

引用

位运算有什么奇技淫巧？