此文涉及的是CS和算法基础，适用于任何开发者。好的开发者一边和其他开发者打交道，另外也要和机器打交道。不过好的代码要效率（执行所需的时间成本和内存成本）和可读性兼备。

为了提高大家对位运算的兴趣，这里引入力扣上的一个算法题：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法，可能的解法有如下几种。

• 使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。

• 使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。

• 使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。

上述三种解法都需要额外使用 O(n) 的空间，其中 n 是数组长度。

如何才能做到线性时间复杂度和常数空间复杂度呢？

答案是使用位运算。对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。

• 任何数和 0 做异或运算，结果仍然是原来的数，即 aa⊕0=a。
• 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
• 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

// 位运算异或
class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

复制代码

操作符

• &
• |
• ^(异或，相异为1，相同为0）
  • 0^a==a;a^a==0
• ~(取反，0变1，1变0)
• <<左移，高位丢弃，低位补0，乘以2，变两倍
• >>右移，对无符号数，高位补 0；对有符号数，高位补符号位，除以2，变一半

交换两数

// 普通操作
void swap(int & a, int & b) {
  a += b;
  b = a - b; // (a + b) - b
  a -= b; // (a + b) - a
}
// 异或
void swap(int & a, int & b) {
  a ^= b; // a = (a ^ b)
  b ^= a; // b = b ^ (a ^ b) = (b ^ b) ^ a = a
  a ^= b; // a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b
}
复制代码

判断奇偶

最后一位是0（偶数），是1（奇数）

if (0 == (a & 1)) {
  // even number
} else {
  // odd number
}
复制代码

交换符号

** 正数取反加1，变成其对应的负数（补码）；负数取反加一，变成其对应的正数原码**

int reversal(int a) {
    return ~a + 1;
 }
复制代码

求绝对值

• 正数的绝对值是其本身，负数的绝对值是其源码。我们首先判断符号位（正数右移31位得到0，负数右移31位得到-1，即0xffffffff。然后根据符号位进行相应的操作

int abs (int a) {
    int i = a >> 31;
    return i == 0 ? a : (~a + 1)
}
复制代码

参考资料

• 位运算有什么奇技淫巧
• matrix67
• juejin.cn/post/684490…
• zhuanlan.zhihu.com/p/26890617

结尾

以上资料中 位运算有什么奇技淫巧中第二个力扣的回答比较系统，还有matrix67大神的文章也很好

大家如果想优化应用程序中耗时最多的关键算法的时间复杂度和空间复杂度，可以夯实一下位运算，帮助比较大
比如说Immutable.js中与Tries有关的底层算法是基于位运算（或者说其他优秀框架）。

这篇文章拖了很久了，以后有空会慢慢继续补充。笔者最近在写交叉表，只会研究工作上用到的设计模式和算法数据结构，连写文章的时间都没有多少，为了尽快发文，将就一下吧?