Подтвердить что ты не робот

Получение числа завершающих 1 бит

Есть ли какие-либо эффективные побитовые операции, которые я могу сделать, чтобы получить количество битов набора, с которыми заканчивается целое число? Например, 11 10= 1011 2 будут двумя конечными 1 битами. 8 10= 1000 2 будет 0 завершать 1 бит.

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

Изменить: невозможно установить ассемблер, меня интересует чистое решение на С++.

4b9b3361

ОТВЕТЫ

Ответ 1

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

b = ~i & (i+1);   // this gives a 1 to the left of the trailing 1's
b--;              // this gets us just the trailing 1 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 будет содержать счет 1 (маски, добавление и перемещение счетчиков 1). Если конечно, я не схожу с ума. Тест перед использованием.

Ответ 2

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

Ответ 3

Страница 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;

Ответ 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.

Ответ 5

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

Ответ 6

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

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 арифметических операции) за вычетом одной арифметической операции.

Ответ 7

Исключительно быстрый способ найти число конечных 0 приведен в Hacker Delight.

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

Ответ 8

Этот код подсчитывает количество конечных нулевых битов, взятых из здесь (там также версия, которая зависит от 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);
}

Ответ 10

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

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

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

Ответ 11

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

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

По мере того как вы получаете один, оставшийся до всех предыдущих, вы можете просто подсчитать конечные нули.

Ответ 12

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

#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 ));
}