位运算
位运算讲究技巧，需要多积累经验。
一、背景知识
Go 语言支持的 位运算符 如下：
| 运算符 | 描述 | 规则 |
|---|---|---|
| & | 按位 与 | 二者同为 1 时结果才为 1，否则为 0 |
| | | 按位 或 | 二者同为 0 时结果才为 0，否则是 1 |
| ^ | 按位 异或 | 相同为 0，相异为 1 |
| « | 左移 n 位，相当于乘以 2 的 n 次方 | 后面补 0 |
| » | 右移一位，相当于除以 2 的 n 次方 | 截掉最后一位 |
1. 与
将参与运算的两个数 各对应的二进制位 相与。只有当二者参与运算的对应位同为 1 时，该位才为 1，否则为 0。
a := 60 // 0011 1100
b := 23 // 0001 0111
fmt.Println(a & b) // 0001 0100
上述例子中，我们从最后一位开始，逐位运算。可以看到只有 倒数第3位 和 倒数第5位 都是 1，结果中也只有倒数第 3 位和倒数第 5 位是 1。
规律：
任何数 & 0 = 0；任何数 & 任何数 = 任何数；
2.或
将参与运算的两个数 各对应的二进制位 相或。只有当二者对应位全部是 0 时，该位结果才是 0，其他情况结果全为 1。
a := 60 // 0011 1100
b := 23 // 0001 0111
fmt.Println(a | b) // 0011 1111
规律：
任何数 | 0 = 任何数任何数 | 任何数 = 任何数
3. 异或
逐位异或，对应位相同，结果为 0，否则为 1——可以理解为 “抵消 1” 效果。
a := 60 // 0011 1100
b := 23 // 0001 0111
fmt.Println(a | b) // 0010 1011
规律：
任何数 ^ 任何数 = 0任何数 ^ 0 = 任何数任何数 ^ 1 = ~任何数(按位取反)
二、经典题目
1. 二进制中 1 的个数
- LeetCode 题目： 191. 位 1 的个数
1.1 题目描述
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
举例：
输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
1.2 思路
思路 1
最后一位通过和 1 进行 与运算，可以判断最后一位是否为 1；然后将要计算的数字向右移动 1 位，再计算是否最后一位是否为 1。逐渐循环，知道直到要计算的数变成 0。
func hammingWeight(num uint32) int {
result := 0 // 保存1出现的次数
for num > 0 {
if num&1 == 1 {
result++ // 最后一位是 1
}
num >>= 1 // 将原数右移一位
}
return result
}
思路 2
某一位通过和 1 进行 与运算，可以判断该位是是否为 1。题目指定了 32 位无符号整数，那么循环 32 次，从最后一位开始逐位判断，如何向前移动？左移一位即可。
func hammingWeight(num uint32) int {
result := 0
base := uint32(1)
for i := 0; i < 32; i++ {
if base&num != 0 {
result++
}
base <<= 1
}
return result
}
思路 3
出发点：n & (n-1)，会消除 n 最后一个 1。因此，n & (n-1) 总是能把 n中最低位的 1 变成 0 ，并保持其他位不变。具体什么原因，暂时不做深究。
func hammingWeight(num uint32) int {
result := 0
for num > 0 {
result++
num &= num - 1
}
return result
}
2. 判断一个数是否为 2 的幂
- LeetCode 题目：231. 2 的幂
2.1 题目描述
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
示例：
输入: 1 输出: true 解释: 20 = 1
2.2 解题思路
如果将 2 的所有次幂的二进制写出来，你会发现这些数的规律：最高位都是 1，其余位全是 0。也就是说，如果一个数为 2 的次幂，那么它只有一个 1，而且是在最高位，同时也是最后一个 1。再回想一下上一题中的思路三，n & (n-1) 会消除最后一个 1，于是乎：
func isPowerOfTwo(n int) bool {
return n > 0 && n&(n-1) == 0
}
3. 使用位运算求和
- LeetCode 题目：剑指 Offer 65. 不用加减乘除做加法
3.1 题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
举例：
输入: a = 1, b = 1 输出: 2提示：
a,b均可能是负数或 0- 结果不会溢出 32 位整数
3.2 解题思路
我们用 n 表示无进位和，c 表示进位，那么 sum = a + b = n + c，而位运算可以分别计算出 n 和 c。以两个 1 位的二进制数求和为例：
| a | b | 无进位和 n | 进位 c |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 10 |
从上表中可以看出，n = a ^ b，c = (a&b) << 1。借用 leetcode 上大神的一张图：
但是在 sum = n + c 中还是使用了加法，而这种情况我们依旧可以使用上面的规律。这里可以使用一个循环来解决，需要存储n 和 c，循环直到c = 0 时停止，而此时n 即为结果。
func add(a,b int) int {
/*
* 循环解法
for b != 0 {
b, a = (a&b) << 1, a ^ b
}
return a
*/
/*
* 递归解法，比上面的循环解法更清晰
if b == 0 {
return a
}
return add(a ^ b, (a & b) << 1)
*/
}
4. 数组中出现的次数
- LeetCode 题目：136. 只出现一次的数字
4.1 题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例：
输入: [2,2,1] 输出: 1
4.2 解题思路
回想前面背景知识中的 异或 的特性：任何数 ^ 任何数 = 0，并且 任何数 ^ 0 = 任何数。所以思路很明显，全部进行 异或 操作，出现两次的都会被“抵消”，最后剩下那个“没人要的”，就是我们要找的。
func singleNumber(nums []int) int {
if len(nums) == 0 {
return 0
}
// 整体异或运算
for i:=1;i<len(nums);i++ {
nums[0] ^= nums[i] // 使用已有数组的第0个位置，节省空间
}
return nums[0]
}
4.3 进阶——只出现一次的数字 II
- LeetCode 题目：137. 只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例：
输入: [2,2,3,2] 输出: 3
使用一个 map 的解法这里没必要说了，因为使用了额外空间。
思路 1
使用数学规律法——原数组去重、再乘以 3 得到的值，刚好就是要找的元素的 2 倍。Go 中没有 set 的这种数据结构，这里提供 Python 解法：
def singleNumber(nums){
return int((sum(set(nums))*3 - sum(nums))/2)
}
思路 2
回想之前的 异或，发现有两个 1，该位结果是 0；二进制加法中，两个 1 相加，产生了进位，抛弃进位，其结果也是 0——这个过程，可以看成是对应位上 1 的个数对 2 取模的结果。如果是三个数呢？是不是三个数的对应位都是 1 的时候，该位结果才是 0，否则就是 1——对应位上的 1 的个数对 3 取模即可。
func singleNumber(nums []int) int {
result := 0
for i := 0; i < 64; i++ {
// int至少32位，一般都是64位
// 初始化每一位1的个数为0
number := 0
for _, k := range nums {
// 通过右移i位的方式，计算每一位1的个数
number += (k >> i) & 1
}
// 对3取模后 最终将抵消后剩余的1放到对应的位数上
res |= (number) % 3 << i
}
return res
}
再如果 除 1 个元素外，每个元素出现了 4 次呢？原理一样，对 4 取模即可。