题目
题目链接
解题思路
计算32位整数二进制表示中1的个数，有几种常用方法：
位运算法：
使用 \(\text{n} \& \text{1}\) 判断最低位是否为1
右移 \(\text{n}\)，继续判断
统计所有为1的位
n & (n-1) 法：
每次操作会消除最右边的1
统计操作次数即为1的个数
这种方法更高效，因为只需要处理1的个数次
查表法：
预处理所有8位数的1的个数
将32位数分成4个8位处理
适合处理大量数据
代码
#include
using namespace std;
class Solution {
public:
// 方法1：位运算统计
int countOnes1(int n) {
int count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}
// 方法2：n & (n-1)
int countOnes2(int n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
};
int main() {
int n;
cin >> n;
Solution solution;
cout << solution.countOnes2(n) << endl;
return 0;
}
import java.util.*;
public class Main {
static class Solution {
// 方法1：位运算统计
public int countOnes1(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1; // 使用无符号右移
}
return count;
}
// 方法2：n & (n-1)
public int countOnes2(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Solution solution = new Solution();
System.out.println(solution.countOnes2(n));
}
}
def count_ones_1(n: int) -> int:
"""方法1：位运算统计"""
count = 0
while n:
count += n & 1
n >>= 1
return count
def count_ones_2(n: int) -> int:
"""方法2：n & (n-1)"""
count = 0
while n:
n &= (n - 1)
count += 1
return count
if __name__ == "__main__":
n = int(input())
print(count_ones_2(n))
算法及复杂度
算法：位运算
时间复杂度：
方法1：\(\mathcal{O}(32)\) = \(\mathcal{O}(1)\)
方法2：\(\mathcal{O}(k)\)，\(k\) 为1的个数
空间复杂度：\(\mathcal{O}(1)\)