binary - 找到 0 数量等于 1 数量的第一个位置的位技巧

Question

假设我有一个 32 或 64 位无符号整数。

找到最左边位的索引 i 以使最左边 i 位中 0 的数量等于最左边 i 位中 1 的数量的最快方法是什么？我正在考虑一些像提到的那样的小技巧here .

我对最新的 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 评论修复了代码中的错误。

Answer 1

我对此没有任何技巧，但我有一个 SIMD 技巧。

首先一些观察，

• 将 0 解释为 -1，这个问题就变成“找到第一个 i，使得第一个 i 位总和为 0”。
• 0 是偶数，但在此解释下所有位都有奇数值，这给出了 i 的见解。一定是偶数，这个问题可以用2位的 block 来分析。
• 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;

<< 15和*2出现是因为生成的掩码是 16 位，但 clz 是 32 位，它会少移一位，因为如果顶部字节为零，则表示采用了 1 组 2，而不是零。