【算法篇】从汉明重量的基础理解到高效位运算优化详解

  大家好，我是 展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》
图书作者：《SwiftUI 入门，进阶与实战》
超级个体：COC上海社区主理人
特约讲师：大学讲师，谷歌亚马逊分享嘉宾
科技博主：极星会首批签约作者

摘要

汉明重量是指一个数字的二进制表示中“1”的个数。本文将探讨如何用 Swift 编写高效函数来计算汉明重量。我们将展示代码实现、详细的分析以及优化方法，并通过示例验证其正确性和性能。

描述

给定一个正整数 n，计算其二进制形式中“1”的个数。我们需要设计一个高效的算法，并为高频调用提供优化方案。

示例 1：

输入：n = 11
输出：3
解释：11 的二进制表示为 1011，其中有 3 个“1”。

示例 2：

输入：n = 128
输出：1
解释：128 的二进制表示为 10000000，其中有 1 个“1”。

示例 3：

输入：n = 2147483645
输出：30
解释：2147483645 的二进制表示为 1111111111111111111111111111101，其中有 30 个“1”。

提示：

• 1 <= n <= 2³¹ - 1

进阶：如果多次调用该函数，如何优化算法？

题解答案

核心思路：利用位运算逐位统计“1”的个数。

Swift 题解代码

func hammingWeight(_ n: Int) -> Int {
    var count = 0
    var number = n

    while number > 0 {
        count += number & 1 // 统计最低位是否为 1
        number >>= 1        // 将数字右移一位
    }

    return count
}

代码分析

1. 初始化变量：

   • count：用于统计“1”的个数，初始为 0。
   • number：保存输入值 n。

2. 核心逻辑：

   • 使用 & 运算获取当前数字的最低位，判断是否为 1。
   • 使用右移操作（>>）逐位处理输入数字，直到数字为 0。

3. 返回结果：

   • 当循环结束时，count 即为二进制中“1”的个数。

示例测试及结果

测试代码：

import Foundation

print(hammingWeight(11))        // 输出: 3
print(hammingWeight(128))       // 输出: 1
print(hammingWeight(2147483645)) // 输出: 30

运行结果：

3
1
30

时间复杂度

• 单次调用：每次右移一位，最多需要 32 次操作（32 位整数）。
• 总时间复杂度：O(log(n))（与位数相关的对数复杂度）。

空间复杂度

• 辅助变量：仅使用常量空间（count 和 number）。
• 总空间复杂度：O(1)。

进阶优化

针对多次调用的场景，可以使用预计算表来优化。

优化代码：

var hammingCache: [Int] = (0...255).map { byte in
    var count = 0
    var value = byte
    while value > 0 {
        count += value & 1
        value >>= 1
    }
    return count
}

func hammingWeightOptimized(_ n: Int) -> Int {
    var count = 0
    var number = n

    for _ in 0..<4 {
        count += hammingCache[number & 0xFF] // 处理最低 8 位
        number >>= 8                        // 移除已处理的 8 位
    }

    return count
}

优化思路：

• 使用一个预计算表存储 8 位数字的汉明重量。
• 每次调用时，将输入分为 4 个字节（每字节 8 位）进行查表统计。

总结

1. 使用位运算实现了高效的汉明重量计算。
2. 通过优化方案，可显著提升多次调用场景下的性能。
3. 本文提供的代码简单易懂，适合嵌入不同类型的系统中使用。

未来展望

1. 深入研究硬件级优化（如使用 CPU 指令 POPCNT）。
2. 应用汉明重量计算于更多实际场景，如网络通信、数据压缩。

参考资料

• LeetCode 官方题解
• Swift 位运算指南