位运算
位操作（Bit Manipulation）是程序设计中对位模式或二进制数的一元和二元操作。在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。在现代编程语言中，情况并非如此，很多编程语言的解释器都会基本的运算进行了优化，因此我们在实际开发中可以不必做一些编译器已经帮我们做好的优化，而就写出代码本身所要表现的意思。
基本操作：
- 按位与 \(&\)
- 按位或 \(|\)
- 按位取反 ~ （注意负数补码符号，第一位是 1）
- 异或 \(^\)
- 左移 \(<<\)
- 右移 \(>>\)
优先级
取反 > 算术 > 左移/右移 > 关系运算 > 与 > 或 > 异或 > 逻辑运算
| 功能 | 示例 | 位运算 |
|---|---|---|
| 去掉末位 | (101101->10110) | x >> 1 |
| 在末尾加 0 | (101101->1011010) | x << 1 |
| 在末尾加 1 | (101101->1011011) | (x << 1) + 1 |
| 末位置 1 | (101100->101101) | x | 1 |
| 末位置 0 | (101101->101100) | (x | 1) - 1 |
| 末位取反 | (101101->101100) | x ^ 1 |
| 从右数 k 位置 1 | (101001->101101, k = 3) | x | (1 << (k - 1)) |
| 从右数 k 位置 0 | (101101->101001, k = 3) | x & ~(1 << (k - 1)) |
| 从右数第 k 位取反 | (101001->101101, k = 3) | x ^ (1 << (k - 1)) |
| 取末尾 3 位 | (101101->101, k = 3) | x & 7 |
| 取末尾 k 位 | (101101->1101, k = 4) | x & (1 << (k - 1)) |
| 取从右数第 k 位 | (101101->1, k = 4) | x >> (k - 1) & 1 |
| 末尾 k 位置 1 | (101101->101111, k = 4) | x | (1 << (k - 1)) |
| 末尾 k 位取反 | (101101->100010, k = 4) | x ^ (1 << (k - 1)) |
| 把右边连续的 1 置 0 | (101101111->101100000) | x & (x + 1) |
| 把右边连续的第一个 0 置 1 | (101101111->101111111) | x | (x + 1) |
| 把右边连续 0 置 1 | (101100->101111) | x | (x - 1) |
| 取右边连续的 1 | (101101111->1111) | (x ^ (x + 1)) >> 1 |
| 去掉右边第一个 1 的左边 | (100101000->1000) | x & (x ^ (x - 1))） |
例题
231 2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1 输出：true 解释：20 = 1
示例 2：
输入：n = 16 输出：true 解释：24 = 16
示例 3：
输入：n = 3 输出：false
示例 4：
输入：n = 4 输出：true
示例 5：
输入：n = 5 输出：false
提示：
-231 <= n <= 231 - 1
进阶：你能够不使用循环/递归解决此问题吗？
191 位 1 的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数
-3。
示例 1：
输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：n = 00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：n = 11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
- 输入必须是长度为
32的 二进制串 。
进阶：
- 如果多次调用这个函数，你将如何优化你的算法？
思路及解法
我们可以直接循环检查给定整数 \(n\) 的二进制位的每一位是否为 \(1\)。
具体代码中，当检查第 \(i\) 位时，我们可以让 \(n\) 与 \(2^i\) 进行与运算，当且仅当 \(n\) 的第 \(i\) 位为 \(1\) 时，运算结果不为 \(0\)。
func hammingWeight(num uint32) (ones int) {
for i := 0; i < 32; i++ {
if 1<<i&num > 0 {
ones++
}
}
return
}
观察这个运算：\(n~\&~(n - 1)\)，其运算结果恰为把 \(n\) 的二进制位中的最低位的 \(1\) 变为 \(0\) 之后的结果。
如：\(6~\&~(6-1) = 4, 6 = (110)_2, 4 = (100)_2\)，运算结果 \(4\) 即为把 \(6\) 的二进制位中的最低位的 \(1\) 变为 \(0\) 之后的结果。
这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的 \(n\) 与 \(n - 1\) 做与运算，直到 \(n\) 变为 \(0\) 即可。因为每次运算会使得 \(n\) 的最低位的 \(1\) 被翻转，因此运算次数就等于 \(n\) 的二进制位中 \(1\) 的个数。