40 | 面试题：统计位1的个数-算法面试通关 50 讲

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

### 40 | 面试题：统计位1的个数

在编程面试中，统计一个整数中二进制表示下1的个数是一个常见且富有挑战性的题目。这类问题不仅考察了对位操作（bitwise operations）的掌握程度，还能间接反映出应聘者的逻辑思维能力和问题解决能力。本章节将深入探讨几种不同的方法来解决这一问题，包括位操作法、Brian Kernighan算法（又称“Brian Kernighan's Algorithm”或“n & (n-1)”算法）、查表法以及循环移位法。

#### 一、引言

在计算机科学中，二进制是计算机内部表示数值的基础。一个整数在内存中以二进制形式存储，由0和1组成。统计一个整数二进制表示中1的个数，即二进制中的汉明重量（Hamming Weight），是算法设计中的基础技能之一。

#### 二、位操作法

位操作法是最直观也最常用的方法之一，它依赖于位运算符来遍历整数的每一位，并统计其中的1的个数。位运算符主要包括按位与（&）、按位或（|）、按位异或（^）、按位取反（~）、左移（<<）和右移（>>）。

**实现思路**：

1. 将整数与1进行按位与操作（`n & 1`），判断最低位是否为1。
2. 将整数右移一位（`n >>= 1`），继续判断次低位，重复上述步骤直到整数变为0。

**示例代码**（C++）：

```cpp
int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
```

这种方法的时间复杂度是O(k)，其中k是整数n中1的个数，因为最坏情况下需要遍历每一位。空间复杂度是O(1)，因为它只使用了常数个变量。

#### 三、Brian Kernighan算法

Brian Kernighan算法是一种更高效的方法，它基于一个观察：一个数`n`与其减一（`n-1`）进行按位与操作的结果，会将`n`中最右边的1变为0。通过不断重复这个过程，直到`n`变为0，就可以统计出`n`中1的个数。

**实现思路**：

1. 初始化计数器`count`为0。
2. 当`n`不为0时，执行`n = n & (n-1)`，并将`count`加1。
3. 重复步骤2，直到`n`变为0。

**示例代码**（C++）：

```cpp
int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}
```

Brian Kernighan算法的时间复杂度同样是O(k)，但由于每次操作都能消除一个1，因此在平均情况下比简单的位操作法更有效率。空间复杂度同样是O(1)。

#### 四、查表法

查表法是一种空间换时间的策略，适用于对性能有极高要求且整数范围相对较小的场景。基本思路是预先计算并存储所有可能整数的1的个数，然后在需要时直接查表获取结果。

**实现思路**：

1. 定义一个足够大的数组或哈希表，用于存储每个整数对应的1的个数。
2. 遍历整数范围，对每个整数使用位操作法或Brian Kernighan算法计算其1的个数，并存储在数组中。
3. 在实际查询时，直接根据整数索引数组获取结果。

**注意**：由于这种方法需要存储大量的数据，因此在实际应用中可能受到内存限制。

#### 五、循环移位法

循环移位法是一种不太常见的思路，它基于将整数与一系列掩码进行按位与操作，然后统计结果中1的个数。这种方法通常与特定的硬件或优化技巧相结合，以达到特定的性能目标。

**基本思路**：

1. 设计一系列掩码，每个掩码在二进制表示下只有一位是1（例如，0001, 0010, 0100...）。
2. 将整数与每个掩码进行按位与操作，统计结果中1的个数。
3. 将所有统计结果相加，得到整数中1的总数。

**示例**（概念性描述，非具体实现）：

虽然循环移位法在实际面试中不常见，但它展示了通过精心设计的位操作来解决复杂问题的能力。

#### 六、总结

统计一个整数中二进制表示下1的个数是编程面试中的一个经典问题，它考察了应聘者对位操作的掌握程度以及解决问题的能力。本文介绍了四种不同的解决方法：位操作法、Brian Kernighan算法、查表法和循环移位法。每种方法都有其独特的优势和适用场景，选择合适的方法需要根据实际问题的需求和约束条件来决定。

在实际应用中，位操作法和Brian Kernighan算法因其简洁性和高效性而被广泛使用。查表法虽然能在某些特定场景下提供更快的查询速度，但受限于内存空间的限制。循环移位法则更多地作为一种理论上的探讨，展示了位操作的灵活性和创造性。

通过学习和掌握这些方法，不仅可以提升自己在编程面试中的竞争力，还能在解决实际问题时拥有更多的选择和思路。

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

业务开发实用算法精讲

数据结构与算法(下)

数据结构与算法之美

数据结构与算法(中)

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

数据结构与算法(上)

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