这篇文章大部分是从英文翻译过来的，是在刷 leetcode 的时候看到的一个 solution，感觉作者讲的很好，只不过英文的读起来有点费劲，在网上搜了一下，发现也没有翻译的版本，于是就想做第一个吃螃蟹的人，然后再加一些其他文章中的位操作技巧进行总结，最终形成了这个版本（文末有原文链接，英文好的可以去看一下，毕竟看原文才不会被误导）

位操作介绍

位操作是对少于一个字母的数据段或位数进行算法层面的计算。在计算机工程领域，用到位操作任务有低等级设备控制、误差检测和校正算法，数据压缩、加密算法和优化算法。对于大多数任务而言，现在编程语言允许程序员直接用高级语言而不是位操作。位操作的源码使用位运算：AND、OR、XOR、NOT 和移位 由于位操作是可以并行处理的，所以在某些情况下可以减少甚至避免对于某数据结构的循环操作，从而在速度上会有较大提升，但是代码将变得很难书写和理解。

基础知识

位操作的核心是位运算符 &（和）、|（或）、~（不）、^（异或）以及移位运算符 a << b 和 a >> b（异或通常缩写为 XOR）。

• 取并集：A | B
• 取交集：A & B
• 取补集：A & ~B
• 所有位数取反：^A 或者~A
• 设置某位：A | = 1 << bit
• 清除某位：A & = ~（1 << bit）
• 检验某位：(A & 1 << bit) != 0
• 提取最后一位：A & -A 或者 A & ~ (A-1) 或者x ^ (x & (x-1))
• 移除最后一位：A & (A-1)
• 所有位数为1：~0

位操作的基本技巧

• 用异或操作符 ^ 可以删除完全相同的数字然后保存剩余的，或者保存不同位然后移除相同位
• 用 | 操作符可以留存尽可能多的 1
• 用 & 可以筛选出指定位

1. 检查整数是奇数还是偶数

只要整数的最后一位比特是 1，那它就是奇数，反之就是偶数。即最低位要么是 1 要么是 0，x 和 1 与（&）运算，保留最低位，如果最低位是 1，x 是奇数，如果最低位是 0 ，x 是偶数。
例如 43，二进制表示为 00101011，注意它的最低位为 1，我们将 43 与 1 做 & 运算：

    00101011
&   00000001   (note: 1 is the same as 00000001)
    --------
    00000001

2. 测试第 n 位比特

只要将与运算的 1 向左平移相应的位数即可。假设向左平移 n 位，接下来的与运算就是只保留第 n 位，其它位都清零了。
比如：122 的第三位比特是 1 吗？（从 0 开始数）可以这样做：122 & (1 << 3)，122 的二进制表示是 01111010，(1 << 3)即 1 向左平移 3 比特 00001000。

    01111010
&   00001000
    --------
    00001000

3. 将第 n 位设为 1 或不变

和前面的技巧一样，只是把与运算（&）换成了或运算（|）。与 1 进行或运算将参与运算的位置设为 1，与 0 进行或运算参与预算的位不变。

y = x | (1 << n)

4. 将第 n 位设为 0

这个方法的关键就是 ~(1 << n)，它将第 n 位设为 0，其它位全部为 1。看下面：

y = x & ~(1 << n)

5. 将第 n 位取反

这次使用的是异或运算，如果异或运算的两个操作数相同，运算结果是 0，两个操作数不同，结果是 1。怎样将第 n 位取反呢？如果第 n 位比特为 1，将它与 1 进行异或运算结果就是 0，如果它是 0，那么它与 1 异或运算的结果就是 1。于是这一位就取反了。

y = x ^ (1 << n)

位操作在数字运算中的应用

1. 计算某二进制数中的 1 的数量

int count_one(int n) {
    while(n) {
        n = n&(n-1);
        count++;
    }
    return count;
}

2. 判断某数字是否为 4 的 n 次方(n ≥ 0)，是就返回该数，不是就返回 0 或 false

bool isPowerOfFour(int n) {
    return !(n&(n-1)) && (n&0x55555555);
}

3. 使用 ^ 和 & 来求两个数字的和

int getSum(int a, int b) {
    return b==0? a:getSum(a^b, (a&b)<<1); 
}

4. 寻找丢失数字：给你一个包括从 0 到 n 的各不相同的 n 元数组，从中找出丢失的那个数字，比如给你的数组为 [0, 1, 3]，那么应该返回 2（当然，你也可以用数学方法解决）

int missingNumber(vector<int>& nums) {
    int ret = 0;
    for(int i = 0; i < nums.size(); ++i) {
        ret ^= i;
        ret ^= nums[i];
    }
    return ret^=nums.size();
}

5. 给定一个自然数 N，找到小于等于 N 的 2 的最大倍数

long largest_power(long N) {
    // 将所有右侧位变为1.
    N = N | (N>>1);
    N = N | (N>>2);
    N = N | (N>>4);
    N = N | (N>>8);
    N = N | (N>>16);
    return (N+1)>>1;
}

6. 将一个 32 位的无符号数进行反转

uint32_t reverseBits(uint32_t n) {
    unsigned int mask = 1<<31, res = 0;
    for(int i = 0; i < 32; ++i) {
        if(n & 1) res |= mask;
        mask >>= 1;
        n >>= 1;
    }
    return res;
}
uint32_t reverseBits(uint32_t n) {
	uint32_t mask = 1, ret = 0;
	for(int i = 0; i < 32; ++i){
		ret <<= 1;
		if(mask & n) ret |= 1;
		mask <<= 1;
	}
	return ret;
}

7. 给定一个范围[m, n]，其中 0<=m<=n<=2147483647，返回在这个范围内的所有数的按位进行 AND 操作之后的数字，比如范围为 [5, 7]，那返回的应该是按位进行计算的 5+6+7，结果是 4（100）

int rangeBitwiseAnd(int m, int n) {
    int a = 0;
    while(m != n) {
        m >>= 1;
        n >>= 1;
        a++;
    }
    return m<<a; 
}

8. 求一个无符号数的汉明距离（即二进制表示中的 1 的个数）

int hammingWeight(uint32_t n) {
	int count = 0;
	while(n) {
		n = n&(n-1);
		count++;
	}
	return count;
}
int hammingWeight(uint32_t n) {
    ulong mask = 1;
    int count = 0;
    for(int i = 0; i < 32; ++i){
        if(mask & n) count++;
        mask <<= 1;
    }
    return count;
}

9. 用位操作交换变量

a = a ^ b; 
b = a ^ b;  // 实际上是(a^b)^b 也就是a异或了b两次，等号右边是a的值
a = a ^ b;  // 此时b里面已经是“果汁”，实际上是(a^b)^a，也就是b异或了a两次，是b

位操作更复杂的应用

1. 查找 DNA 重复序列

所有的 DNA 是由一系列简写为 A、C、G 和 T 核苷酸组成的，比如 “ACGAATTCCG”，当我们研究 DNA 时，有时候识别 DNA 中的重复序列是有用的，设计一个方法可以找出所有在 DNA 分子中出现不止一次的 10 字母长的序列（或子序列）

举个例子：
Given s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” Return: [“AAAAACCCCC”, “CCCCCAAAAA”]

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int sLen = s.length();
        vector<string> v;
        if(sLen < 11) return v;
        char keyMap[1<<21]{0};
        int hashKey = 0;
        for(int i = 0; i < 9; ++i) hashKey = (hashKey<<2) | (s[i]-'A'+1)%5;
        for(int i = 9; i < sLen; ++i) {
            if(keyMap[hashKey = ((hashKey<<2)|(s[i]-'A'+1)%5)&0xfffff]++ == 1)
                v.push_back(s.substr(i-9, 10));
        }
        return v;
    }
};

2. 多数单元

给定一个 n 元数组，多数单元式在该数组中出现次数多于 ⌊n/2⌋ 次的数（一般采用位运算，但是在这里我们也可以采用分组和穆尔投票算法）

int majorityElement(vector<int>& nums) {
    int len = sizeof(int)*8, size = nums.size();
    int count = 0, mask = 1, ret = 0;
    for(int i = 0; i < len; ++i) {
        count = 0;
        for(int j = 0; j < size; ++j)
            if(mask & nums[j]) count++;
        if(count > size/2) ret |= mask;
        mask <<= 1;
    }
    return ret;
}

3. 找数字

给定整数数组，每个元素都出现了三次，除了一个元素，找到这个元素（这种问题通过位运算可以迎刃而解）

// inspired by logical circuit design and boolean algebra;
// counter - unit of 3;
// current   incoming  next
// a b            c    a b
// 0 0            0    0 0
// 0 1            0    0 1
// 1 0            0    1 0
// 0 0            1    0 1
// 0 1            1    1 0
// 1 0            1    0 0
// a = a&~b&~c + ~a&b&c;
// b = ~a&b&~c + ~a&~b&c;
// return a|b since the single number can appear once or twice;
int singleNumber(vector<int>& nums) {
    int t = 0, a = 0, b = 0;
    for(int i = 0; i < nums.size(); ++i) {
        t = (a&~b&~nums[i]) | (~a&b&nums[i]);
        b = (~a&b&~nums[i]) | (~a&~b&nums[i]);
        a = t;
    }
    return a | b;
}

4. 字符长度的最大积

给定一个包含几个字符串的数组，找到 length(word[i])*length(word[j]) 的最大值，其中这两个字符串没有共同的字符。假定每个字符串的字符均为小写，如果没有这样的两个字符，返回 0

实例：

1. Example 1: Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”] Return 16 The two words can be “abcw”, “xtfn”.
2. Example 2: Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”] Return 4 The two words can be “ab”, “cd”.
3. Example 3: Given [“a”, “aa”, “aaa”, “aaaa”] Return 0 No such pair of words.

解题思路：

因为我们要非常频繁的用到字符串的长度，并且我们要比较两个字符串中的字符来检测他们是否有相同的字符，所以：

• 使用一个 int 型数组来保存每个字符串的长度
• 因为 int 型数字有 4 比特，可以有 32 位，而字母只有 26 中，所以我们仅仅使用一位就可以代表字母在字符串中的存在与否

int maxProduct(vector<string>& words) {
    vector<int> mask(words.size());
    vector<int> lens(words.size());
    for(int i = 0; i < words.size(); ++i) lens[i] = words[i].length();
    int result = 0;
    for (int i=0; i<words.size(); ++i) {
        for (char c : words[i])
            mask[i] |= 1 << (c - 'a');
        for (int j=0; j<i; ++j)
            if (!(mask[i] & mask[j]))
                result = max(result, lens[i]*lens[j]);
    }
    return result;
}

二进制在趣味数学中的应用

1. 一工人工作 7 天，老板有一段黄金，每天要给工人 1/7 的黄金作为工资，老板只能切这段黄金 2 刀，请问怎样切才能每天都给工人 1/7 的黄金？

因为 7 < 2^3 = 8，所以只要使用 2^0，2^1，2^2 三个数，就可以表示 1 到 7 之间的所有数。那么我们只要把金条分成三份，比例为 1:2:4，也就是第一刀切下金条的七分之一（设为黄金 A），第二刀切下金条的七分之二（设为黄金 B），剩下的部分刚好为金条的七分之四（设为黄金 C）。我们只要按照如下的方法发放工资，就解决问题了：

1. 第一天：给长工黄金 A；（1 = 2^0）
2. 第二天：给长工黄金 B，并把黄金 A 拿回来；（2 = 2^1）
3. 第三天：给长工黄金 A；（3 = 2^0 + 2^1）
4. 第四天：给长工黄金 C，并把黄金 A 和黄金 B 拿回来；（4 = 2^2）
5. 第五天：给长工黄金 A；（5 = 2^0 + 2^2）
6. 第六天：给长工黄金 B，并把黄金 A 拿回来；（6 = 2^1 + 2^2）
7. 第七天：给长工黄金 A。（5 = 2^0 + 2^1 + 2^2）

2. 用天平称 1~63 克整数克重的物品，至少要配备几只多重的砝码（砝码只能放在天平的一端）？

没有学过二进制的人是很难想到答案的，可是如果你知道二进制数，那就不难了。我们知道二进制中只有 0 和 1 两个数字，它的各位数字的权值从小到大依次为 2^0，2^1，2^2，2^3。。。。我们用一个数的每位数字乘以其权值所得到的乘积之和来表示这个数。对于一个具有 8 位的二进制数来说，它可以表示的数据范围是 0~2^8。63 = 2^6 – 1 = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 所以，我们只需配备 2^0 =1，2^1 = 2，2^2 = 4，2^3 = 8，2^4 = 16，2^5 = 32 五种不同克数的砝码各一个。

3. 药瓶问题

一家药店收到运来的某种药品十瓶。每瓶装药丸 1000 粒。药剂师怀特先生刚把药瓶送上架子，一封电报接踵而来。怀特先生把电报念给药店经理布莱克小姐听。怀特先生：“特急！所有药瓶须检查后方能出售。由于失误，其中有一瓶药丸每粒超重 10 毫克。请即退回分量有误的那瓶药。怀特先生很气恼。怀特先生：“倒霉极了，我只好从每瓶中取出一粒来称一下。真是胡闹。怀特先生刚要动手，布莱克小姐拦住了他。布莱克小姐：“等一下，没必要称十次，只需称一次就够了。”这怎么可能呢？
布莱克小姐的妙主意是从第一瓶中取出1粒，从第二瓶中取出 2 粒，第三瓶中取出 3 粒，以此类推，直至从第十瓶中取出 10 粒。把这 55 粒药丸放在秤上，记下总重量。如果重 5510 毫克，也就是超过规格 10 毫克，她当即明白其中只有一粒是超重的，并且是从第一瓶中取出的。如果总重量超过规格 20 毫克，则其中有 2 粒超重，并且是从第二瓶中取出的，以此类推进行判断。所以布莱克小姐只要称一次，不是吗？
六个月后，药店又收到此种药品十瓶。一封加急电报又接踵而至，指出发生了一个更糟糕的错误。这一次，药丸每粒超重仍然是 10 毫克，但是对超重药丸的瓶数无可奉告，也就是说可能有好几个药瓶超重。怀特先生气恼极了。怀特先生：“布莱克小姐，怎么办？我们上次的方法不中用了。布莱克小姐没有立即回答，她在思索这个问题。布莱克小姐：“不错。但如果把那个方法改变一下，我们仍然只需称一次就能把分量有误的药品识别出来。这回布莱克小姐又有什么好主意？
为了解决第二个问题，我们必须用一个数字序列把每瓶药单独标上某个数字，且此序列中的每一个子集必须有一个单独的和。有没有这样的序列？有的，最简单的就是下列二重序列：1，2，4，8，16，。。。这些数字是 2 的连续次幂，这一序列为二进制记数法奠定了基础。在这个问题中，解法是把药瓶排成一行，从第一瓶中取出 1 粒，从第二瓶中取出 2 粒，从第三瓶中取出 4 粒，以此类推。取出的药丸放在秤上称一下。假设总重量超重 270 毫克，由于每粒分量有误的药丸超重 10 毫克，所以我们把 270 除以 10，得到 27，即为超重药丸的粒数。把 27 化成二进制数：11011 。在 11011 中自右至左，第一，二，四，五位上的“1”表示其权值分别为 1，2，8，16。因此分量有误的药瓶是第一，二，四，五瓶。

4. 简单的扑克魔术

请别人把一副牌洗过，然后放进你的口袋，再请人说出一个 1 至 15 以内的数字。然后你把手插进你的口袋里，一伸手就取出一组牌，其数值相加正好等于他所说的数字。
此秘密简单的很。在耍魔术之前，预先取出 A，2，4，8 各一张放入口袋。这副牌缺少区区四张，不大可能为人察觉。洗过的牌放入口袋后，暗中将其排置于原先已经放在口袋中的四张牌的后面。请别人说出一个数字，你用心算将此数表示成 2 的幂的和。如果是 10，那你就应想到：8+2=10，随即伸手入袋，取出 2 和 8 的牌示众。

5. 心灵感应游戏

心灵感应游戏的依据也是二进制原理，准备五张卡片，分别记为 A，B，C，D，E，上面写着 1~31 之间的一些整数。请一位观众想好此范围内的一个数字（例如某个人的年龄），然后请他把所有上面有此数字的卡片都交给你。你随即说出他心中所想的那个数字。
卡片如下：

• A：1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
• B：2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31
• C：4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31
• D：8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31
• E：16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

秘诀就是把每张卡片上 2 的幂的第一个数字相加。例如，如果把卡片 C 和 E 交给你，你只要将上面第一个数字 4 和 16 相加，便知道别人心中所想的数字是 20。这是为什么呢？
我们观察卡片上的数字，可以发现这样一个规律：
第一张卡片 (A) 上的数字如果用五位二进制表示，则分别为：
00001，00011，00101，00111，01001，01011，01101，01111，10001，10011，10101，10111，11001，11011，11101，11111。
第二张卡片 (B) 上的数字如果用五位二进制表示，则分别为：
00010，00011，00110，00111，01010，01011，01110，01111，10010，10011，10110，10111，11010，11011，11110，11111。
第三张卡片 (C) 上的数字如果用五位二进制表示，则分别为：
00100，00101，00110，00111，01100，01101，01110，01111，10100，10101，10110，10111，11100，11101，11110，11111。
请大家注意观察，第一张卡片上每个二进制数的右起第一位都是 “1”，第二张卡片上每个二进制数的右起第二位都是 “1”，第三张卡片上每个二进制数的右起第三位都是 “1”。依此类推，我们可以发现第 n 张卡片上每个二进制数的右起第 n 位都是 “1”。观众所想的数字和卡片的关系只有“有”和“无”两种状态，正好与二进制数码 0 与 1 一一对应。“有”我们就记为 “1”，“无”我们就记为 “0”，这样观众交给我们的卡片组合，就对应一个二进制数，如把卡片 C 和 E 交给你，那卡片组合就是“有无有无无”，对应二进制数为 10100”，即十进制数 “20”。又如把卡片A，B 和 E 交给你，那卡片组合就是“有无无有有”，对应二进制数为 “10011”，即十进制数 “19”。 二进制数的位数越多，能够表示的数值就越大，如果有 6 张卡片，则表示的数字范围扩大到 1~63，7 张卡片则可以表示 1~127。

参考文章

• A summary: how to use bit manipulation to solve problems easily and efficiently

扩展阅读

• Bit Twiddling Hacks
• Bitwise gems – fast integer math