位运算的奇技淫巧

计算机中数在内存中都是以二机制形式进行存储的，用位运算就是直接对整数在内存中的二机制位进行操作，因此执行效率很高，因此在程序中，按需尽量使用位运算进行操作

位操作符

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

  1 2 3 4

  10011 &11001 ----------- 10001

• | 或运算：两位都是0时，结果才为0；

  1 2 3 4

  10011 |11001 ----------- 11011

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

  1 2 3 4

  10011 ^11001 ----------- 01010

• ~取反运算，0变为1，1变为0；

  1 2 3 4

  10011 ~ --------- 01100

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

  1 2 3 4 5 6

  int a=8; a<<3; 移位前：00000000 00000000 00000000 00001000 移位后：00000000 00000000 00000000 01000000 移动后a=64,即左移为a*2^3=64

• >>右移运算，向右进行移位运算，高位补0，对于有符号数，高位补符号位；

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

  unsigned int a=8; a>>3; 移位前：00000000 00000000 00000000 00001000 移位后：00000000 00000000 00000000 00000001 int a=-8; a>>3; 计算机中负数以补码的形式存放 首先8到-8是取反后为 00000000 00000000 00000000 00001000 ~ ------------------------------------ 11111111 11111111 11111111 11110111 +1得到补码 11111111 11111111 11111111 11110111 +1 --------------------------------------- 11111111 11111111 11111111 11111000 所以前： 11111111 11111111 11111111 11111000 移位后： 11111111 11111111 11111111 11111111 转为十进制： 最高位是1， 所以是负数。 按补码规则，如下等式成立： 　　 负数 = 负数的绝对值按位取反+1 负数按位取反+1 =负数的绝对值 　　 所以11111111按位取反+1 就等于 1. 　　 因此，对应-1

  正数的补码 = 原码；负数的补码 = 原码符号位不变， 数值位按位取反后+1

---

• 常见位运算问题

  1、位操作实现乘除法

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

  2、位操作交换两数

  位操作交换两数可以不需要第三个临时变量，虽然普通操作也可以做到，但是没有其效率高

  1 2 3 4 5 6 7 8 9 10 11 12 13

  //普通操作 void swap(int &a, int &b) { a = a + b; b = a - b; a = a - b; } //位与操作 void swap(int &a, int &b) { a ^= b; b ^= a; a ^= b; }

  3、位操作判断基偶数

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

  1 2 3

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

  4、位操作交换符号

  交换符号将正数变成负数，负数变成正数

  1 2 3

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

  整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数

  5、位操作求绝对值

  整数的绝对值是其本身，负数的绝对值正好可以与其进行取反加一所得，即我们首先判断其符号位（整数右移31位得到0，负数右移31得到-1，即0xffffffff）

  十六进制转换为二进制就是直接把每位转换成二进制就可以了
  f(15)变成二进制：1111，则
  0xffffffff = 1111 1111 1111 1111 1111 1111 1111 1111 (8个F的二进制形式, 一个F占4个字节 )
  即32位数都是1的二进制数

  1 2 3 4

  int abs(int a){ int i>>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); }

  6、位操作进行高地位切换

  给定一个 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);

  7、位操作统计二机制中1的个数

  统计二机制1的个数可以分别获取每个二机制的位数，然后再统计其1的个数，但是这种方法效率比较低，这里介绍一种更高效的方法

  以34520为例，我们计算其a&(a-1)的结果：

  第一次：

  1 2	计算前：10000110 11011000 计算后：1000 0110 1101 1000

  第二次：

  1 2	计算前：10000110 11010000 计算后：10000110 11000000

  第三次：

  1 2	计算前：10000110 11000000 计算后：10000110 10000000

  我们发现，，每计算一次，二进制中就少一个1，所以

  1 2 3 4 5

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

---

• 异或操作常见的用途

https://blog.csdn.net/qq_39705793/article/details/81237005

---

• ← Previous Post
• Next Post →

---

---