企业官网建设流程全解析

LeetCode 191 Number of 1 Bits 题解：用n & (n - 1)位运算统计二进制中 1 的个数（汉明重量）

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇文章基于开源仓库 leetcode 中的 191.number-of-1-bits.en.md 展开。题目要求统计一个无符号整数的二进制表达式中1的个数，也就是经典的**汉明重量（Hamming Weight）**问题。读完本文，你将掌握n & (n - 1)这一消除最低位1的核心位运算技巧、多语言实现（JS / C++ / Python / Java）、复杂度分析方法，以及基于掩码分治的 O(1) 常数时间扩展解法，并能在实际面试与工程场景中举一反三。

题目描述

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为1的个数（也被称为汉明重量）。

示例 1

输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2

输入：00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3

输入：11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。在 Java 中，编译器使用二进制补码记法来表示有符号整数，因此在示例 3 中，输入实际表示的是有符号整数-3。

进阶

如果这个函数会被多次调用，你将如何优化算法？

前置知识

本题目属于典型的位运算（Bit Operation）问题。仓库在 thinkings/bit.md 中系统整理了位运算套路，并以 136、137、260、645 等题目为例讲解了异或的性质与用法：

• 异或运算：a ^ b按位计算，相同为 0、不同为 1；
• 任何数与自身异或为0，任何数与0异或为自身；
• 异或满足交换律：a ^ b ^ c = a ^ c ^ b。

在阅读本篇文章之前，建议先熟悉二进制的位与（&）、位或（|）、左移（<<）、右移（>>）等基础位运算，这对理解后面消除1的原理与分治掩码扩展会很有帮助。该题在 collections/easy.en.md 中被收录为简单题，可见其解法思路直观、代码量小，但背后的位运算原理却非常值得深挖。

核心思路：n & (n - 1)消除最低位的 1

这个题目的大意是：给定一个无符号整数，返回其用二进制表示时1的个数。

最朴素的想法是逐位检查（例如 Java 解法中常见的n & (1 << i)循环 32 次），但这里有一个经典的 trick，可以非常优雅地求解——n & (n - 1)可以消除n最低位（最右边）的那一个1。

为什么能消除最后一个1？原理其实比较简单：

• 当n的二进制末位为1（即n为奇数）时，n - 1只是把末位的1变成0，其余位不变，两者相与后末位归零，其余位保持原样，等价于把最低位的1清零；
• 当n的二进制末位为0（即n为偶数）时，n - 1需要向低位连续借位，其效果是：从最低位开始，直到遇到第一个1为止，低位连续的0全部变为1，而那个1变为0。此时n & (n - 1)恰好把从低到高第一个1及其更低位的所有位全部清零。

例如n = 12，二进制为1100，则n - 1 = 11，二进制为1011，两者相与得到1000，即8。可以看到1100中最低位的那个1（从右往左第三位）被消除，同时更低位也全部归零。

基于这一原理，我们可以不断执行：

n = n & (n - 1)

直到n === 0，说明已经没有一个1了。此时我们消除了多少个1，就说明n原本有多少个1——每次迭代消除恰好一个1，因此循环次数就等于答案本身。

关键点解析

1. n & (n - 1)消除最低位 1 的原理：这是整个题目的灵魂，利用它可以直接把循环次数从"32 次"降为"二进制中 1 的个数"次，显著简化操作；
2. 位运算思维：遇到数字统计、二进制相关问题，优先考虑位运算方案，往往能获得比字符串转换或逐位移位更简洁的实现。

代码实现

原文档在 191.number-of-1-bits.en.md 中给出了 JS、C++、Python 三种语言的实现，仓库中文版 191.number-of-1-bits.md 还补充了 Java 逐位检查版本，这里一并收录。

JavaScript

/* * @lc app=leetcode id=191 lang=javascript * */ /** * @param {number} n - a positive integer * @return {number} */ var hammingWeight = function (n) { let count = 0; while (n !== 0) { n = n & (n - 1); count++; } return count; };

C++

class Solution { public: int hammingWeight(uint32_t v) { auto count = 0; while (v != 0) { v &= (v - 1); ++count; } return count; } };

注意 C++ 版本将参数类型声明为uint32_t，直接利用无符号整型的语义，无需关心符号位的干扰。

Python

class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ count = 0 while n: n &= n - 1 count += 1 return count

Python 中while n在n为0时自动结束循环，代码非常简洁。

Java（逐位检查）

public class Solution { public int hammingWeight(int n) { int count = 0; for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { count++; } } return count; } }

Java 版本使用n & (1 << i)依次检查 32 个二进制位，体现了"逐位统计"的基础思路，其循环次数固定为 32 次。

复杂度分析

• 时间复杂度：原文档标注为 $O(logN)$。更准确地说，基于n & (n - 1)的解法循环次数等于二进制中1的个数（记为 $k$），最坏情况下（如n = 0xFFFFFFFF）$k = 32$；在 32 位整数的前提下，也可以理解为常数时间内可完成（$O(1)$）。相比固定循环 32 次的逐位检查法，当输入中1较少时效率明显更高。
• 空间复杂度：原文档标注为 $O(N)$。从上述所有实现看，循环内仅使用一个计数变量，未申请任何与输入规模相关的额外存储，实际空间复杂度应为 $O(1)$，原文档的 $O(N)$ 应视为笔误。

扩展：利用掩码分治的常数时间解法

除了迭代消除1，还可以使用位操作分治（也称 SWAR，SIMD Within A Register）在常数时间内完成统计，这也是"进阶：多次调用时如何优化"的一种重要思路。原文档以 8 位的整数21（二进制00010101）为例演示了这种分治统计过程。

其核心思想是：先统计相邻 1 位中的1的个数（结果用 2 位二进制表示），再统计相邻 2 位中的1的个数（结果用 4 位二进制表示），以此类推，每轮将相邻块合并，最终得到整个 32 位整数中1的总数。每一轮只需要常数次位与、移位和加法，因此整体是 $O(1)$ 时间，且不依赖输入中1的个数，非常适合被高频反复调用。

C++ 代码如下（来自 191.number-of-1-bits.en.md）：

const uint32_t ODD_BIT_MASK = 0xAAAAAAAA; const uint32_t EVEN_BIT_MASK = 0x55555555; const uint32_t ODD_2BIT_MASK = 0xCCCCCCCC; const uint32_t EVEN_2BIT_MASK = 0x33333333; const uint32_t ODD_4BIT_MASK = 0xF0F0F0F0; const uint32_t EVEN_4BIT_MASK = 0x0F0F0F0F; const uint32_t ODD_8BIT_MASK = 0xFF00FF00; const uint32_t EVEN_8BIT_MASK = 0x00FF00FF; const uint32_t ODD_16BIT_MASK = 0xFFFF0000; const uint32_t EVEN_16BIT_MASK = 0x0000FFFF; class Solution { public: int hammingWeight(uint32_t v) { v = (v & EVEN_BIT_MASK) + ((v & ODD_BIT_MASK) >> 1); v = (v & EVEN_2BIT_MASK) + ((v & ODD_2BIT_MASK) >> 2); v = (v & EVEN_4BIT_MASK) + ((v & ODD_4BIT_MASK) >> 4); v = (v & EVEN_8BIT_MASK) + ((v & ODD_8BIT_MASK) >> 8); return (v & EVEN_16BIT_MASK) + ((v & ODD_16BIT_MASK) >> 16); } };

各掩码的作用：

• 0x55555555（0101...）：保留偶数位（从 0 开始计），用于统计相邻 1 位的和；
• 0xAAAAAAAA（1010...）：保留奇数位，配合右移 1 位后与偶数位相加，得到每 2 位内的1个数；
• 0x33333333、0xCCCCCCCC、0x0F0F0F0F、0xF0F0F0F0等依次将统计粒度从 2 位扩展到 4 位、8 位、16 位，直到合并出完整的 32 位结果。

进阶问题的进一步思考

题目结尾提出"如果多次调用这个函数，你将如何优化算法？"针对这一进阶场景，除了上述分治（SWAR）常数时间方案外，还可以考虑：

1. 查表法：将 8 位（或 16 位）整数的汉明重量预先存入查找表，统计 32 位整数时拆成 4 个（或 2 个）字节查表求和。预计算一次、查询无数次，适合海量重复调用的场景；
2. 分治（SWAR）：如上文 C++ 实现，每轮并行统计相邻块内的1，固定迭代次数，无循环、无查表，指令级开销极低。

从仓库源码结构看，本题位于 collections/easy.en.md 的简单题列表，且 SUMMARY.md 将其收录在"位运算"专题之下，与 190.reverse-bits.md（颠倒二进制位）、201（数字范围按位与）、898（子数组按位或）等题目共同构成位运算练习主线。建议在掌握本题的n & (n - 1)技巧后，继续练习 190.reverse-bits.md，该题同样运用了位运算的掩码分治扩展（相邻 1 位交换、2 位交换、4 位交换……直至 16 位交换），两题互为镜像、相互印证，可以一举吃透位运算的常见套路。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode