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

Question

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

代表数字7的8位看起来像这样：

00000111

设置三位。

什么算法来确定32位整数中的设置位数？

Answer 1

在我看来，“最佳”解决方案是另一个程序员（或两年后的原始程序员）可以阅读而没有大量评论的解决方案。你可能想要一些已经提供的最快或最聪明的解决方案，但我更喜欢可读性而不是聪明。unsigned int bitCount (unsigned int value) {&nbsp; &nbsp; unsigned int count = 0;&nbsp; &nbsp; while (value > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// until all bits are zero&nbsp; &nbsp; &nbsp; &nbsp; if ((value & 1) == 1)&nbsp; &nbsp; &nbsp;// check lower bit&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; &nbsp; &nbsp; value >>= 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // shift bits, removing lower bit&nbsp; &nbsp; }&nbsp; &nbsp; return count;}如果你想要更快的速度（假设你记录好以帮助你的继任者），你可以使用表查找：// Lookup table for fast calculation of bits set in 8-bit unsigned char.static unsigned char oneBitsInUChar[] = {//&nbsp; 0&nbsp; 1&nbsp; 2&nbsp; 3&nbsp; 4&nbsp; 5&nbsp; 6&nbsp; 7&nbsp; 8&nbsp; 9&nbsp; A&nbsp; B&nbsp; C&nbsp; D&nbsp; E&nbsp; F (<- n)//&nbsp; =====================================================&nbsp; &nbsp; 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n&nbsp; &nbsp; 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n&nbsp; &nbsp; : : :&nbsp; &nbsp; 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) {&nbsp; &nbsp; return oneBitsInUChar [x >>&nbsp; &nbsp; 8]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ oneBitsInUChar [x &&nbsp; 0xff];}// Function for fast calculation of bits set in 32-bit unsigned int.unsigned char oneBitsInUInt (unsigned int x) {&nbsp; &nbsp; return oneBitsInUShort (x >>&nbsp; &nbsp; &nbsp;16)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;+ oneBitsInUShort (x &&nbsp; 0xffff);}虽然这些依赖于特定的数据类型大小，因此它们不具备可移植性。但是，由于许多性能优化无论如何都不可移植，这可能不是问题。如果你想要便携性，我会坚持使用可读的解决方案。