Получение числа запаздывающего 1 бита
Есть ли какие-либо эффективные битовые операции, которые я могу сделать для получения числа битов набора, которыми заканчивается целое число? Например, 1110 = 10112 составил бы два запаздывающих 1 бит. 810 = 10002 был бы 0 запаздывающих 1 бит.
Существует ли лучший алгоритм для этого, чем линейный поиск? Я реализую рандомизированный список пропуска и использую случайные числа для определения максимального уровня элемента при вставке его. Я имею дело с целыми числами на 32 бита в C++.
Править: ассемблер вне рассмотрения, я интересуюсь чистым решением для C++.
11 ответов
Взяв ответ Игнасио Васкес-Абрамса и завершив его счетом, а не таблицей:
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 будет содержать счетчик единиц (маски, добавление и смещение счетчика единиц). {{1 }} Если, конечно, я не пошутил. Перед использованием проверьте.
Вычислите ~ i & (i + 1) и используйте результат для поиска в таблице с 32 записями. 1 означает ноль единиц, 2 означает одну единицу, 4 означает две единицы и так далее, за исключением того, что 0 означает 32 единицы.
Реализация идеи Стивена Судита ...
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 арифметических операции) минус одна арифметическая операция.
GCC имеет __ builtin_ctz , а другие компиляторы имеют свои собственные встроенные функции. Просто защитите его с помощью #ifdef :
#ifdef __GNUC__
int trailingones( uint32_t in ) {
return ~ in == 0? 32 : __builtin_ctz( ~ in );
}
#else
// portable implementation
#endif
На x86 эта встроенная команда будет компилироваться в одну очень быструю инструкцию. Другие платформы могут быть несколько медленнее, но у большинства есть какая-то функция подсчета битов, которая превосходит то, что вы можете делать с чистыми операторами C.
Могут быть доступны лучшие ответы, особенно если ассемблер не исключено, но одним из жизнеспособных решений было бы использование таблицы поиска. Он будет иметь 256 записей, каждая из которых возвращает количество непрерывных завершающих 1 битов. Примените его к младшему байту. Если это 8, обратитесь к следующему и ведите счет.
У меня есть для вас этот образец:
#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 ));
}
Потрясающе быстрый способ найти количество отстающих 0'ов приведен в Hacker's Delight.
Вы можете дополнить ваше целое число (или, в более общем случае, слово), чтобы найти количество идущих следом 1.
Этот код подсчитывает количество нулевых битов, взятый из здесь (есть также версия, которая зависит от 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);
}
Реализация, основанная на ответе Игнасио Васкеса-Абрамса
uint8_t trailing_ones(uint32_t i) {
return log2(~i & (i + 1));
}
Реализация log2 () оставлена в качестве упражнения для читателя (см. здесь ])
На странице 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;
http://graphics.stanford.edu/~seander/bithacks.html может дать вам немного вдохновения.