假设我有一个 32 位或 64 位无符号整数。
找到最左边位的索引 i 以使最左边 i 位中 0 的数量等于最左边 i 位中 1 的数量的最快方法是什么？我在想一些小技巧，就像这里提到的那样。
我对最近的 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 评论修复了代码中的错误。
我对此没有任何技巧，但我确实有一个 SIMD 技巧。
先说几个观察，
i，以便第一位i总和为 0”。i必须是偶数的见解，并且可以通过 2 位块来分析此问题。将 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;
出现<< 15and*2是因为生成的掩码是 16 位，但 clz 是 32 位，因为如果顶部字节为零，则表示采用 1 组 2，而不是零。
这是使用经典位旋转技术的 32 位数据的解决方案。中间计算需要 64 位算术和逻辑运算。我必须尽可能地坚持便携式操作。需要的是 POSIX 函数的实现，ffsll以查找 64 位中的最低有效 1 位，以及反转 32 位整数中的位二重奏long long的自定义函数。rev_bit_duos后者可以替换为特定于平台的位反转内在函数，例如ARM 平台上的__rbit内在函数。
基本观察是，如果可以提取具有相同数量的 0 位和 1 位的位组，则它必须包含偶数位。这意味着我们可以检查 2 位组中的操作数。我们可以进一步限制自己跟踪每个 2 位是增加 ( 0b11)、减少 ( 0b00) 还是保持不变 ( 0b01, 0b10) 的运行平衡。如果我们用单独的计数器计算正负变化，4 位计数器就足够了，除非输入是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;
}
一种可能的解决方案（对于 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) ]
这需要约 1MB 的查找表。同样的想法也适用于使用 4 个查找表（x 的每个字节一个）。这需要更多操作，但会将内存降低到 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) ];