我正在阅读一个包含以下函数的程序：
int f(int n) {
int c;
for (c=0;n!=0;++c)
n=n&(n-1);
return c;
}
我不太明白这个函数的目的是什么？
7个回答
39
这个算法用于计算 n 的二进制表示中 1 的数量。
- Vladimir
6
9如果这个函数被称为
countBinaryOnes 而不是 f，那么这个问题本来就不需要被问到，我喜欢这种方式。另外加一。 - Cam+1。在此处查看2a - http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/ - Dummy00001
2编码优雅度：A+。 编码清晰度：F。 - Jay
这种函数不仅需要一个好的名称，还需要一个良好的注释块来描述它的功能。即使名称是countBinaryOnes，你也会相信它确实做到了吗？ - Martin York
@Jay，也许是B+。f（INT_MIN）会引发未定义行为。在我看来应该是无符号的f（unsigned）。 - Nordic Mainframe
1哦，就我个人而言，为了简洁起见，我会写成“n&=n-1”。另一方面，我可能不会使用FOR循环，因为我避免测试引用与增量不同的值。我发现这可能会令人困惑。 - Jay
6
该函数旨在返回n的表示中的位数。其他答案中遗漏的是，当参数n < 0时，该函数调用未定义的行为。这是因为该函数从最低位到最高位一次剥离一个比特位。对于负数，这意味着在循环终止之前n的最后一个值（对于2补码的32位整数）是0x8000000。这个数字是INT_MIN，并且现在用于循环的最后一次：
n = n&(n-1)
很遗憾，INT_MIN-1是一种溢出情况，而且溢出会引起未定义的行为。符合规范的实现不要求对整数进行“环绕”，它可能会发出溢出陷阱，或者留下各种奇怪的结果。
- Nordic Mainframe
1
1在有符号的数量中计算设置位通常不是您想要做的事情。该函数应该只接受“unsigned int”。 - Karl Knechtel
5
这是一种（现在已经过时的）解决非军用CPU缺少POPCNT指令的方法。
- mvds
4
这个方法通过使用二进制和运算来计算将n减少到0所需的迭代次数。
- John Weldon
3
是的，但迭代次数取决于什么呢 :P Vlad说中了。 - Nick T
答案最多为1：n & 0。 - Amnon
3@Nick; 很好的观点。我没有想到那个解释，所以我只是描述了机制而非意图。 - John Weldon
3
表达式n = n & (n - 1) 是一种按位运算，它将 n 中最右边的 '1' 换成了 '0'。
例如，取一个整数 5（0101）。那么 n & (n - 1) → (0101) & (0100) → 0100（从右侧移除第一个 '1' 位）。
因此，上述代码返回给定整数的二进制形式中 '1' 的数量。
- sai Charan
1
它展示了一种不正确的编程方式（针对x86指令集），使用内置/内联汇编指令更快且更易读，适用于像这样简单的任务。（但是这只适用于我所了解的x86体系结构，我不清楚ARM或者SPARC或其他体系结构是否也适用。）
- Quonux
2
1在Freescale HCS08上执行此操作的汇编指令是什么？ :P - Nick T
我认为你需要更加充分地证明一下。 - BobbyShaftoe
0
它是否试图返回n中有效位数的数量？（还没有完全思考...）
- TheBlastOne
9
虽然我认为@Vladimir的答案在技术上是准确的，但我最喜欢这个解释。 - Randolpho
2@Randolpho 什么？这个答案是错误的。如果输入是0b1000，它应该返回1，而不是4（二进制数中有效数字位数）。 - Nick T
什么是有效位？ - Amnon
@Ammon：二进制表示中所需的最小位数，即从最低有效位（从右侧）开始计算最后一个非零位的位置（基于1的计数）。 - Andreas Rejbrand
1哇，我很高兴我在一开始就提到了这件事，直到最后我都没有想到它 :) - TheBlastOne
显示剩余4条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
f是这个函数的一个糟糕的名称。 - David Thornley