Битовые трюки, чтобы найти первую позицию, где число 0 равно числу 1

Question

Предположим, у меня есть 32- или 64-разрядное целое число без знака.

Каков самый быстрый способ найти индекс i самого левого бита, чтобы число 0 в крайних левых битах равнялось числу 1 в крайних левых битах? Я думал о некоторых хитростях, подобных упомянутым здесь.

Я заинтересован в недавнем процессоре x86_64. Это может быть уместно, поскольку некоторые инструкции по поддержке процессора, такие как POPCNT (считать количество 1 с) или LZCNT (подсчитывают количество ведущих 0).

Если это помогает, можно предположить, что первый бит всегда имеет определенное значение.

Пример (с 16 битами): если целое число

1110010100110110b 
         ^ 
         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 бита.
• 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, а не ноль.

Answer 2

Это решение для 32-битных данных, использующее классические методы бит-тиддлинга. Промежуточное вычисление требует 64-битных арифметических и логических операций. Я должен попытаться придерживаться переносимых операций, насколько это было возможно. Требуется реализация функции POSIX ffsll найти наименее значимый 1-разрядный в 64-разрядном long long и пользовательская функция rev_bit_duos это инвертирует битовые дуэты в 32-битном целом числе. Последний может быть заменен платформо-ориентированной инверсией битов, такой как __rbit свойственный платформам ARM.

Основное наблюдение состоит в том, что, если можно извлечь битовую группу с равным количеством 0 битов и 1 битов, она должна содержать четное количество битов. Это означает, что мы можем исследовать операнд в 2-битных группах. Мы можем дополнительно ограничиться отслеживанием увеличения каждого 2-битного 0b11), уменьшается (0b00) или оставляет без изменений (0b01, 0b10) текущий баланс битов. Если мы подсчитываем положительные и отрицательные изменения с помощью отдельных счетчиков, 4-разрядных счетчиков будет достаточно, если только вход 0 или же 0xffffffff, который может быть обработан отдельно. Судя по комментариям к вопросу, таких случаев не должно быть. Вычитая отрицательный счетчик изменений из положительного счетчика изменений для каждой 2-битной группы, мы можем определить, в какой группе баланс становится равным нулю. Таких битовых групп может быть несколько, нам нужно найти первую.

Обработка может быть распараллелена путем расширения каждой 2-битной группы в клочок, который затем может служить счетчиком изменений. Сумма префикса может быть вычислена посредством умножения целого числа на соответствующую константу, которая обеспечивает необходимые операции сдвига и сложения в каждой позиции клева. Эффективные способы параллельного вычитания по клевам хорошо известны, так же, как и у Алана Майкрофта, существует хорошо известная методика обнаружения нулевых байтов, которая тривиально изменяема на обнаружение нулевого клева. Функция POSIX ffsll Затем применяется, чтобы найти положение бита этого клева.

Немного проблематичным является требование к извлечению самой левой группы битов, а не самой правой, поскольку трюк Алана Майкрофта работает только для нахождения первого нулевого куска справа. Кроме того, обработка суммы префикса для самой левой группы битов требует использования 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;
}

Answer 3

Возможное решение (для 32-битных целых). Я не уверен, что это можно улучшить / избежать использования таблиц подстановки. Здесь х - входное целое число.

//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 МБ для справочных таблиц. Эта же идея также работает с использованием 4 справочных таблиц (по одной на байт x). Требует больше операций, но сокращает объем памяти до 12 КБ.

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) ];