跳转至

位运算算法详解

位操作（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 == 2^x ，则认为 n 是 2 的幂次方。

示例 1：

**输入：**n = 1 **输出：**true **解释：**2^0 = 1 

**示例 2：**

**输入：**n = 16
**输出：**true
**解释：**2^4 = 16

示例 3：

**输入：**n = 3 **输出：**false 

**示例 4：**

**输入：**n = 4
**输出：**true

示例 5：

**输入：**n = 5 **输出：**false 

**提示：**

- <code>-2^31 <= n <= 2^31 - 1</code>

**进阶：**你能够不使用循环/递归解决此问题吗？

```go
func isPowerOfTwo(n int) bool {
    return n > 0 && n&(n-1) == 0
}


func isPowerOfTwo(n int) bool {
    return n > 0 && n&-n == n
}

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$。

```go
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\) 的个数。

func hammingWeight(num uint32) (ones int) {
    for ; num > 0; num &= num - 1 {
        ones++
    }
    return
}

评论