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

Question

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

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

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

Answer 1

Рассчитайте ~i & (i + 1) и используйте результат в качестве поиска в таблице с 32 записями. 1 означает ноль 1 с, 2 означает один 1, 4 означает два 1 с и т. Д., За исключением того, что 0 означает 32 1 с.

Answer 2

На странице Bit Twiddling Hacks имеется ряд алгоритмов для подсчета конечных нулей. Любой из них можно адаптировать, просто сначала инвертировав свой номер, и, вероятно, есть разумные способы изменить действующие алгоритмы, не делая этого также. На современном процессоре с дешевыми операциями с плавающей запятой лучшее, вероятно, выглядит так:

unsigned int v=~input;            // find the number of trailing ones in input
int r;                     // the result goes here
float f = (float)(v & -v); // cast the least significant bit in v to a float
r = (*(uint32_t *)&f >> 23) - 0x7f;
if(r==-127) r=32;

Answer 3

Получив ответ от Игнасио Васкеса-Абрамса и заполнив его счетом, а не таблицей:

b = ~i & (i+1);   // this gives a 1 to the left of the trailing 1's
b--;              // this gets us just the trailing 1's that need counting
b = (b & 0x55555555) + ((b>>1) & 0x55555555);  // 2 bit sums of 1 bit numbers
b = (b & 0x33333333) + ((b>>2) & 0x33333333);  // 4 bit sums of 2 bit numbers
b = (b & 0x0f0f0f0f) + ((b>>4) & 0x0f0f0f0f);  // 8 bit sums of 4 bit numbers
b = (b & 0x00ff00ff) + ((b>>8) & 0x00ff00ff);  // 16 bit sums of 8 bit numbers
b = (b & 0x0000ffff) + ((b>>16) & 0x0000ffff); // sum of 16 bit numbers

в конце b будет содержать количество единиц (маски, сложение и смещение подсчета единиц). Если, конечно, я не обманываю. Тест перед использованием.

Answer 4

GCC имеет __builtin_ctz, а другие компиляторы имеют свои собственные встроенные функции. Просто защитите его с помощью #ifdef:

#ifdef __GNUC__
int trailingones( uint32_t in ) {
    return ~ in == 0? 32 : __builtin_ctz( ~ in );
}
#else
// portable implementation
#endif

На x86 эта встроенная команда скомпилируется в одну очень быструю инструкцию. Другие платформы могут быть несколько медленнее, но у большинства есть какая-то функция подсчета битов, которая превзойдет то, что вы можете сделать с чистыми операторами C.

Answer 5

Реализация идеи Стивена Судита ...

uint32_t n; // input value
uint8_t o;  // number of trailing one bits in n

uint8_t trailing_ones[256] = {
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 8};

uint8_t t;
do {
  t=trailing_ones[n&255];
  o+=t;
} while(t==8 && (n>>=8))

От

1 (наилучшее) до 4 (наихудшее) (в среднем 1,004) раза (1 поиск + 1 сравнение + 3 арифметических операции) минус одна арифметическая операция.

Answer 6

Возможно, есть лучшие ответы, особенно если ассемблер не исключен, но одним из жизнеспособных решений будет использование таблицы поиска. Было бы 256 записей, каждая из которых возвращала бы количество последовательных завершающих 1 бит. Примените его к младшему байту. Если это 8, обратитесь к следующему и держите счет.

Answer 7

Удивительно быстрый способ узнать количество конечных 0 приведен в Восторг хакера .

Вы можете дополнить свое целое число (или, в более общем смысле, слово), чтобы найти количество конечных единиц.

Answer 8

Принимая ответ @ phkahler, вы можете определить следующий оператор препроцессора:

#define trailing_ones(x) __builtin_ctz(~x & (x + 1))

Получив один балл от всех предыдущих, вы можете просто посчитать завершающие нули.

Answer 9

Реализация на основе ответа Игнасио Васкеса-Абрамса

uint8_t trailing_ones(uint32_t i) {
 return log2(~i & (i + 1));
}

Реализация log2 () оставлена ​​читателю как упражнение (см. здесь )

Answer 10

У меня есть этот образец для вас:

#include <stdio.h>

int trailbits ( unsigned int bits, bool zero )
{
    int bitsize = sizeof(int) * 8;
    int len = 0;
    int trail = 0;
    unsigned int compbits = bits;

    if ( zero ) compbits = ~bits;

    for ( ; bitsize; bitsize-- )
    {
        if ( compbits & 0x01 ) trail++;
        else
        {
            if ( trail > 1 ) len++;
            trail = 0;
        }
        compbits = compbits >> 1;
    }

    if ( trail > 1 ) len++;

    return len;
}

void PrintBits ( unsigned int bits )
{
    unsigned int pbit = 0x80000000;
    for ( int len=0 ; len<32; len++ )
    {
        printf ( "%c ", pbit & bits ? '1' : '0' ); 
        pbit = pbit >> 1;
    }
    printf ( "\n" );
}

void main(void)
{
    unsigned int forbyte = 0x0CC00990;

    PrintBits ( forbyte );

    printf ( "Trailing ones is %d\n", trailbits ( forbyte, false ));
    printf ( "Trailing zeros is %d\n", trailbits ( forbyte, true ));
}