位置：文档库 > C/C++ > C/C++程序：计算一个整数中设置的位数？

C/C++程序：计算一个整数中设置的位数？

王安石上传于 2020-01-04 12:25

《C/C++程序：计算一个整数中设置的位数？》

在计算机科学中，"设置的位数"（Set Bits）指的是一个整数在二进制表示中值为1的位的数量。这一概念在底层编程、算法优化和硬件交互中具有重要应用，例如哈希计算、数据压缩和加密算法。本文将系统探讨如何使用C/C++语言高效计算整数的设置位数，涵盖基础方法、优化技巧及实际应用场景。

一、基础概念与二进制表示

整数在计算机中以二进制形式存储，每个二进制位（bit）只能是0或1。例如，十进制数5的二进制表示为101，其中包含2个设置的位（两个1）。计算设置位数的核心任务是遍历整数的二进制表示，统计1的个数。

C/C++中，整数类型（如int、unsigned int）的位数取决于系统架构。32位系统中，int通常为32位；64位系统中可能为64位。明确数据类型是编写可移植代码的关键。

二、基础方法：逐位检查法

最直观的方法是逐位检查整数的每一位是否为1。通过右移操作和按位与运算，可以依次检查每个位。

#include 
using namespace std;

int countSetBits(int num) {
    int count = 0;
    unsigned int n = static_cast(num); // 处理负数
    while (n > 0) {
        if (n & 1) { // 检查最低位是否为1
            count++;
        }
        n >>= 1; // 右移一位
    }
    return count;
}

int main() {
    int num;
    cout > num;
    cout

此方法的时间复杂度为O(n)，其中n为整数的位数（如32或64）。对于大整数，效率较低，但逻辑简单易懂。

三、优化方法：Brian Kernighan算法

Brian Kernighan算法通过利用n & (n-1)操作快速消除最低位的1，显著减少循环次数。例如，对于n=10100（十进制20），n-1=10011，n & (n-1)=10000，直接跳过中间的0。

int countSetBitsKernighan(unsigned int n) {
    int count = 0;
    while (n) {
        n &= (n - 1); // 消除最低位的1
        count++;
    }
    return count;
}

该算法的时间复杂度为O(k)，其中k为设置位的数量。对于稀疏的二进制数（1较少），效率远高于逐位检查法。

四、查表法：空间换时间

查表法通过预计算0-255范围内所有字节的设置位数，将8位数的计算转换为查表操作。适用于需要高频计算小范围整数的场景。

#include 

vector precomputeBits() {
    vector bits(256);
    for (int i = 0; i > 1];
    }
    return bits;
}

int countSetBitsLookup(unsigned int n, const vector& bits) {
    int count = 0;
    for (int i = 0; i >= 8;
    }
    return count;
}

int main() {
    auto bits = precomputeBits();
    unsigned int num = 0x12345678;
    cout

查表法的空间复杂度为O(2^k)，k为每段位数（如8）。时间复杂度为O(n/k)，适合嵌入式系统等资源受限环境。

五、分治法：并行计算

分治法将整数拆分为多个部分，并行计算各部分的设置位数后汇总。例如，32位数可拆分为4个8位部分，利用查表法或并行指令加速。

int countSetBitsDivideConquer(unsigned int n) {
    // 拆分为4个8位部分
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
    n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF);
    n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF);
    return n;
}

此方法通过位操作并行统计，时间复杂度为O(log n)，适合高性能计算场景。

六、编译器内置函数：__builtin_popcount

GCC和Clang等编译器提供了内置函数__builtin_popcount（C++）和__builtin_popcountl（长整型），直接调用硬件指令（如POPCNT）实现最优性能。

#include 
using namespace std;

int main() {
    unsigned int num;
    cout > num;
    cout

该方法在支持POPCNT指令的CPU上效率最高，但可移植性较差。使用时需检查编译器和硬件支持。

七、处理负数与边界条件

负数在C/C++中以补码形式存储。例如，-1的二进制表示为全1（32位系统中为0xFFFFFFFF）。直接右移负数会导致符号位扩展，需转换为无符号类型处理。

int countSetBitsNegative(int num) {
    unsigned int n = static_cast(num);
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

对于64位整数，需使用unsigned long long类型并调整循环次数。

八、性能对比与选择策略

不同方法的性能取决于输入数据和硬件环境：

小范围整数（0-255）：查表法最优。
稀疏二进制数：Brian Kernighan算法最快。
高性能需求：编译器内置函数或分治法。
嵌入式系统：查表法或逐位检查法（资源受限）。

九、实际应用场景

1. 哈希函数：设置位数可用于设计简单哈希，如布隆过滤器。

2. 数据压缩：统计1的密度优化编码方案。

3. 加密算法：某些加密操作依赖设置位数计算。

4. 性能优化：识别数据稀疏性以选择算法。

十、完整代码示例

#include 
#include 
using namespace std;

// 方法1：逐位检查
int countBitsNaive(unsigned int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// 方法2：Brian Kernighan
int countBitsKernighan(unsigned int n) {
    int count = 0;
    while (n) {
        n &= (n - 1);
        count++;
    }
    return count;
}

// 方法3：查表法
vector precompute() {
    vector bits(256);
    for (int i = 0; i > 1];
    }
    return bits;
}

int countBitsLookup(unsigned int n, const vector& bits) {
    int count = 0;
    for (int i = 0; i >= 8;
    }
    return count;
}

int main() {
    unsigned int num;
    cout > num;

    auto bits = precompute();
    cout

关键词：设置位数、C/C++、Brian Kernighan算法、查表法、分治法、内置函数、补码、性能优化

简介：本文详细探讨了C/C++中计算整数设置位数的多种方法，包括逐位检查、Brian Kernighan算法、查表法、分治法及编译器内置函数，分析了各方法的原理、实现与性能，并提供了处理负数和边界条件的技巧，适用于算法优化、哈希计算等实际场景。

立即下载

C/C++相关