41 | 面试题：2的幂次方问题&比特位计数问题-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 41 | 面试题：2的幂次方问题 & 比特位计数问题

在算法面试中，处理与位操作相关的问题不仅考验着面试者的基础知识掌握程度，还体现了其解决问题的灵活性和对计算机底层原理的理解。本章将深入探讨两个经典的面试问题：判断一个数是否为2的幂次方，以及计算一个整数的比特位（二进制位）中1的个数。这两个问题虽然看似简单，但背后蕴含了丰富的位操作技巧和数学原理。

#### 41.1 判断一个数是否为2的幂次方

**问题描述**：
给定一个整数`n`，判断它是否是2的幂次方。换句话说，我们需要检查是否存在一个整数`x`，使得`n == 2^x`。

**解决方案一：迭代法**

最直观的方法是通过迭代不断除以2，直到结果为1或不再为整数（即出现小数或0）。但这种方法在编程中不够优雅，且可能涉及浮点数的比较，存在精度问题。

**解决方案二：位操作法**

利用位操作，我们可以发现2的幂次方在二进制表示中有一个显著特点：只有一个比特位是1，其余都是0。例如，`2^0 = 1`（二进制`0001`），`2^1 = 2`（二进制`0010`），`2^2 = 4`（二进制`0100`）等。基于这个特性，我们可以使用`(n & (n - 1))`来判断。如果`n`是2的幂次方，则`n - 1`的二进制表示中最低位的1会变成0，并且原本为0的位会变成1，这样与`n`进行按位与操作的结果必然是0。反之，如果`n`不是2的幂次方，则`(n & (n - 1))`的结果不为0。

```python
def isPowerOfTwo(n):
    if n <= 0:
        return False
    return (n & (n - 1)) == 0
```

**复杂度分析**：
- 时间复杂度：O(1)，因为只进行了常数次操作。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。

#### 41.2 计算一个整数的比特位中1的个数

**问题描述**：
编写一个函数，输入是一个无符号整数（以32位为例），你需要计算并返回该整数二进制表示中1的个数（也被称为汉明重量）。

**解决方案一：逐位检查法**

最直观的方法是遍历整数的每一位，检查是否为1。但这种方法效率低下，因为它需要遍历整数的每一位。

**解决方案二：Brian Kernighan算法**

Brian Kernighan算法（也称为Brian Kernighan's Algorithm或n & (n-1)算法）是一种高效的计算整数中1的个数的位操作方法。该算法的基本思想是通过每次操作消除最低位的1，并计数，直到整数变为0。具体来说，每次将整数`n`与其自身减1的结果进行按位与操作（`n & (n - 1)`），这样可以消除`n`中最低位的1。重复此过程，直到`n`变为0，计数次数即为1的个数。

```python
def hammingWeight(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count
```

**解决方案三：位操作技巧**

另一种高效的方法是利用位操作技巧。我们可以将整数`n`与一系列的掩码进行按位与操作，每个掩码只在其一个位上为1，其余位都为0。通过统计与这些掩码进行按位与操作后结果为非零的次数，即可得到1的个数。但这种方法相比Brian Kernighan算法，在理解和实现上稍显复杂，且效率上并不占优势。

还有一种更简洁的位操作方法，利用`n & -n`的性质。对于任意正整数`n`，`-n`的二进制表示是`n`的二进制表示取反后加1。这样，`n & -n`的结果就是`n`二进制表示中最低位的1及其后面的所有0（如果有的话）。通过不断移除这个最低位的1，并计数，同样可以计算出1的个数。

```python
def hammingWeight_optimized(n):
    count = 0
    while n:
        n &= -n
        count += 1
        n -= 1
    return count

# 注意：上面的优化版本实际上并不比Brian Kernighan算法更优，因为每次循环都进行了两次操作。
# 更常见的优化版本是只利用 n &= -n 来迭代，如下所示：

def hammingWeight_optimized_v2(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

# 这与Brian Kernighan算法本质上是相同的。

**复杂度分析**（针对Brian Kernighan算法和等效优化版本）：
- 时间复杂度：O(k)，其中k是整数`n`中1的个数。在最坏情况下（即`n`是`2^m - 1`，其中m是整数的位数），时间复杂度为O(m)，但对于大多数实际应用场景，k远小于m。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。

#### 总结

通过解决这两个问题，我们不仅掌握了位操作的基本技巧，还深入理解了2的幂次方在二进制表示中的特殊性质，以及如何利用这些性质来高效解决问题。在面试中，能够灵活运用位操作解决问题，往往能展现出面试者深厚的编程功底和对计算机底层原理的深刻理解。

该分类下的相关小册推荐：

业务开发实用算法精讲

数据结构与算法之美

编程之道-算法面试(下)

编程之道-算法面试(上)

数据结构与算法(上)

数据结构与算法(下)

数据结构与算法(中)