为了账号安全,请及时绑定邮箱和手机立即绑定

如何计算32位整数中的设置位数?

如何计算32位整数中的设置位数?

如何计算32位整数中的设置位数?代表数字7的8位看起来像这样:00000111设置三位。什么算法来确定32位整数中的设置位数?
查看完整描述

4 回答

?
Qyouu

TA贡献1786条经验 获得超11个赞

在我看来,“最佳”解决方案是另一个程序员(或两年后的原始程序员)可以阅读而没有大量评论的解决方案。你可能想要一些已经提供的最快或最聪明的解决方案,但我更喜欢可读性而不是聪明。


unsigned int bitCount (unsigned int value) {

    unsigned int count = 0;

    while (value > 0) {           // until all bits are zero

        if ((value & 1) == 1)     // check lower bit

            count++;

        value >>= 1;              // shift bits, removing lower bit

    }

    return count;

}

如果你想要更快的速度(假设你记录好以帮助你的继任者),你可以使用表查找:


// Lookup table for fast calculation of bits set in 8-bit unsigned char.


static unsigned char oneBitsInUChar[] = {

//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)

//  =====================================================

    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n

    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n

    : : :

    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn

};


// Function for fast calculation of bits set in 16-bit unsigned short.


unsigned char oneBitsInUShort (unsigned short x) {

    return oneBitsInUChar [x >>    8]

         + oneBitsInUChar [x &  0xff];

}


// Function for fast calculation of bits set in 32-bit unsigned int.


unsigned char oneBitsInUInt (unsigned int x) {

    return oneBitsInUShort (x >>     16)

         + oneBitsInUShort (x &  0xffff);

}

虽然这些依赖于特定的数据类型大小,因此它们不具备可移植性。但是,由于许多性能优化无论如何都不可移植,这可能不是问题。如果你想要便携性,我会坚持使用可读的解决方案。


查看完整回答
反对 回复 2019-05-24
  • 4 回答
  • 0 关注
  • 1086 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信