1.位运算基础 2.位运算的奇淫技巧 3.两数之和 4.二的幂
5.一的个数 6.只出现一次的数字Ⅰ 7.只出现一次的数字Ⅱ
基本常用常考的，也就这么多。相信大家都知道，也就没什么好说的。
直接使用上面我们讲过的奇淫技巧进行解题：
“异或”是一个无进位加法，说白了就是把进位砍掉。比如01^01=00。
“与”可以用来获取进位，比如01&01=01，然后再把结果左移一位，就可以获取进位结果。
根据上面两个技巧，假设有 12+7：
根据分析，完成题解：
1//JAVA
2class Solution {
3 public int getSum(int a, int b){
4 while(b != 0){
5 int temp = a ^ b;
6 b = (a & b) << 1;
7 a = temp;
8 }
9 return a;
10 }
11}
对，就是这么简单。
可以看到，对于N为2的幂的数，都有 N&(N-1)=0 ，所以这就是我们的判断条件。（这个技巧可以记忆下来，在一些别的位运算的题目中也是会用到的）
根据分析，完成代码：
1//go
2func isPowerOfTwo(n int) bool {
3 return n > 0 && n&(n-1) == 0
4}
本题还是很简单。直接使用 x & (x - 1) 的技巧即可。
首先最容易想到的方法是：我们直接把目标数转化成二进制数，然后遍历每一位看看是不是1，如果是1就记录下来。通过这种比较暴力的方式，来进行求解。比如Java中，int类型是32位，我们只要能计算出当前是第几位，就可以顺利进行求解。
那如何计算当前是第几位呢，我们可以构造一个掩码来进行，说掩码可能大家听着有点懵逼，其实就是弄个1出来，1的二进制是这样：
我们只需要让这个掩码每次向左移动一位，然后与目标值求“&”，就可以判断目标值的当前位是不是1。比如目标值为21，21的二进制是这样：
然后每次移动掩码，来和当前位进行计算：
根据分析，完成代码：
1//java
2public class Solution {
3 public int hammingWeight(int n) {
4 int result = 0;
5 //初始化掩码为1
6 int mask = 1;
7 for (int i = 0; i < 32; i++) {
8 if ((n & mask) != 0) {
9 result++;
10 }
11 mask = mask << 1;
12 }
13 return result;
14 }
15}
唯一需要提醒的地方是：判断 n&mask 的时候，不要错写成 (n&mask) == 1，因为这里你对比的是十进制数。新人很容易犯这样的错误。
直接分析，我们要找只出现一次的数字，并且已知了其他的数字都只出现了两次。那么这种一听其实就应该想到需使用位运算来进行求解。最好的，就是在读完题目的瞬间，直接条件反射！（当然，如果你现在第一反应是想到 通过遍历统计，或者其他如使用hashmap 等方式来进行求解，那我觉得你的位运算这块，是有必要加强练习力度的。如果你第一反应，连思路都没有，那我觉得对于整个算法的能力这块，都是比较欠缺的，需要下苦功！）
回到题目，如何使用位运算进行求解呢？对于任意两个数a和b，我们对其使用 “异或”操作，应该有以下性质：
任意一个数和0异或仍然为自己：
a⊕0=a
任意一个数和自己异或是0：
a⊕a=0
异或操作满足交换律和结合律：
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
可能有人直接都不知道异或是什么，所以还是举个例子，比如5异或3，也就是5⊕3，也就是5^3，是下面这样：
因为这道题目比较典型，所以我多给几个版本的代码：
（CPP）
1//CPP
2class Solution {
3public:
4 int singleNumber(vector<int>& nums) {
5 int ans = 0;
6 for (int num : nums) {
7 ans ^= num;
8 }
9 return ans;
10 }
11};
（java版本）
1//JAVA
2class Solution {
3 public int singleNumber(int[] nums) {
4 int ans = nums[0];
5 for (int i = 1; i < nums.length; i++) {
6 ans = ans ^ nums[i];
7 }
8 return ans;
9 }
10}
(python版本)
1//py
2class Solution:
3 def singleNumber(self, nums: List[int]) -> int:
4 ans = 0
5 for i in range(len(nums)):
6 ans ^= nums[i]
7 return ans
使用hashmap来求解的方式，实在是没什么可说的。
1func singleNumber(nums []int) int {
2 m := make(map[int]int)
3 for _, k := range nums {
4 //如果是其他语言，请注意对应的判空操作！
5 m[k]++
6 }
7 for k, v := range m {
8 if v == 1 {
9 return k
10 }
11 }
12 return 0
13}
当然，这里还有一种数学解法：
原理：[A,A,A,B,B,B,C,C,C] 和 [A,A,A,B,B,B,C]，差了两个C。
也就是说，如果把原数组去重、再乘以3得到的值，刚好就是要找的元素的2倍。举个例子：
利用这个性质，进行求解：（python代码如下，这里要注意的是，使用int可能会因为超出界限报错）
1class Solution:2
def singleNumber(self, nums: List[int]) -> int:3
return int((sum(set(nums)) * 3 - sum(nums)) / 2)效果不错，但是仍然使用了额外空间。所以我们还是得使用位运算。对于“每个其余元素，均出现了二次”之所以可以使用“异或”进行求解，原因是因为“异或”操作可以让两数相同归 0。那对于其余元素出现三次的，是不是只要可以让其三者相同归 0，就能达到我们的目的呢？
这个思想可能比较简单，但是要让大家理解，还是有一定难度。如果大家准备好了，可以开始往下看。我看过leetcode上的题解，很多都是直接扔出来一个公式，其实讲的我认为并不是特别的清楚。所以我打算先把本题退化到“每个其余元素，均出现二次”的case来进行分析一下。
假如我们有 [21,21,26] 三个数，是下面这样：
回想一下，之所以能用“异或”，其实我们是完成了一个 同一位上有2个1清零 的过程。上面的图看起来可能容易，如果是这样：
那对于“每个其余元素，均出现了三次”也是一样，如果我们可以完成 一个同一位上的三个1清零的过程，也就是 a ？a ？a = 0，问题则迎刃冰解。那因为各语言中都没有这样一个现成的方法可以使用，所以我们需要构造一个。（想象一下，位运算也是造出来的对不对？）
如何构造，这里先说第一种方法（注意，到这里我们的问题已经转化成了定义一种 a ? a ? a = 0 的运算），观察一下“异或”运算：
1^1=0
1^0=1
0^1=1
是不是可以理解为，其实就是二进制的加法，然后砍掉进位呢？
砍掉进位的过程，是不是又可以理解为对 2 进行取模，也就是取余。到了这里，问题已经非常非常明确了。那我们要完成一个 a ? a ? a = 0 的运算，是不是其实就是让其二进制的每一位数都相加，最后再对 3 进行一个取模的过程呢？（一样，如果要定义一个 a ? a ? a ? a = 0 的运算，那就最后对 4 进行取模就可以了）
1//go
2func singleNumber(nums []int) int {
3 number, res := 0, 0
4 for i := 0; i < 64; i++ {
5 //初始化每一位1的个数为0
6 number = 0
7 for _, k := range nums {
8 //通过右移i位的方式，计算每一位1的个数
9 number += (k >> i) & 1
10 }
11 //最终将抵消后剩余的1放到对应的位数上
12 res |= (number) % 3 << i
13 }
14 return res
15}
如果对上面的代码不能理解，可以看看这个图，假设只有一个数 [21]，我们通过不断右移的方式，获取其每一位上的1。当然，这里因为余数都是1，所以肯定都保留了下来，然后与 1 进行 “与”运算，最终再将其放入到对应的位数上。
在上面的代码中，我们通过一个number，来记录每一位数出现的次数。但是缺点是，我们记录了64位（Go语言中，int为32位以上）
那如果我们可以同时对所有位进行计数，是不是就可以简化过程。因为我们的目的是把每一位与3取模进行运算，是不是就可以理解为其实是一个三进制。如果大家听不懂三进制的话，可以简单理解为3次一循环，也就是 00 - 01 - 10 - 11。但是又因为对于 11 这种情况，我们需要砍掉（上面已经说过了，相当于 11 - 00 的转化），所以我们就只有3个状态，00 - 01 - 10，所以我们采用 a 和 b 来记录状态。其中的状态转移过程如下：
这里 a` 和 b` 的意思代表着 a 和 b 下一次的状态。next 代表着下一个 bit 位对应的值。然后这是什么，不就是状态机嘛。。。我们通过 a 和 b 的状态变化，来完成次数统计。
然后因为此图复杂，将其分别简化成 a 和 b 的卡诺图（卡诺图是逻辑函数的一种图形表示。两逻辑相邻项，合并为一项，保留相同变量，消去不同变量。）
然后我们根据卡诺图（这个卡诺图其实并不难看。。如果学习一下话，还是挺简单的。。）写出关系式：
a` = (a &~ next) | (b & next)
b` = (~a & ~b & next) | (b & ~next)
然后就是套公式：（Java代码，注意Go语言中是不天然支持 ~ 这种运算的）
1class Solution {
2 public int singleNumber(int[] nums) {
3 int a = 0, b = 0, tmp = 0;
4 for (int next : nums) {
5 tmp = (a & ~next) | (b & next);
6 b = (~a & ~b & next) | (b & ~next);
7 a = tmp;
8 }
9 return b;
10 }
11}
当然，其实题解还可以再近一步优化，其实就是化简上一步中的公式：
1class Solution {
2 public int singleNumber(int[] nums) {
3 int a = 0, b = 0;
4 for (int next : nums) {
5 b = (b ^ next) & ~a;
6 a = (a ^ next) & ~b;
7 }
8 return b;
9 }
10}
当然，这个解法就相当牛皮了。如果实在看不懂也没关系，请把上面的两种解法掌握。
全部评论