二进制算法
2025-05-27 08:06:25
求职指导郭老师
已认证
已认证求职指导郭老师为您分享以下优质知识
关于二进制中1的个数计算，以下是几种常用方法及实现方式：
一、逐位检查法（时间复杂度O（k））
通过逐位与运算判断是否为1，适用于正整数。
示例代码（C++）：
```cpp
int countones(unsigned int n) {
int count = 0;
while (n >
0) {
count += n & 1; // 检查最低位是否为1
n >
>
= 1;// 右移一位
}
return count;
}
```
二、Brian Kernighan算法（时间复杂度O（k））
通过`n &= （n - 1）`操作，每次将最右边的1变为0，直到n为0，统计操作次数。
示例代码（C++）：
```cpp
int countones(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // 将最右边的1变为0
count++;// 统计1的个数
}
return count;
}
```
三、分治法（时间复杂度O（log n））
利用二进制位规律，按位计算每一组数中1的个数，再累加。
示例代码（C++）：
```cpp
int countones(int n) {
int count = 0;
for (int k = 0; k < 32; ++k) { // 假设32位整数
int group_size = 1 >
k; // 完整组数
count += complete_groups * group_size; // 每组1的个数
n &= (1 >
= 1;
}
return count;
}
```
注意事项
数据类型选择：
使用`unsigned int`可避免负数转换时的符号位影响。
效率优化：
Brian Kernighan算法在1的个数较少时效率更高，而分治法在1的分布较均匀时表现更好。
以上方法可根据具体场景选择，例如Brian Kernighan算法适合需要频繁调用且1的分布随机的场景，分治法则更适合需要精确统计的场景。
