由网友(且放白鹿青崖间)分享简介：有没有有效的按位操作，我可以做的就是，一个整数结尾设置位是多少？例如11 10 = 1011 2 将有两个尾1位​​。 8 10 = 1000 2 是0尾1位。Are there any efficient bitwise operations I can do to get the number of...

有没有有效的按位操作，我可以做的就是，一个整数结尾设置位是多少？例如11 10 = 1011 2 将有两个尾1位​​。 8 10 = 1000 2 是0尾1位。

Are there any efficient bitwise operations I can do to get the number of set bits that an integer ends with? For example 1110 = 10112 would be two trailing 1 bits. 810 = 10002 would be 0 trailing 1 bits.

对此有更好的算法比线性搜索？我实施随机化的跳跃列表，并使用随机数插入时，它以确定的元件的最大电平。我与32位整数处理在C ++中。

Is there a better algorithm for this than a linear search? I'm implementing a randomized skip list and using random numbers to determine the maximum level of an element when inserting it. I am dealing with 32 bit integers in C++.

编辑：汇编是出了问题，我感兴趣的是一个纯C ++的解决方案

assembler is out of the question, I'm interested in a pure C++ solution.

推荐答案

以从伊格纳西奥巴斯克斯 - 艾布拉姆斯的答案并与计完成它，而不是一个表：

Taking the answer from Ignacio Vazquez-Abrams and completing it with the count rather than a table:

b = ~i & (i+1);   // this gives a 1 to the left of the trailing 1's
b--;              // this gets us just the trailing 1's that need counting
b = (b & 0x55555555) + ((b>>1) & 0x55555555);  // 2 bit sums of 1 bit numbers
b = (b & 0x33333333) + ((b>>2) & 0x33333333);  // 4 bit sums of 2 bit numbers
b = (b & 0x0f0f0f0f) + ((b>>4) & 0x0f0f0f0f);  // 8 bit sums of 4 bit numbers
b = (b & 0x00ff00ff) + ((b>>8) & 0x00ff00ff);  // 16 bit sums of 8 bit numbers
b = (b & 0x0000ffff) + ((b>>16) & 0x0000ffff); // sum of 16 bit numbers

在B端将包含1的计数（口罩，增加和转变算1的）。 除非我出了差错，当然。使用前测试。

at the end b will contain the count of 1's (the masks, adding and shifting count the 1's). Unless I goofed of course. Test before use.