统计二进制数中 1 的个数
这个任务常常出现在哈希函数、数据压缩、权限管理等场景中
代码示例
一、逐位判断
int bitCount(unsigned int n) {
unsigned int c = 0;
int i;
for (i = 0; i < sizeof(n) * 8; ++i) {
c += (n >> i) & 1; // 右移 i 位并与 1 做与操作，检查当前位是否为 1
}
return c;
}解释
n >> i：将 n 右移 i 位，将目标位移到最低位
& 1：通过与操作判断当前最低位是否为 1
c += (n >> i) & 1;：如果当前位是 1，就加 1 到计数器 c 中
举例
n = 13，逐位判断的过程
- i = 0:
(13 >> 0) & 1 = 1101 & 0001 = 1→ 1 被加到c - i = 1:
(13 >> 1) & 1 = 1101 >> 1 = 0110 & 0001 = 0→ 0 被加到c - i = 2:
(13 >> 2) & 1 = 1101 >> 2 = 0011 & 0001 = 1→ 1 被加到c - i = 3:
(13 >> 3) & 1 = 1101 >> 3 = 0001 & 0001 = 1→ 1 被加到c - i = 4 to 31: 由于这些位都是 0，因此每次
& 1的结果都为 0
最终 c = 3，表示数字 13 中有 3 个 1
二、n &= (n - 1)
int bitCount(unsigned int n) {
unsigned int c;
for (c = 0; n; ++c) {
n &= (n - 1); // 清除最低位的1
}
return c;
}- 不断清除 n 的二进制表示中最右边的 1，同时累加计数器，直至 n 为 0
- 比起逐位判断（例如
n >> i & 1），这种写法更高效
举例
n = 13，二进制表示为 1101，可以通过这个过程逐步清除最低位的 1：
- 第一次，
n = 1101，n - 1 = 1100，n &= (n - 1)结果是1100，清除了最右边的1 - 第二次，
n = 1100，n - 1 = 1011，n &= (n - 1)结果是1000 - 第三次，
n = 1000，n - 1 = 0111，n &= (n - 1)结果是0000
最终，n 变为 0，共清除 3 次，表示数字 13 中有 3 个 1
运算次数与输入 n 的大小无关，只与 n 中 1 的个数有关
这是位操作中非常高效的技巧之一，用于 计数、布隆过滤器、掩码处理 等多种场景
三、GCC __builtin_popcount
通常编译器会优化成高效的机器指令（如
POPCNT）
#include <stdio.h>
int main() {
unsigned int x =13;
printf("Number of 1 in %u (binary: %08b): %d\n", x,x, __builtin_popcount(x));
return 0;
}GCC 还提供了用于不同整数类型的版本：
| 函数名 | 类型 |
|---|---|
__builtin_popcount(x) |
unsigned int |
__builtin_popcountl(x) |
unsigned long |
__builtin_popcountll(x) |
unsigned long long |
性能比较
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 手动实现 popcount
int popcount_manual(unsigned int n) {
int count = 0;
while (n) {
n &= (n - 1); // 清除最低位的 1
count++;
}
return count;
}
int main() {
unsigned int number = 0b1101010110110101; // 16 位数（含 10 个 1）
// 比较性能的循环次数
int iterations = 10000000;
// 测量 __builtin_popcount 的时间
clock_t start = clock();
for (int i = 0; i < iterations; i++) {
__builtin_popcount(number);
}
clock_t end = clock();
double builtin_time = ((double)(end - start)) / CLOCKS_PER_SEC;
// 测量手动实现的时间
start = clock();
for (int i = 0; i < iterations; i++) {
popcount_manual(number);
}
end = clock();
double manual_time = ((double)(end - start)) / CLOCKS_PER_SEC;
// 输出时间对比结果
printf("Time taken by __builtin_popcount: %.6f seconds\n", builtin_time);
printf("Time taken by popcount_manual: %.6f seconds\n", manual_time);
return 0;
}Time taken by __builtin_popcount: 0.003116 seconds
Time taken by popcount_manual: 0.049420 seconds位操作其他技巧
一、1 的相关技巧（统计、掩码）
| 技巧 | 说明 | 示例或表达式 |
|---|---|---|
| 清除最低位的 1 | n & (n - 1)：把最右边的 1 变成 0 |
n = 0b10100 → n & (n - 1) = 0b10000 |
| 只保留最低位的 1 | n & -n 或 n & (~n + 1) |
提取最右边的 1 |
| 判断是否是 2 的幂 | n > 0 && (n & (n - 1)) == 0 |
只有一个 1 的数字 |
| 统计 1 的个数（位计数） | __builtin_popcount(n)（GCC）或用循环清 1 |
|
| 找最高位的 1 的位置 | 31 - __builtin_clz(n)（GCC） |
CLZ = Count Leading Zeros |
| 找最低位的 1 的位置 | __builtin_ctz(n)（GCC） |
CTZ = Count Trailing Zeros |
二、加减乘除相关（通常用于优化）
| 技巧 | 等价于 | 示例 |
|---|---|---|
| 乘以 2 的幂 | x << n |
x * 2^n |
| 除以 2 的幂（向下取整） | x >> n |
x / 2^n |
| 模 2 的幂（取低位） | x & (2^n - 1) |
x % 2^n |
| 交换两个数不用中间变量 | x ^= y; y ^= x; x ^= y; |
适用于整数 |
三、掩码与位操作常见应用
| 功能 | 表达式或方法 | 说明 |
|---|---|---|
| 设置第 k 位为 1 | n | (1 << k) |
将一个 1 移动到目标位 k，然后与原数进行按位或 |
| 清除第 k 位为 0 | n &= ~(1 << k) |
|
| 翻转第 k 位 | n ^= (1 << k) |
|
| 测试第 k 位是否为 1 | (n >> k) & 1 或 (n & (1 << k)) != 0 |
|
| 只保留前 n 位 | n &= (1 << k) - 1 |
清除高位 |
四、奇偶性判断
| 表达式 | 说明 |
|---|---|
x & 1 |
判断奇偶：1 是奇数，0 是偶数 |
x ^ 1 |
切换奇偶：偶数变奇数，奇数变偶数 |
五、位图法（Bitset/Bitmap）
当你要记录大规模的布尔标志（如是否出现过），可以用位图：
unsigned int bitmap[1000]; // 每个 int 存 32 个布尔值
// 设置第 k 个元素为 1
bitmap[k / 32] |= (1 << (k % 32));
// 查询是否为 1
bool exist = bitmap[k / 32] & (1 << (k % 32));比 bool array[32000] 少用很多内存！
六、快速幂与其他优化技巧
- 幂优化：用快速幂算法实现
a^b mod m，经常用在加密、哈希等领域 - 反码 / 补码：理解
~x + 1是-x，用于实现取负数 - 整除奇偶优化：比如判断是否是 4 的倍数
x & 3 == 0
📌 小结：位操作常见应用场景
- 快速统计（如计数、权限组合）
- 高效布尔数组（如素数筛、哈希）
- 数据压缩、空间优化
- 状态压缩（如动态规划中的状态编码）
- 字符串哈希 / rolling hash
- 多线程锁结构（比如原子变量标记）
其他场景应用（如图像处理、操作系统内核、密码学、编译器等）