2

32 ビットまたは 64 ビットの符号なし整数があるとします。

左端 i ビットの 0 の数が左端 i ビットの 1 の数と等しくなるように、左端ビットのインデックス i を見つける最速の方法は何ですか? ここで述べたようなちょっとしたトリックを考えていました。

最近の x86_64 プロセッサに興味があります。これは、POPCNT (1 の数をカウントする) または LZCNT (先頭の 0 の数をカウントする) などの一部のプロセッサ サポート命令に関連している可能性があります。

それが役立つ場合は、最初のビットが常に特定の値を持っていると仮定することができます。

例 (16 ビットの場合): 整数が

1110010100110110b 
         ^ 
         i

i=10 で、マークされた位置に対応します。

16 ビット整数の可能な (遅い) 実装は次のようになります。

mask = 1000000000000000b
pos = 0
count=0
do {
    if(x & mask)
        count++;
    else
        count--;

    pos++;
    x<<=1;
} while(count)

return pos;

編集: @njuffa コメントに従ってコードのバグを修正しました。

4

3 に答える 3

3

これには少しのトリックはありませんが、SIMD のトリックはあります。

最初にいくつかの観察、

  • 0 を -1 と解釈すると、この問題は「最初のビットの合計が 0 になるiように最初のビットを見つける」になります。i
  • 0 は偶数ですが、この解釈ではすべてのビットの値が奇数であり、偶数でなければならないという洞察が得られi、この問題は 2 ビットのブロックで分析できます。
  • 01と10はバランスを変えません。

2 つのグループをバイトに展開した後 (次のいずれもテストされていません)、

// optionally use AVX2 _mm_srlv_epi32 instead of ugly variable set
__m128i spread = _mm_shuffle_epi8(_mm_setr_epi32(x, x >> 2, x >> 4, x >> 6),
                   _mm_setr_epi8(0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15));
spread = _mm_and_si128(spread, _mm_set1_epi8(3));

00 を -1 に、11 を 1 に、01 と 10 を 0 に置き換えます。

__m128i r = _mm_shuffle_epi8(_mm_setr_epi8(-1, 0, 0, 1,  0,0,0,0,0,0,0,0,0,0,0,0),
                             spread);

プレフィックスの合計を計算します。

__m128i pfs = _mm_add_epi8(r, _mm_bsrli_si128(r, 1));
pfs = _mm_add_epi8(pfs, _mm_bsrli_si128(pfs, 2));
pfs = _mm_add_epi8(pfs, _mm_bsrli_si128(pfs, 4));
pfs = _mm_add_epi8(pfs, _mm_bsrli_si128(pfs, 8));

最高の 0 を見つける:

__m128i iszero = _mm_cmpeq_epi8(pfs, _mm_setzero_si128());
return __builtin_clz(_mm_movemask_epi8(iszero) << 15) * 2;

結果のマスクは 16 ビットですが、clz は 32 ビットであるため、<< 15andが表示されます。上位バイトがゼロの場合、ゼロではなく 2 の 1 つのグループが取得されることを示すため、1 つ少なくシフトされます。*2

于 2016-12-02T14:24:15.453 に答える
2

これは、従来のビット操作手法を使用した 32 ビット データのソリューションです。中間計算には、64 ビットの算術演算と論理演算が必要です。可能な限り、移植可能な操作に固執するようにしなければなりません。ffsll64 ビットの最下位 1 ビットを検出するPOSIX 関数の実装と、32 ビット整数のビットデュオを逆にlong longするカスタム関数が必要です。後者は、ARM プラットフォームの組み込み関数rev_bit_duosなど、プラットフォーム固有のビット反転組み込み関数に置き換えることができます。__rbit

基本的な観察は、等しい数の 0 ビットと 1 ビットを持つビット グループを抽出できる場合、それには偶数のビットが含まれている必要があるということです。これは、オペランドを 2 ビット グループで調べることができることを意味します。0b11さらに、各 2 ビットが増加するか ( )、減少するか ( 0b00)、または変更されないままになるか ( 0b01、 )を追跡することに限定することができ0b10ます。正と負の変化を別々のカウンターでカウントする場合、入力が0または0xffffffff、個別に処理できます。質問へのコメントに基づいて、これらのケースは発生しないはずです。各 2 ビット グループの正の変更カウントから負の変更カウントを減算することにより、バランスがゼロになるグループを見つけることができます。そのようなビット グループが複数ある可能性があるため、最初のグループを見つける必要があります。

処理は、各 2 ビット グループをニブルに拡張することで並列化できます。ニブルは変更カウンターとして機能します。プレフィックスの合計は、適切な定数を使用した整数乗算によって計算できます。これにより、各ニブル位置で必要なシフトおよび加算操作が提供されます。ニブルごとの並列減算の効率的な方法はよく知られており、同様に、ゼロニブル検出に簡単に変更できるゼロバイトを検出するための Alan Mycroft によるよく知られた手法があります。次に、 POSIX 関数ffsllを適用して、そのニブルのビット位置を見つけます。

Alan Mycroft のトリックは、右端から最初のゼロニブルを見つける場合にのみ機能するため、右端のビット グループではなく、左端のビット グループを抽出する必要があることは少し問題です。また、左端のビット グループのプレフィックス サムを処理するには、簡単に利用できない操作を使用する必要があり、標準の整数乗算よりも効率が悪い場合があります。元のオペランドを前もってビット反転するだけで、これらの問題の両方に対処しました。mulhi

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

/* Reverse bit-duos using classic binary partitioning algorithm */
inline uint32_t rev_bit_duos (uint32_t a)
{
    uint32_t m;
    a = (a >> 16) | (a << 16);                            // swap halfwords
    m = 0x00ff00ff; a = ((a >> 8) & m) | ((a << 8) & ~m); // swap bytes
    m = (m << 4)^m; a = ((a >> 4) & m) | ((a << 4) & ~m); // swap nibbles
    m = (m << 2)^m; a = ((a >> 2) & m) | ((a << 2) & ~m); // swap bit-duos
    return a;
}

/* Return the number of most significant (leftmost) bits that must be extracted
   to achieve an equal count of 1-bits and 0-bits in the extracted bit group.
   Return 0 if no such bit group exists.
*/   
int solution (uint32_t x)
{
    const uint64_t mask16 = 0x0000ffff0000ffffULL; // alternate half-words
    const uint64_t mask8  = 0x00ff00ff00ff00ffULL; // alternate bytes
    const uint64_t mask4h = 0x0c0c0c0c0c0c0c0cULL; // alternate nibbles, high bit-duo
    const uint64_t mask4l = 0x0303030303030303ULL; // alternate nibbles, low bit-duo
    const uint64_t nibble_lsb = 0x1111111111111111ULL;
    const uint64_t nibble_msb = 0x8888888888888888ULL; 
    uint64_t a, b, r, s, t, expx, pc_expx, nc_expx;
    int res;

    /* common path can't handle all 0s and all 1s due to counter overflow */
    if ((x == 0) || (x == ~0)) return 0;

    /* make zero-nibble detection work, and simplify prefix sum computation */
    x = rev_bit_duos (x); // reverse bit-duos

    /* expand each bit-duo into a nibble */
    expx = x;
    expx = ((expx << 16) | expx) & mask16;
    expx = ((expx <<  8) | expx) & mask8;
    expx = ((expx <<  4) | expx);
    expx = ((expx & mask4h) * 4) + (expx & mask4l);

    /* compute positive and negative change counts for each nibble */
    pc_expx =  expx & ( expx >> 1) & nibble_lsb;
    nc_expx = ~expx & (~expx >> 1) & nibble_lsb;

    /* produce prefix sums for positive and negative change counters */
    a = pc_expx * nibble_lsb;
    b = nc_expx * nibble_lsb;

    /* subtract positive and negative prefix sums, nibble-wise */
    s = a ^ ~b;
    r = a | nibble_msb;
    t = b & ~nibble_msb;
    s = s & nibble_msb;
    r = r - t;
    r = r ^ s;

    /* find first nibble that is zero using Alan Mycroft's magic */
    r = (r - nibble_lsb) & (~r & nibble_msb);
    res = ffsll (r) / 2;  // account for bit-duo to nibble expansion

    return res;
}

/* Return the number of most significant (leftmost) bits that must be extracted
   to achieve an equal count of 1-bits and 0-bits in the extracted bit group.
   Return 0 if no such bit group exists.
*/   
int reference (uint32_t x)
{
    int count = 0;
    int bits = 0;
    uint32_t mask = 0x80000000;
    do {
        bits++;
        if (x & mask) {
            count++;
        } else {
            count--;
        }
        x = x << 1;
    } while ((count) && (bits <= (int)(sizeof(x) * CHAR_BIT)));
    return (count) ? 0 : bits;
}

int main (void)
{
    uint32_t x = 0;
    do {
        uint32_t ref = reference (x);
        uint32_t res = solution (x);
        if (res != ref) {
            printf ("x=%08x  res=%u ref=%u\n\n", x, res, ref);
        }
        x++;
    } while (x);
    return EXIT_SUCCESS;
}
于 2016-12-02T23:02:37.827 に答える
1

考えられる解決策 (32 ビット整数の場合)。改善できるかどうかわからない/ルックアップテーブルの使用を避ける. ここで、x は入力整数です。

//Look-up table of 2^16 elements.
//The y-th is associated with the first 2 bytes y of x.
//If the wanted bit is in y, LUT1[y] is minus the position of the bit
//If the wanted bit is not in y, LUT1[y] is the number of ones in excess in y minus 1 (between 0 and 15)
LUT1 = ....

//Look-up talbe of 16 * 2^16 elements.
//The y-th element is associated to two integers y' and y'' of 4 and 16 bits, respectively.
//y' is the number of excess ones in the first byte of x, minus 1
//y'' is the second byte of x. The table contains the answer to return.
LUT2 = ....

if(LUT1[x>>16] < 0)
    return -LUT1[x>>16];

return LUT2[ (LUT1[x>>16]<<16) | (x & 0xFFFF) ]

これには、ルックアップ テーブルに最大 1 MB が必要です。4 つのルックアップ テーブル (x のバイトごとに 1 つ) を使用しても、同じ考え方が機能します。より多くの操作が必要ですが、メモリは 12KB に減少します。

LUT1 = ... //2^8 elements
LUT2 = ... //8 * 2^8 elements
LUT3 = ... //16 * 2^8 elements
LUT3 = ... //24 * 2^8 elements

y = x>>24
if(LUT1[y] < 0)
    return -LUT1[y];

y = (LUT1[y]<<8) | ((x>>16) & 0xFF);
if(LUT2[y] < 0)
    return -LUT2[y];

y = (LUT2[y]<<8) | ((x>>8) & 0xFF);
if(LUT3[y] < 0)
    return -LUT3[y];

return LUT4[(LUT2[y]<<8) | (x & 0xFF) ];
于 2016-12-02T14:27:48.220 に答える