9

重複の可能性:
32 ビット整数で設定されたビット数をカウントする方法は?

unsigned char 型の値を指定し、その中の合計ビット数を数えます。最速の方法は何ですか? 私は以下のように 3 つの関数を書きました。最善の方法は何ですか?また、誰かがより高速な関数を思い付くことができますか?(私は非常に高速な関数が欲しいだけです)

const int tbl[] =
{
#define B2(n)   n, n+1, n+1, n+2
#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

char naivecount (unsigned char val)
{
    char cnt = 0;
    while (val)
    {
        cnt += (val & 1);
        val = val >> 1;
    }
    return cnt;
}

inline tableLookUp(int val)
{
    assert(val >= 0 && val <= 255);
    return tbl[val];
}

int asmCount(int val)
{
    int res = 0;
    asm volatile("xor %0, %0\n\t"
            "begin:\n\t"
            "cmp $0x0, %1\n\t"
            "jle end\n\t"
            "movl %1, %%ecx\n\t"
            "and $0x1, %%ecx\n\t"
            "addl %%ecx, %0\n\t"
            "shrl %1\n\t"
            "jmp begin\n\t"
            "end:"
            : "=r"(res)
            : "r" (val));
    return res;
}

編集：

私はすべての方法をテストしましたが、最速の方法は命令を使用すること popcntlです.命令のないプラットフォームでは、テーブルルックアップを使用します.

4

2 に答える 2

9

手動でコーディングする場合は、次のようにしてください。

#include <stdint.h>

int popcnt8(uint8_t x) {

    x = (x & 0x55) + (x >> 1 & 0x55);
    x = (x & 0x33) + (x >> 2 & 0x33);
    x = (x & 0x0f) + (x >> 4 & 0x0f);

    return x;
}

x86 では、これは (AT&T 構文) にコンパイルされます。

popcnt8:
    movl    %edi, %eax
    shrb    %dil
    andl    $85, %eax
    andl    $85, %edi
    addl    %eax, %edi
    movl    %edi, %eax
    shrb    $2, %dil
    andl    $51, %eax
    andl    $51, %edi
    addl    %eax, %edi
    movl    %edi, %eax
    shrb    $4, %dil
    andl    $15, %eax
    addl    %edi, %eax
    movzbl  %al, %eax
    ret

これを、gcc が組み込みで生成するものと比較してください。

#include <stdint.h>

int popcnt8_intrin(uint8_t x) { return __builtin_popcount(x); }

SSE 4.2 を使用する x86 の場合:

popcnt8_intrin:
movzbl  %dil, %eax
popcntl %eax, %eax
ret

これは最適ではありません。clang は以下を生成します。

popcnt8_intrin:
    popcntl %edi,%eax
    ret

計算を 1 つの (!) 命令に減らします。

SSE 4.2 を使用しない x86 の場合:

popcnt8_intrin:
subq    $8, %rsp
movzbl  %dil, %edi
call    __popcountdi2
addq    $8, %rsp
ret

gcc は基本的にここでそのライブラリを呼び出します。最適ではありません。clang はもう少しうまくいきます:

popcnt8_intrin:                         # @popcnt8_intrin
movl    %edi, %eax
shrl    %eax
andl    $85, %eax
subl    %eax, %edi
movl    %edi, %eax
andl    $858993459, %eax        # imm = 0x33333333
shrl    $2, %edi
andl    $858993459, %edi        # imm = 0x33333333
addl    %eax, %edi
movl    %edi, %eax
shrl    $4, %eax
addl    %edi, %eax
andl    $252645135, %eax        # imm = 0xF0F0F0F
imull   $16843009, %eax, %eax   # imm = 0x1010101
shrl    $24, %eax
ret

clang は、32 ビット数全体の popcnt を計算します。これは最適な私見ではありません。

于 2012-12-23T10:35:58.393 に答える
2

アセンブラー コードは、実行されたものと実行されなかったものとで異なる比較と分岐をそれほど多く行わなければ、高速になります。

しかし、明らかに、最速の方法はバイト ルックアップを行うことです。特に 256 個の値しか扱っていないためです (単純な方法を使用して値のリストを記述static const table[256] = { ... }; return table[value];し、関数に a を含めるだけです。

さまざまなソリューションをベンチマークします。

アセンブラー コードがコンパイラー生成コードよりも遅くても、私は驚かないでしょう!

編集：あなたのアセンブラコードは、次のようにすることでわずかに速くなります：

int asmCount(int val)
{
    int res = 0;
    asm volatile("begin:\n\t"
            "movl %1, %%ecx\n\t"
            "and $0x1, %%ecx\n\t"
            "addl %%ecx, %0\n\t"
            "shrl %1\n\t"
            "jnz begin\n\t"
            "end:"
            : "=r"(res)
            : "r" (val)
            : "ecx");      // Important: clobbers ecx!
    return res;
}

xor を削除し (とにかく res = 0 にする必要があります)、比較します (確かに、val がゼロの場合、いくつかの追加の命令を実行しますが、上位ビットが設定されているものについては、2 つの追加の命令であるため、はるかに悪いことです)。つまり、潜在的に 16 の余分な命令を意味し、そのうちの 1 つは分岐です!)、ループの最後でジャンプを jnz に変更しました。おそらく、最初のケースでコンパイラが生成するものとほぼ同じです。単純なコードでコンパイラを打ち負かすのは簡単ではありません!

于 2012-12-23T10:09:04.153 に答える