在 C 中计数 '1'

Question

我的任务是打印从 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;
}

最后，我只是搞砸了，不知道什么更好。你怎么看待这件事？

Answer 1

我在下面的实验中使用了 gcc 编译器。您的编译器可能不同，因此您可能需要做一些不同的事情才能获得类似的效果。

当试图找出最优化的方法来做某事时，您想看看编译器生成什么样的代码。查看 CPU 的手册，看看在特定架构上哪些操作快，哪些操作慢。虽然有一般指导方针。当然，如果有办法可以减少 CPU 必须执行的指令数量。

我决定向您展示几种不同的方法(并非详尽无遗)，并为您提供一个示例，说明如何手动查看小函数(例如这个)的优化。有更复杂的工具可以帮助处理更大更复杂的功能，但是这种方法几乎适用于任何事情:

笔记

所有汇编代码都是使用以下方法生成的:

gcc -O99 -o foo -fprofile-generate foo.c

其次是

gcc -O99 -o foo -fprofile-use foo.c

在 -fprofile-generate

双重编译使 gcc 真正让我们的 gcc 工作(尽管 -O99 很可能已经这样做了)，但是里程可能会根据您可能使用的 gcc 版本而有所不同。

继续:

方法一(你)

这是您的功能的反汇编:

CountOnes_you:
.LFB20:
        .cfi_startproc
        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L5
        .p2align 4,,10
        .p2align 3
.L4:
        movl    %edi, %edx
        xorl    %ecx, %ecx
        andl    $-2, %edx
        subl    %edx, %edi
        cmpl    $1, %edi
        movl    %edx, %edi
        sete    %cl
        addl    %ecx, %eax
        shrl    %edi
        jne     .L4
        rep ret
        .p2align 4,,10
        .p2align 3
.L5:
        rep ret
        .cfi_endproc

乍看上去

一个循环大约有 9 条指令，直到循环退出

方法二(教师)

这是一个使用老师算法的函数:

int CountOnes_teacher(unsigned int x)
{
    unsigned int one_count = 0;
    while(x) {
        if(x%2)
            ++one_count;
        x >>= 1;
    }
    return one_count;
}

这是它的反汇编:

CountOnes_teacher:
.LFB21:
        .cfi_startproc
        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L12
        .p2align 4,,10
        .p2align 3
.L11:
        movl    %edi, %edx
        andl    $1, %edx
        cmpl    $1, %edx
        sbbl    $-1, %eax
        shrl    %edi
        jne     .L11
        rep ret
        .p2align 4,,10
        .p2align 3
.L12:
        rep ret
        .cfi_endproc

乍看上去:

循环中的 5 条指令，直到循环退出

方法三

这是 Krenighan 的方法:

 int CountOnes_K(unsigned int x) {
      unsigned int count;
      for(count = 0; ; x; count++) {
          x &= x - 1; // clear least sig bit
      }
      return count;
 }

下面是拆解:

CountOnes_k:
.LFB22:
        .cfi_startproc
        xorl    %eax, %eax
        testl   %edi, %edi
        je      .L19
        .p2align 4,,10
        .p2align 3
.L18: 
        leal    -1(%rdi), %edx
        addl    $1, %eax
        andl    %edx, %edi
        jne     .L18  ; loop is here
        rep ret
        .p2align 4,,10
        .p2align 3
.L19:
        rep ret
        .cfi_endproc

乍看上去

循环中的3条指令。

在继续之前的一些评论

正如您所看到的，当您使用 % 时，编译器并没有真正使用最佳方式。计数(您和您的老师都使用过)。

Krenighan 方法非常优化，循环中的操作次数最少)。将 Krenighan 与幼稚的计数方法进行比较是有指导意义的，而从表面上看，它可能看起来相同，但实际上并非如此!

for (c = 0; v; v >>= 1)
{
  c += v & 1;
}

与 Krenighans 相比，这种方法很糟糕。在这里，如果您说设置了第 32 位，则此循环将运行 32 次，而 Krenighan 则不会!

但是所有这些方法仍然相当低级，因为它们是循环的。

如果我们将其他一些(隐式)知识结合到我们的算法中，我们可以一起摆脱循环。它们是，1 是我们数字的大小(以位为单位)，以及一个字符的大小(以位为单位)。有了这些片段，并意识到我们可以过滤掉 14、24 或 32 位块中的位，因为我们有一个 64 位寄存器。

因此，例如，如果我们查看一个 14 位数字，那么我们可以简单地通过以下方式计算位数:

 (n * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

用途 %但对于 0x0 之间的所有数字只有一次和 0x3fff
对于 24 位，我们使用 14 位，然后对其余 10 位使用类似的东西:

  ((n & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f 
+ (((n & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
 % 0x1f;

但是我们可以通过实现上面数字中的模式来概括这个概念，并意识到魔数(Magic Number)实际上只是恭维(仔细观察十六进制数 0x8000 + 0x400 + 0x200 + 0x1)移位

我们可以概括然后缩小这里的想法，为我们提供最优化的计数位(最多 128 位)(无循环)O(1) 的方法:

CountOnes_best(unsigned int n) {
    const unsigned char_bits = sizeof(unsigned char) << 3;
    typedef __typeof__(n) T; // T is unsigned int in this case;
    n = n - ((n >> 1) & (T)~(T)0/3); // reuse n as a temporary 
    n = (n & (T)~(T)0/15*3) + ((n >> 2) & (T)~(T)0/15*3);
    n = (n + (n >> 4)) & (T)~(T)0/255*15;
    return (T)(n * ((T)~(T)0/255)) >> (sizeof(T) - 1) * char_bits;
} 


CountOnes_best:
.LFB23:
        .cfi_startproc
        movl    %edi, %eax
        shrl    %eax
        andl    $1431655765, %eax
        subl    %eax, %edi
        movl    %edi, %edx
        shrl    $2, %edi
        andl    $858993459, %edx
        andl    $858993459, %edi
        addl    %edx, %edi
        movl    %edi, %ecx
        shrl    $4, %ecx
        addl    %edi, %ecx
        andl    $252645135, %ecx
        imull   $16843009, %ecx, %eax
        shrl    $24, %eax
        ret
        .cfi_endproc

这可能有点跳跃(你到底是怎么从以前到这里的)，但请花点时间回顾一下。

最优化的方法首先在 AMD Athelon™ 64 和 Opteron™ 处理器的软件优化指南中提到，我的 URL 已损坏。在非常优秀的C bit twiddling page上也有很好的解释
我强烈建议阅读该页面的内容，这真的是一本很棒的书。