位运算经典题解
在计算机世界里，位运算有着独特的高效魅力，今天就来聊聊 LeetCode 上三道围绕位运算展开的经典题目：位1的个数、汉明距离、比特位计数 ，带大家剖析解题思路，感受位运算的巧妙 。
一、位1的个数（LeetCode 191）
题目理解
给定一个正整数 n ，要统计它的二进制表示中 1 的个数，也就是汉明重量。比如 n = 11 （二进制 1011 ），结果就是 3 。
核心思路
利用位运算的小技巧： n & (n - 1) 会把 n 二进制中最右边的 1 变成 0 。举个例子， n = 11 （ 1011 ）， n - 1 = 10 （ 1010 ）， n & (n - 1) = 1010 （ 10 ），这就消去了最右边的 1 。循环执行这个操作，每消去一个 1 就计数，直到 n 变成 0 ，计数结果就是二进制中 1 的个数 。
代码实现（C++）
class Solution {
public:int hammingWeight(int n) {int count = 0;while (n != 0) {count++;n &= (n - 1);}return count;}
};
二、汉明距离（LeetCode 461）
题目理解
两个整数 x 和 y ，汉明距离是它们二进制对应位不同的位置数目。比如 x = 1 （ 0001 ）， y = 4 （ 0100 ），不同的位置有 2 处，汉明距离就是 2 。
核心思路
第一步，用 x ^ y 得到一个新数 tmp ，这个操作会把 x 和 y 二进制中不同的位变成 1 ，相同的位变成 0 。比如 x = 1 （ 0001 ）， y = 4 （ 0100 ）， x ^ y = 0101 ，这里面 1 的个数就是汉明距离。接下来，就转化成了和“位1的个数”一样的问题，用 tmp & (tmp - 1) 循环消去 1 并计数即可 。
代码实现（C++）
class Solution {
public:int hammingDistance(int x, int y) {int tmp = x ^ y;int count = 0;while (tmp) {tmp &= (tmp - 1);count++;}return count;}
};
三、比特位计数（LeetCode 338）
题目理解
给定整数 n ，要返回一个长度为 n + 1 的数组 ans ，其中 ans[i] 是 i 的二进制表示中 1 的个数。比如 n = 2 时，数组是 [0,1,1] ，对应 0 （ 0 ）、 1 （ 1 ）、 2 （ 10 ）的 1 个数 。
核心思路
最直接的做法是对每个 i （从 0 到 n ），都用“位1的个数”的方法统计 1 的数量。也就是遍历每个数，内部用 while 循环和 i & (i - 1) 操作来计数。这种方法简单直观，时间复杂度是 O(n log n) ，对于题目中 n <= 10^5 的范围，也能顺利通过 。
代码实现（C++）
class Solution {
public:vector<int> countBits(int n) {vector<int> v(n + 1, 0);for (int i = 1; i <= n; i++) {int temp = i;int count = 0;while (temp) {temp &= (temp - 1);count++;}v[i] = count;}return v;}
};
四、总结
这三道题都围绕二进制中 1 的个数统计展开，核心技巧就是 n & (n - 1) 消去最右边 1 的操作 。从单一数字的 1 个数统计（位1的个数），到两个数字基于异或后的 1 个数统计（汉明距离），再到批量数字的 1 个数统计（比特位计数），层层递进，帮我们深入理解位运算在这类问题里的应用 。
掌握了这个小技巧，遇到类似统计二进制位特征的题目，就能快速想到解题思路啦，大家快去刷题实践一下吧～