位运算的奇思妙想

位操作实现乘除法

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

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

示例

Lintcode 1

---

位操作交换两数

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

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

解释

第一步：a ^= b –> a = (a^b);
第二步：b ^= a –> b = b^(a^b) —> b = (b^b)^a = a
第三步：a ^= b –> a = (a^b)^a = (a^a)^b = b

---

位操作判断奇偶

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

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

---

位操作交换符号

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

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

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

---

位操作求绝对值

整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得。

int abs(int a) {
  int i = a >> 31;
  return ((a^i) - i); // return i == 0 ? a : (~a + 1);
}

步骤

1. 判断符号位。整数右移31位为0，负数右移31位为-1。
2. 根据符号位进行对应的处理。

---

位操作进行高低位交换

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

34520的二进制表示：
10000110 11011000

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

做法如下：

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

解释

1. 将其高 8 位移到低 8 位，高位补0 。
2. 再将其低 8 位移到高 8 位，低位补0 。
3. 最后再将上述的结果进行或操作即可。

---

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

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。

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

---

参考

https://www.zhihu.com/question/38206659/answer/736472332

---

个人备注

此博客内容均为作者学习所做笔记，侵删！
若转作其他用途，请注明来源！