我的任务是打印从 2 到 N 的所有整数（其中“1”的二进制数大于“0”）
int CountOnes(unsigned int x)
{
unsigned int iPassedNumber = x; // number to be modifed
unsigned int iOriginalNumber = iPassedNumber;
unsigned int iNumbOfOnes = 0;
while (iPassedNumber > 0)
{
iPassedNumber = iPassedNumber >> 1 << 1; //if LSB was '1', it turns to '0'
if (iOriginalNumber - iPassedNumber == 1) //if diffrence == 1, then we increment numb of '1'
{
++iNumbOfOnes;
}
iOriginalNumber = iPassedNumber >> 1; //do this to operate with the next bit
iPassedNumber = iOriginalNumber;
}
return (iNumbOfOnes);
}
这是我计算二进制中“1”的数量的函数。这是我大学时的家庭作业。不过老师说这样效率会更高
{
if(n%2==1)
++CountOnes;
else(n%2==0)
++CountZeros;
}
最后我只是搞砸了，不知道什么是更好的。你怎么看待这件事？
我使用 gcc 编译器进行下面的实验。您的编译器可能不同，因此您可能需要采取一些不同的操作才能获得类似的效果。
\n当试图找出执行某些操作的最优化方法时，您希望查看编译器生成什么样的代码。查看 CPU 手册，看看在该特定架构上哪些操作快，哪些操作慢。尽管有一般准则。当然，如果有办法可以减少 CPU 必须执行的指令数量。
\n我决定向您展示几种不同的方法（并非详尽无遗），并为您提供一个如何手动优化小函数（如本例）的示例。有更复杂的工具可以帮助完成更大、更复杂的功能，但是这种方法几乎适用于任何东西：
\n所有汇编代码都是使用以下代码生成的：
\n\n\ngcc -O99 -o foo -fprofile-生成 foo.c
\n
其次是
\n\n\ngcc -O99 -o foo -fprofile-use foo.c
\n
双重编译使 gcc 真正让 gcc 工作（尽管 -O99 很可能已经做到了），但是里程可能会根据您使用的 gcc 版本而有所不同。
\n这是您的函数的反汇编：
\nCountOnes_you:\n.LFB20:\n .cfi_startproc\n xorl %eax, %eax\n testl %edi, %edi\n je .L5\n .p2align 4,,10\n .p2align 3\n.L4:\n movl %edi, %edx\n xorl %ecx, %ecx\n andl $-2, %edx\n subl %edx, %edi\n cmpl $1, %edi\n movl %edx, %edi\n sete %cl\n addl %ecx, %eax\n shrl %edi\n jne .L4\n rep ret\n .p2align 4,,10\n .p2align 3\n.L5:\n rep ret\n .cfi_endproc\n一个循环中大约有 9 条指令，直到循环退出
\n这是一个使用老师算法的函数：
\nint CountOnes_teacher(unsigned int x)\n{\n unsigned int one_count = 0;\n while(x) {\n if(x%2)\n ++one_count;\n x >>= 1;\n }\n return one_count;\n}\n这是它的反汇编：
\nCountOnes_teacher:\n.LFB21:\n .cfi_startproc\n xorl %eax, %eax\n testl %edi, %edi\n je .L12\n .p2align 4,,10\n .p2align 3\n.L11:\n movl %edi, %edx\n andl $1, %edx\n cmpl $1, %edx\n sbbl $-1, %eax\n shrl %edi\n jne .L11\n rep ret\n .p2align 4,,10\n .p2align 3\n.L12:\n rep ret\n .cfi_endproc\n循环中有 5 条指令，直到循环退出
\n这是 Kernighan 的方法：
\n int CountOnes_K(unsigned int x) {\n unsigned int count;\n for(count = 0; ; x; count++) {\n x &= x - 1; // clear least sig bit\n }\n return count;\n }\n这是反汇编：
\nCountOnes_k:\n.LFB22:\n .cfi_startproc\n xorl %eax, %eax\n testl %edi, %edi\n je .L19\n .p2align 4,,10\n .p2align 3\n.L18: \n leal -1(%rdi), %edx\n addl $1, %eax\n andl %edx, %edi\n jne .L18 ; loop is here\n rep ret\n .p2align 4,,10\n .p2align 3\n.L19:\n rep ret\n .cfi_endproc\n循环3条指令。
\n正如您所看到的，当您使用计数时，编译器并没有真正使用最好的方法（您和您的老师都使用过）。%
Krenighan 方法非常优化，循环中的操作数量最少）。将克雷尼根与朴素的计数方法进行比较是有指导意义的，虽然表面上看起来相同，但实际上并非如此！
\nfor (c = 0; v; v >>= 1)\n{\n c += v & 1;\n}\n与克雷尼汉人相比，这种方法很糟糕。在这里，如果您设置了第 32 位，则此循环将运行 32 次，而 Krenighan 则不会！
\n但所有这些方法仍然相当低于标准，因为它们会循环。
\n如果我们将其他一些（隐式）知识结合到我们的算法中，我们就可以一起消除循环。它们是， 1 数字的大小（以位为单位）和字符的大小（以位为单位）。有了这些片段，并认识到我们可以过滤掉 14、24 或 32 位块中的位，前提是我们有一个 64 位寄存器。
\n例如，如果我们查看一个 14 位数字，那么我们可以简单地计算位数：
\n (n * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;\n对于和%之间的所有数字仅使用一次0x00x3fff
对于 24 位，我们使用 14 位，然后对其余 10 位使用类似的内容：
\n ((n & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f \n+ (((n & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) \n % 0x1f;\n但是我们可以通过实现上面数字中的模式来概括这个概念，并认识到幻数实际上只是恭维（仔细观察十六进制数字 0x8000 + 0x400 + 0x200 + 0x1）移位
\n我们可以概括然后缩小这里的想法，为我们提供最优化的位数计数方法（最多 128 位）（无循环） O(1)：
\nCountOnes_best(unsigned int n) {\n const unsigned char_bits = sizeof(unsigned char) << 3;\n typedef __typeof__(n) T; // T is unsigned int in this case;\n n = n - ((n >> 1) & (T)~(T)0/3); // reuse n as a temporary \n n = (n & (T)~(T)0/15*3) + ((n >> 2) & (T)~(T)0/15*3);\n n = (n + (n >> 4)) & (T)~(T)0/255*15;\n return (T)(n * ((T)~(T)0/255)) >> (sizeof(T) - 1) * char_bits;\n} \n\n\nCountOnes_best:\n.LFB23:\n .cfi_startproc\n movl %edi, %eax\n shrl %eax\n andl $1431655765, %eax\n subl %eax, %edi\n movl %edi, %edx\n shrl $2, %edi\n andl $858993459, %edx\n andl $858993459, %edi\n addl %edx, %edi\n movl %edi, %ecx\n shrl $4, %ecx\n addl %edi, %ecx\n andl $252645135, %ecx\n imull $16843009, %ecx, %eax\n shrl $24, %eax\n ret\n .cfi_endproc\n这可能有点跳跃（你到底是怎么从之前转到这里的），但请花点时间回顾一下。
\n最优化的方法首先在Software Optimization Guide for AMD Athelon\xe2\x84\xa2 64 and Opteron\xe2\x84\xa2 Processor中提到，我的 URL 已损坏。在非常优秀的C bit twiddling 页面上也有很好的解释
\n我强烈建议您仔细阅读该页面的内容，这确实是一本很棒的读物。
\n