用于计数位的高效按位运算或找到最右侧的位
给定unsigned int，我必须执行以下操作：
- 计算设置为1的位数
- 找到最左边1位的索引
- 找到最右边1位的索引
（该操作不应该是架构依赖）。
我已经使用按位移位完成了这项工作，但我必须迭代几乎所有的位（es.32）。 例如，计算1：
unsigned int number= ...; while(number != 0){ if ((number & 0x01) != 0) ++count; number >>=1; } 其他操作类似。
所以我的问题是：有没有更快的方法呢？
如果您想要最快的方式，则需要使用非便携式方法。
在Windows / MSVC：
- _BitScanForward（）
- _BitScanReverse（）
- __popcnt（）
GCC：
- __builtin_ffs（）
- __builtin_ctz（）
- __builtin_clz（）
- __builtin_popcount（）
这些通常直接映射到本机硬件指令。 所以它没有比这些快得多。
但由于它们没有C / C ++function，因此只能通过编译器内在函数访问它们。
看看ffs（3），ffsl（3），fls（3），flsl（3）。
ffs（）和ffsl（）函数在i中找到第一个位集（从最低有效位开始）并返回该位的索引。
fls（）和flsl（）函数在i中找到最后一位，并返回该位的索引。
您可能也对bitstring（3）感兴趣。
引自http://graphics.stanford.edu/~seander/bithacks.html
计算32位整数v中位的最佳方法如下：
unsigned int v; // count bits set in this (32-bit value) unsigned int c; // store the total here v = v - ((v >> 1) & 0x55555555); // reuse input as temporary v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count最好的位计数方法只需要12次操作，这与查找表方法相同，但避免了表的内存和潜在的高速缓存未命中。 它是上面的纯粹并行方法和使用乘法的早期方法之间的混合（在使用64位指令计数位的部分中），尽管它不使用64位指令。 字节中设置的位数是并行完成的，字节中设置的位总和是通过乘以0x1010101和右移24位来计算的。
一种方法是使用查找表。
uint8_t popcount_table[256] = { ... }; uint8_t popcount (uint32_t x) { uint8_t *p = (uint8_t*)&x; return popcount_table[p[0]] + popcount_table[p[1]] + popcount_table[p[2]] + popcount_table[p[3]]; }