位运算的实际意义（常见的位运算）

计算机中的数在内存中都是以二进制形式进行存储的，用位操作就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。位操作是各大互联网公司面试经常会问的一类问题。

位操作符

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

| 或运算 两个位都是 0 时，结果才为 0，否则为 1，如：

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

~ 取反运算，0 则变为 1，1 则变为 0，如：

<< 左移运算，向左进行移位操作，高位丢弃，低位补 0，如：

>> 右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位，如：

常见位运算问题

1. 位操作实现乘除法

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

---

2. 位操作交货两数

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

位与操作解释：

• 第一步：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

---

3. 位操作判断奇偶数

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

---

4. 位操作交换符号

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

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

---

5. 位操作求绝对值

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

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

---

6. 位操作进行高低位交换

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

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

---

7. 位操作进行二进制逆序

将无符号数的二进制表示进行逆序，求取逆序后的结果，如：

在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理。

• 第一步：以每 2 位为一组，组内进行高低位交换

• 第二步：在上面的基础上，以每 4 位为 1 组，组内高低位进行交换

• 第三步：以每 8 位为一组，组内高低位进行交换

• 第四步：以每 16 位为一组，组内高低位进行交换

对于上面的第一步，依次以 2 位作为一组，再进行组内高低位交换，这样处理起来比较繁琐，下面介绍另外一种方法进行处理。先分别取原数 10000110 11011000 的奇数位和偶数位，将空余位用 0 填充：

再将奇数位右移一位，偶数位左移一位，此时将两个数据相或即可以达到奇偶位上数据交换的效果：

上面的方法用位操作可以表示为：

• 取 a 的奇数位并用 0 进行填充可以表示为：a & 0xAAAA
• 取 a 的偶数为并用 0 进行填充可以表示为: a & 0x5555 因此，上面的第一步可以表示为：
• a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
• 同理，可以得到其第二、三和四步为：
• a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
• a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
• a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
• 因此整个操作为：

---

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，则我们可以通过下面方法去统计：

,