特别提醒：Python 的同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题，比如：
(n << shift_amount) & 0xFFFFFFFF（Python 溢出会自动升位：）
位运算有很多奇技淫巧，位运算的速度非常快，仅次于赋值操作，常数时间极好！
这节课展示一下先贤的功力！骚就完了！
关于位运算还有非常重要的内容：
- N 皇后问题用位运算实现，将在【必备】课程里讲到
- 状态压缩的动态规划，将在【扩展】课程里讲到
题目1.判断一个整数是不是 2 的幂
测试链接：231.2 的幂
func isPowerOfTwo(n int) bool {
return n > 0 && n&(-n) == n // > 0 且 二进制中只有一个 1
}func isPowerOfTwo(n int) bool {
if n <= 0 {
return false
}
return n&(n-1) == 0
}题目2.判断一个整数是不是 3 的幂
本题和位运算没关系
测试链接：326.3 的幂
// 如果一个数字是 3 的某次幂，那么这个数一定只含有 3 这个质数因子
// 1162261467 是 int 型范围内，最大的 3 的幂，它是 3 的 19 次方
// 这个 1162261467 只含有 3 这个质数因子，如果 n 也是只含有 3 这个质数因子，那么
// 1162261467 % n == 0
// 反之如果 1162261467 % n != 0 说明 n 一定含有其他因子
func isPowerOfThree(n int) bool {
return n > 0 && 1162261467%n == 0
}题目3.返回大于等于 n 的最小的 2 的幂
const (
INT_BIT_COUNT = int(unsafe.Sizeof(int(0))) * 8 // int 占的位数
)
// 已知 n 是非负数
// 返回大于等于 n 的最小的 2 某次方
// 如果 int 范围内不存在这样的数，返回整数最小值
func near2power(n int) int {
if n <= 0 {
return 1
}
n--
for i := 1; i < INT_BIT_COUNT; i <<= 1 {
n |= n >> (1 << i)
}
return n + 1
}解释：
以 int8 举例
n 00100100
经过
n--
for i := 1; i < 8; i <<= 1 {
n |= n >> (1 << i)
}
会变成 00111111
即：从最左边的 1 开始，将右侧的位置都刷成 1
n 00100100
n-- 00100011
n 00100011
n>>1 00010001
n|n>>1 00110011
n 00110011
n>>2 00001100
n|n>>2 00111111
n 00111111
n>>4 00000011
n|n>>4 00111111题目4.区间 [left, right] 内所有数字 & 的结果
测试链接：201.数字范围按位与
func rangeBitwiseAnd(left int, right int) int {
for left < right {
right -= right & -right
}
return right
}解释：
当 left == right 时，right & right = right，正确
当 left < right 时，right 最右侧的 1 一定留不下来
right 01101100
& right-1 011
---------------------
000题目5.颠倒二进制位
颠倒，即：逆序
测试链接：190.颠倒二进制位
func reverseBits(n uint32) uint32 {
// 0b1010 == 0xa, 0b0101 == 0x5
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
// 0b1100 == 0xc, 0b0011 == 0x3
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
// 0b11110000 == 0xf0, 0b00001111 == 0x0f
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
// 0b1111111100000000 == 0xff00, 0b0000000011111111 == 0x00ff
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
n = (n >> 16) | (n << 16)
return n
}解释：
以 int8 举例
n abcdefjh
逆序 hjfedcba
一组一组地进行交换：
第一次：1v1 为一组
n a-b c-d e-f j-h
交换 b-a d-c f-e h-j
第二次：2v2 为一组
n ba-dc fe-hj
交换 dc-ba hj-fe
第三次：4v4 为一组
n dcba-hjfe
交换 hjfe-dcba
完成了！
如何交换？以第一次 1v1 为一组为例
n abcdefjh
& 10101010
---------------
a0c0e0j0
>>>1 0a0c0e0j a
n abcdefjh
& 01010101
---------------
0b0d0f0h
<<1 b0d0f0h0 b
a 0a0c0e0j
| b b0d0f0h0
---------------
badcfehj
交换完毕！题目6.返回一个数二进制中有几个 1
测试链接：461.汉明距离
func hammingDistance(x int, y int) int {
return cntOnes(x ^ y)
}
// 返回 n 的二进制中有几个 1
// 这里认为 int 是 32 位
func cntOnes(n int) int {
uN := uint(n) // go 中没有无符号右移，转成 uint
uN = (uN & 0x55555555) + ((uN >> 1) & 0x55555555) // 每 2 位表示 1 的个数
uN = (uN & 0x33333333) + ((uN >> 2) & 0x33333333) // 每 4 位表示 1 的个数
uN = (uN & 0x0f0f0f0f) + ((uN >> 4) & 0x0f0f0f0f) // 每 8 位表示 1 的个数
uN = (uN & 0x00ff00ff) + ((uN >> 8) & 0x00ff00ff) // 每 16 位表示 1 的个数
uN = (uN & 0x0000ffff) + ((uN >> 16) & 0x0000ffff) // 每 32 位表示 1 的个数
return int(uN)
}解释：
n 11111001 （每一位表示 1 的个数：1+1+1+1+1+0+0+1=6 个 1）
n 11111001
& 01010101
-------------
_1_1_0_1 （奇数位 1 的个数信息保留）
a 01010001
n>>>1 01111100
& 01010101
-------------
_1_1_1_0 （偶数位 1 的个数信息保留）
b 01010100
a 01 01 00 01
+ b 01 01 01 00
-------------
10 10 01 01
2 2 1 1 （每两位表示 1 的个数：2+2+1+1=6 个 1）
以此类推：推到每 32 位表示 1 的个数备注
题目 5 和题目 6 代码看着跟脑子有大病一样，承认很强但似乎有点太嘚瑟了，是这样吗？
不是的，条件判断相比于赋值、位运算、算术运算是稍慢的，所以其实有现实意义
但是不需要追求在练算法过程中尽量少写条件判断，那样会带来很多不必要的困扰，还是要写尽量直白、尤其是自己能理解的代码最好（代码可读性、代码编写复杂度与效率之间的权衡）
大牛的实现欣赏完理解就好，下次当模版直接用