Получение количества конечных 1 бит

Question

Существуют ли какие-либо эффективные побитовые операции, которые я могу сделать, чтобы получить число установленных битов, которым заканчивается целое число? Например, 11 ₁₀ = 1011 ₂ будет двумя концевыми 1 битами. 8 ₁₀ = 1000 ₂ будет равно 0 конечных 1 бит.

Есть ли лучший алгоритм для этого, чем линейный поиск? Я реализую случайный список пропусков и использую случайные числа, чтобы определить максимальный уровень элемента при его вставке. Я имею дело с 32-битными целыми числами в C ++.

Редактировать: Об ассемблере не может быть и речи, меня интересует чисто C ++ решение.

Answer 1

http://graphics.stanford.edu/~seander/bithacks.html может дать вам некоторое вдохновение.

Answer 2

Этот код подсчитывает количество завершающих нулевых бит, взятых из здесь (есть также версия, которая зависит от 32-битного представления с плавающей точкой IEEE, но я бы не стал доверять этому, а также модуль / Подходы с разделением выглядят очень гладко - тоже стоит попробовать):

int CountTrailingZeroBits(unsigned int v) // 32 bit
{
    unsigned int c = 32; // c will be the number of zero bits on the right

    static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
    static const unsigned int S[] = {1, 2, 4, 8, 16}; // Our Magic Binary Numbers

    for (int i = 4; i >= 0; --i) // unroll for more speed
    {
        if (v & B[i])
        {
            v <<= S[i];
            c -= S[i];
        }
    }

    if (v)
    {
        c--;
    }

    return c;
}

, а затем посчитать конечные:

int CountTrailingOneBits(unsigned int v)
{
    return CountTrailingZeroBits(~v);
}