好的，各位朋友们，大家好！今天咱们来聊聊一个稍微有点“底层”，但绝对能让你代码跑得飞快的东东：C++ 的 __builtin_popcount 以及其他类似的内置函数，它们背后的秘密是 CPU 硬件指令加速位操作。
啥是位操作？（别告诉我你不知道！）
首先，咱们得明确一下啥是位操作。简单来说，就是直接对二进制位进行操作。比如：
- 按位与 (&):
a & b，对应位都为 1 时结果才为 1。 - 按位或 (|):
a | b，对应位只要有一个为 1 结果就为 1。 - 按位异或 (^):
a ^ b，对应位不同时结果为 1。 - 按位取反 (~):
~a，每一位取反。 - 左移 (<<):
a << n，所有位向左移动 n 位。 - 右移 (>>):
a >> n，所有位向右移动 n 位。
这些玩意儿看起来简单，但在某些场景下却非常有用，比如：
- 集合表示： 可以用一个整数的每一位来表示集合中是否存在某个元素。
- 状态压缩： 在动态规划中，可以用位来表示状态。
- 图像处理： 某些图像操作可以直接在位级别进行。
- 密码学： 位操作是很多密码算法的基础。
为啥位操作很重要？（快！更快！还要更快！）
传统的位操作，比如循环遍历每一位来计数，效率相对较低。想象一下，你要数一个 32 位整数里面有多少个 1，难道真的要循环 32 次？这太浪费时间了！尤其是在对性能要求很高的场景下，每一毫秒都至关重要。
这时候，__builtin_popcount 就闪亮登场了！
__builtin_popcount：数数有几个 1（高效版）
__builtin_popcount(x) 是 GCC 和 Clang 编译器提供的内置函数，它的作用是计算一个无符号整数 x 的二进制表示中 1 的个数（也叫汉明重量）。
重点来了： __builtin_popcount 通常不是通过软件实现的，而是直接利用 CPU 提供的硬件指令。这意味着，它比你手写的循环快得多！
例子：
#include <iostream>
int main() {
unsigned int num = 0b10110010101010111100010101010110; // 一个32位整数
int count = __builtin_popcount(num);
std::cout << "Number of set bits: " << count << std::endl; // 输出：20
return 0;
}这段代码会直接调用 CPU 对应的指令来计算 num 中 1 的个数，效率极高。
其他类似的内置函数
除了 __builtin_popcount，还有一些类似的内置函数，它们也利用了 CPU 的硬件指令来加速位操作：
__builtin_clz(x)：Count Leading Zeros，计算一个无符号整数x二进制表示中，从最高位开始连续 0 的个数。如果x为 0，结果未定义。__builtin_ctz(x)：Count Trailing Zeros，计算一个无符号整数x二进制表示中，从最低位开始连续 0 的个数。如果x为 0，结果未定义。__builtin_ffs(x)：Find First Set，返回一个整数x二进制表示中，最低位的 1 的位置（从 1 开始计数）。如果x为 0，返回 0。__builtin_parity(x)：计算一个无符号整数x的二进制表示中 1 的个数的奇偶性。如果 1 的个数为奇数，返回 1，否则返回 0。
代码演示：
#include <iostream>
int main() {
unsigned int num = 0b00001000; // 8
std::cout << "__builtin_clz(num): " << __builtin_clz(num) << std::endl; // 输出：28 (32 - 4)
std::cout << "__builtin_ctz(num): " << __builtin_ctz(num) << std::endl; // 输出：3
std::cout << "__builtin_ffs(num): " << __builtin_ffs(num) << std::endl; // 输出：4
unsigned int num2 = 0b10110; //22
std::cout << "__builtin_parity(num2): " << __builtin_parity(num2) << std::endl; // 输出：0
return 0;
}背后的硬件指令：别眨眼，有点枯燥！
这些内置函数之所以快，是因为编译器会把它们转换成对应的 CPU 指令。不同的 CPU 架构可能有不同的指令集，但通常都会提供专门的指令来执行这些位操作。
- POPCNT (Population Count): 这是专门用于计算 1 的个数的指令。Intel 在 SSE4.2 指令集中引入了 POPCNT 指令。AMD 也在某些 CPU 中支持。
- BSR/BSF (Bit Scan Reverse/Forward): 用于查找最高位/最低位的 1。
- LZCNT (Leading Zero Count): 用于计算前导零的个数。
这些指令都是由 CPU 硬件直接执行的，速度远快于软件模拟。
编译器做了什么？（魔法！）
编译器会根据你的 CPU 架构，自动选择合适的指令来替换这些内置函数。如果没有对应的硬件指令，编译器可能会使用一些优化的软件实现，但仍然比你手写的循环要快。
如何确定你的 CPU 支持哪些指令？
你可以使用一些工具来查看你的 CPU 支持的指令集，比如在 Linux 下可以使用 lscpu 命令。在 Windows 下，可以使用 CPU-Z 等软件。
适用场景：在哪里用它？
这些内置函数在以下场景中特别有用：
- 需要高性能的位操作： 比如在游戏开发、图像处理、密码学等领域。
- 算法竞赛： 可以显著提高代码的运行速度。
- 底层系统编程： 比如在操作系统内核中，经常需要进行位操作。
注意事项：别踩坑！
- 可移植性： 虽然
__builtin_popcount等是 GCC 和 Clang 的标准扩展，但并非所有编译器都支持。如果你的代码需要在不同的编译器下编译，最好使用#ifdef等预处理指令来判断是否支持这些内置函数，并提供备用的软件实现。 - 参数类型： 这些内置函数通常只接受无符号整数作为参数。如果你需要处理有符号整数，需要先将其转换为无符号整数。
- 未定义行为：
__builtin_clz(0)和__builtin_ctz(0)的行为是未定义的。在使用它们之前，需要确保参数不为 0。 - 编译器优化： 编译器可能会对这些内置函数进行优化，比如内联展开。因此，在使用它们时，不需要手动进行优化。
表格总结：
| 函数名 | 功能 | 参数类型 | 返回值类型 | CPU 指令支持 |
|---|---|---|---|---|
__builtin_popcount(x) |
计算 x 的二进制表示中 1 的个数 | unsigned int |
int |
POPCNT (SSE4.2, AMD), 软件模拟 (如果不支持) |
__builtin_clz(x) |
计算 x 的二进制表示中，从最高位开始连续 0 的个数 | unsigned int |
int |
LZCNT (BMI1), BSR (如果不支持 LZCNT), 软件模拟 (如果都不支持) |
__builtin_ctz(x) |
计算 x 的二进制表示中，从最低位开始连续 0 的个数 | unsigned int |
int |
BSF, 软件模拟 (如果不支持 BSF) |
__builtin_ffs(x) |
返回 x 的二进制表示中，最低位的 1 的位置（从 1 开始计数） | int |
int |
BSF, 软件模拟 (如果不支持 BSF) |
__builtin_parity(x) |
计算 x 的二进制表示中 1 的个数的奇偶性 | unsigned int |
int |
软件模拟 (通常使用查表法或位运算) |
一个更复杂的例子：计算两个整数的汉明距离
汉明距离是指两个等长字符串之间，对应位置上不同字符的个数。对于整数来说，可以理解为二进制表示中不同位的个数。
#include <iostream>
int hammingDistance(unsigned int x, unsigned int y) {
return __builtin_popcount(x ^ y);
}
int main() {
unsigned int num1 = 0b10101010;
unsigned int num2 = 0b10110000;
int distance = hammingDistance(num1, num2);
std::cout << "Hamming distance: " << distance << std::endl; // 输出：2
return 0;
}这段代码利用 __builtin_popcount 和异或操作，简洁高效地计算了两个整数的汉明距离。
结论：用好工具，事半功倍！
__builtin_popcount 等内置函数是 C++ 中进行位操作的利器。它们利用 CPU 硬件指令，可以显著提高代码的运行速度。在对性能要求较高的场景下，熟练使用这些函数可以让你事半功倍。记住，了解你的工具，才能更好地利用它们！
好了，今天的分享就到这里。希望大家以后在写代码的时候，能想起这些小技巧，让你的程序跑得更快，更优雅！谢谢大家！