Положение младшего значащего бита, который установлен
Я ищу эффективный способ определения позиции младшего значащего бита, который установлен в целое число, например, для 0x0FF0 это будет 4.
Тривиальная реализация такова:
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
return pos;
}
Есть идеи, как выжать из него несколько циклов?
(Примечание: этот вопрос для людей, которым нравятся такие вещи, а не для людей, которые говорят мне, что ксизоптимизация - это зло.)
[править] Спасибо всем за идеи! Я также узнал несколько других вещей. Здорово!
22 ответа
Bit Twiddling Hacks предлагает отличную коллекцию бит-тиддлинг-хаков с прикрепленным обсуждением производительности / оптимизации. Мое любимое решение для вашей проблемы (с этого сайта) - "умножение и поиск":
unsigned int v; // find the number of trailing zeros in 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
Полезные ссылки:
- " Использование последовательности де Брюйна для индексации 1 в компьютерном слове" - объяснение того, почему работает приведенный выше код.
- " Представление доски> Битборды> BitScan" - подробный анализ этой проблемы с особым акцентом на шахматное программирование
Почему бы не использовать встроенный FFS? (Я взял справочную страницу из Linux, но она более широко доступна.)
ffs (3) - справочная страница по Linux
название
ffs - найти первый бит, установленный в слове
конспект
#include <strings.h> int ffs(int i); #define _GNU_SOURCE #include <string.h> int ffsl(long int i); int ffsll(long long int i);Описание
Функция ffs() возвращает позицию первого (наименее значимого) бита, установленного в слове i. Наименее значимый бит - это позиция 1, а наиболее значимая позиция, например, 32 или 64. Функции ffsll() и ffsl() делают то же самое, но принимают аргументы, возможно, разного размера.
Возвращаемое значение
Эти функции возвращают позицию первого установленного бита или 0, если в i не установлено ни одного бита.
В соответствии с
4.3BSD, POSIX.1-2001.
Заметки
Системы BSD имеют прототип в
<string.h>,
Есть инструкция по сборке x86 (bsf) это будет делать.:)
Больше оптимизировано?!
Примечание:
Оптимизация на этом уровне по своей природе зависит от архитектуры. Современные процессоры слишком сложны (с точки зрения предсказания ветвлений, пропадания кэша, конвейерной обработки), поэтому трудно предсказать, какой код будет выполняться быстрее на какой архитектуре. Сокращение операций с 32 до 9 или подобных вещей может даже снизить производительность на некоторых архитектурах. Оптимизированный код в одной архитектуре может привести к ухудшению кода в другой. Я думаю, что вы либо оптимизируете это для конкретного процессора, либо оставите его как есть и позволите компилятору выбирать, что он считает лучше.
В большинстве современных архитектур есть некоторая инструкция для поиска позиции самого младшего установленного бита или самого высокого установленного бита, или подсчета количества ведущих нулей и т. Д.
Если у вас есть одна инструкция этого класса, вы можете дешево подражать другим.
Найдите время, чтобы проработать это на бумаге и понять, что x & (x-1) очистит младший установленный бит в х, и ( x & ~(x-1) ) будет возвращать только самый низкий установленный бит, независимо от архитектуры, длины слова и т. д. Зная это, тривиально использовать аппаратный счетчик-ведущий-ноль / самый высокий-установленный бит, чтобы найти самый низкий установленный бит, если нет явной инструкции для выполнения так.
Если соответствующая аппаратная поддержка отсутствует вообще, приведенная здесь реализация умножения-и-поиска начальных нулей или одного из них на странице Взломы битовых комбинаций может быть легко преобразована для получения младшего установленного бита с использованием вышеуказанных тождеств и имеет преимущество того, что не имеет ответвлений.
Множество решений, а не эталон. Вам, людям, должно быть стыдно за себя;-)
Моя машина - Intel i530 (2,9 ГГц), работающая под управлением Windows 7 64-разрядная версия. Я скомпилировал 32-битную версию MinGW.
$ gcc --version
gcc.exe (GCC) 4.7.2
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop. Time = 2.91 (Original questioner)
De Bruijn multiply. Time = 1.16 (Tykhyy)
Lookup table. Time = 0.36 (Andrew Grant)
FFS instruction. Time = 0.90 (ephemient)
Branch free mask. Time = 3.48 (Dan / Jim Balter)
Double hack. Time = 3.41 (DocMax)
$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop. Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table. Time = 0.35
FFS instruction. Time = 0.68
Branch free mask. Time = 3.49
Double hack. Time = 0.92
Мой код:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ARRAY_SIZE 65536
#define NUM_ITERS 5000 // Number of times to process array
int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
if (value == 0)
continue;
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
total += pos + 1;
}
}
return total;
}
int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
static const int MultiplyDeBruijnBitPosition[32] =
{
1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9,
32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
};
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int c = nums[i];
total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
}
}
return total;
}
unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
unsigned mask = 1;
for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
if (num & mask) {
return cnt;
}
}
return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned int value = nums[i];
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
unsigned char *bytes = (unsigned char *)&value;
if (bytes[0])
total += lowestBitTable[bytes[0]];
else if (bytes[1])
total += lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
total += lowestBitTable[bytes[2]] + 16;
else
total += lowestBitTable[bytes[3]] + 24;
}
}
return total;
}
int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
total += __builtin_ffs(nums[i]);
}
}
return total;
}
int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
}
}
return total;
}
int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
int total = 0; // Prevent compiler from optimizing out the code
for (int j = 0; j < NUM_ITERS; j++) {
for (int i = 0; i < ARRAY_SIZE; i++) {
unsigned value = nums[i];
double d = value ^ (value - !!value);
total += (((int*)&d)[1]>>20)-1022;
}
}
return total;
}
int main() {
unsigned nums[ARRAY_SIZE];
for (int i = 0; i < ARRAY_SIZE; i++) {
nums[i] = rand() + (rand() << 15);
}
for (int i = 0; i < 256; i++) {
lowestBitTable[i] = get_lowest_set_bit(i);
}
clock_t start_time, end_time;
int result;
start_time = clock();
result = find_first_bits_naive_loop(nums);
end_time = clock();
printf("Naive loop. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_de_bruijn(nums);
end_time = clock();
printf("De Bruijn multiply. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_lookup_table(nums);
end_time = clock();
printf("Lookup table. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_ffs_instruction(nums);
end_time = clock();
printf("FFS instruction. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_branch_free_mask(nums);
end_time = clock();
printf("Branch free mask. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
start_time = clock();
result = find_first_bits_double_hack(nums);
end_time = clock();
printf("Double hack. Time = %.2f, result = %d\n",
(end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}
Самым быстрым (не внутренним / не ассемблерным) решением этого является поиск младшего байта, а затем использование этого байта в таблице поиска с 256 записями. Это дает вам наихудшую производительность из четырех условных инструкций и наилучший случай из 1. Не только это наименьшее количество инструкций, но и наименьшее количество ветвей, что очень важно для современного оборудования.
Ваша таблица (256 8-битных записей) должна содержать индекс LSB для каждого числа в диапазоне 0-255. Вы проверяете каждый байт своего значения и находите младший ненулевой байт, а затем используете это значение для поиска реального индекса.
Для этого требуется 256 байтов памяти, но если скорость этой функции так важна, то 256 байтов того стоят,
Например
byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};
unsigned GetLowestBitPos(unsigned value)
{
// note that order to check indices will depend whether you are on a big
// or little endian machine. This is for little-endian
byte* bytes = (byte*)value;
if (bytes[0])
return lowestBitTable[bytes[0]];
else if (bytes[1])
return lowestBitTable[bytes[1]] + 8;
else if (bytes[2])
return lowestBitTable[bytes[2]] + 16;
else
return lowestBitTable[bytes[3]] + 24;
}
ОМГ только что завернул.
Чего не хватает большинству этих примеров, так это небольшого понимания того, как работает все оборудование.
Каждый раз, когда у вас есть ветвь, процессор должен угадать, какая ветвь будет взята. Канал инструкций загружается с инструкциями, которые ведут по предполагаемому пути. Если ЦП угадал неправильно, канал инструкций сбрасывается, а другая ветвь должна быть загружена.
Рассмотрим простой цикл while сверху. Предположение будет оставаться в цикле. Это будет неправильно по крайней мере один раз, когда он выйдет из цикла. Это промоет канал инструкций. Это поведение немного лучше, чем догадываться, что он выйдет из цикла, и в этом случае он будет очищать канал инструкций на каждой итерации.
Количество потерянных циклов ЦП сильно варьируется от одного типа процессора к другому. Но вы можете ожидать от 20 до 150 потерянных циклов ЦП.
Следующая худшая группа, где вы думаете, что вы собираетесь сэкономить несколько итераций, разделив значение на более мелкие части и добавив еще несколько ветвей. Каждая из этих ветвей добавляет дополнительную возможность очистить канал инструкций и стоит еще от 20 до 150 тактов.
Давайте рассмотрим, что происходит, когда вы ищите значение в таблице. Скорее всего, значение в данный момент отсутствует в кэше, по крайней мере, не в первый раз, когда вызывается ваша функция. Это означает, что процессор останавливается, пока значение загружается из кеша. Опять же, это зависит от одной машины к другой. Новые чипы Intel фактически используют эту возможность для обмена потоками, пока текущий поток ожидает завершения загрузки кэша. Это легко может быть дороже, чем очистка канала инструкций, однако, если вы выполняете эту операцию несколько раз, она может произойти только один раз.
Очевидно, что самым быстрым решением с постоянным временем является решение, которое включает в себя детерминистическую математику. Чистое и элегантное решение.
Мои извинения, если это уже было покрыто.
Каждый компилятор, который я использую, за исключением XCODE AFAIK, имеет встроенные функции компилятора как для прямого, так и для обратного битового сканирования. Они будут скомпилированы в одну инструкцию по сборке на большинстве аппаратных средств без пропусков Cache, Miss-Prediction и других программистов.
Для компиляторов Microsoft используйте _BitScanForward & _BitScanReverse.
Для GCC используйте __builtin_ffs, __builtin_clz, __builtin_ctz.
Кроме того, пожалуйста, воздержитесь от публикации ответа и, возможно, вводите в заблуждение новичков, если вы недостаточно осведомлены об обсуждаемой теме.
Извините, я полностью забыл предоставить решение. Это код, который я использую на IPAD, в котором нет инструкции уровня сборки для этой задачи:
unsigned BitScanLow_BranchFree(unsigned value)
{
bool bwl = (value & 0x0000ffff) == 0;
unsigned I1 = (bwl * 15);
value = (value >> I1) & 0x0000ffff;
bool bbl = (value & 0x00ff00ff) == 0;
unsigned I2 = (bbl * 7);
value = (value >> I2) & 0x00ff00ff;
bool bnl = (value & 0x0f0f0f0f) == 0;
unsigned I3 = (bnl * 3);
value = (value >> I3) & 0x0f0f0f0f;
bool bsl = (value & 0x33333333) == 0;
unsigned I4 = (bsl * 1);
value = (value >> I4) & 0x33333333;
unsigned result = value + I1 + I2 + I3 + I4 - 1;
return result;
}
Здесь нужно понять, что дорого стоит не сравнение, а ответвление, которое происходит после сравнения. Сравнение в этом случае принудительно устанавливается на значение 0 или 1 с.. == 0, и результат используется для объединения математических вычислений, которые произошли бы по обе стороны ветви.
Редактировать:
Код выше полностью сломан. Этот код работает и по-прежнему без веток (если оптимизирован):
int BitScanLow_BranchFree(ui value)
{
int i16 = !(value & 0xffff) << 4;
value >>= i16;
int i8 = !(value & 0xff) << 3;
value >>= i8;
int i4 = !(value & 0xf) << 2;
value >>= i4;
int i2 = !(value & 0x3) << 1;
value >>= i2;
int i1 = !(value & 0x1);
int i0 = (value >> i1) & 1? 0 : -32;
return i16 + i8 + i4 + i2 + i1 + i0;
}
Возвращает -1, если дано 0. Если вас не волнует 0 или вы хотите получить 31 за 0, удалите вычисление i0, сэкономив часть времени.
Спустя 11 лет у нас наконец-то есть: countr_zero
Молодец C++20
Вдохновленный этим похожим постом, который включает поиск заданного бита, я предлагаю следующее:
unsigned GetLowestBitPos(unsigned value)
{
double d = value ^ (value - !!value);
return (((int*)&d)[1]>>20)-1023;
}
Плюсы:
- без петель
- нет ветвления
- работает в постоянном времени
- обрабатывает значение =0, возвращая результат, выходящий за пределы
- только две строки кода
Минусы:
- Предполагается, что в кодированном виде немного порядка байтов (может быть исправлено путем изменения констант).
- предполагает, что double - это реальное число с плавающей запятой *8 IEEE (IEEE 754)
Обновление: Как отмечено в комментариях, объединение является более чистой реализацией (по крайней мере, для C) и будет выглядеть так:
unsigned GetLowestBitPos(unsigned value)
{
union {
int i[2];
double d;
} temp = { .d = value ^ (value - !!value) };
return (temp.i[1] >> 20) - 1023;
}
Это предполагает 32-битные целочисленные значения с прямым порядком хранения для всего (например, процессоры x86).
Это может быть сделано в худшем случае менее 32 операций:
Принцип: проверка на 2 или более бит так же эффективна, как и проверка на 1 бит.
Так, например, ничто не мешает вам проверять, для какой группы оно сначала, а затем проверять каждый бит от наименьшего к наибольшему в этой группе.
Так...
если вы проверяете 2 бита за раз, у вас в худшем случае (Нбит /2) + 1 проверка всего.
если вы проверяете 3 бита за раз, у вас в худшем случае (Нбит /3) + 2 проверки всего.
...
Оптимальным будет проверка в группах по 4. Что в худшем случае потребует 11 операций вместо ваших 32.
Наилучший случай - от 1 проверки ваших алгоритмов до 2 проверок, если вы используете эту идею группировки. Но эта дополнительная 1 проверка в лучшем случае стоит того, чтобы сэкономить наихудший случай.
Примечание: я записываю это полностью вместо использования цикла, потому что это более эффективно.
int getLowestBitPos(unsigned int value)
{
//Group 1: Bits 0-3
if(value&0xf)
{
if(value&0x1)
return 0;
else if(value&0x2)
return 1;
else if(value&0x4)
return 2;
else
return 3;
}
//Group 2: Bits 4-7
if(value&0xf0)
{
if(value&0x10)
return 4;
else if(value&0x20)
return 5;
else if(value&0x40)
return 6;
else
return 7;
}
//Group 3: Bits 8-11
if(value&0xf00)
{
if(value&0x100)
return 8;
else if(value&0x200)
return 9;
else if(value&0x400)
return 10;
else
return 11;
}
//Group 4: Bits 12-15
if(value&0xf000)
{
if(value&0x1000)
return 12;
else if(value&0x2000)
return 13;
else if(value&0x4000)
return 14;
else
return 15;
}
//Group 5: Bits 16-19
if(value&0xf0000)
{
if(value&0x10000)
return 16;
else if(value&0x20000)
return 17;
else if(value&0x40000)
return 18;
else
return 19;
}
//Group 6: Bits 20-23
if(value&0xf00000)
{
if(value&0x100000)
return 20;
else if(value&0x200000)
return 21;
else if(value&0x400000)
return 22;
else
return 23;
}
//Group 7: Bits 24-27
if(value&0xf000000)
{
if(value&0x1000000)
return 24;
else if(value&0x2000000)
return 25;
else if(value&0x4000000)
return 26;
else
return 27;
}
//Group 8: Bits 28-31
if(value&0xf0000000)
{
if(value&0x10000000)
return 28;
else if(value&0x20000000)
return 29;
else if(value&0x40000000)
return 30;
else
return 31;
}
return -1;
}
Почему бы не использовать бинарный поиск? Это будет всегда завершаться после 5 операций (при условии, что размер int равен 4 байтам):
if (0x0000FFFF & value) {
if (0x000000FF & value) {
if (0x0000000F & value) {
if (0x00000003 & value) {
if (0x00000001 & value) {
return 1;
} else {
return 2;
}
} else {
if (0x0000004 & value) {
return 3;
} else {
return 4;
}
}
} else { ...
} else { ...
} else { ...
Нашел этот хитрый трюк, используя "волшебные маски" в "Искусстве программирования, часть 4", который делает это за O(log(n)) время для n-битного числа. [с log (n) лишним пробелом]. Типичными решениями, проверяющими установленный бит, является либо O (n), либо требуется O (n) дополнительное пространство для таблицы поиска, так что это хороший компромисс.
Волшебные маски:
m0 = (...............01010101)
m1 = (...............00110011)
m2 = (...............00001111)
m3 = (.......0000000011111111)
....
Ключевая идея: Нет конечных нулей в x = 1 * [(x & m0) = 0] + 2 * [(x & m1) = 0] + 4 * [(x & m2) = 0] + ...
int lastSetBitPos(const uint64_t x) {
if (x == 0) return -1;
//For 64 bit number, log2(64)-1, ie; 5 masks needed
int steps = log2(sizeof(x) * 8); assert(steps == 6);
//magic masks
uint64_t m[] = { 0x5555555555555555, // .... 010101
0x3333333333333333, // .....110011
0x0f0f0f0f0f0f0f0f, // ...00001111
0x00ff00ff00ff00ff, //0000000011111111
0x0000ffff0000ffff,
0x00000000ffffffff };
//Firstly extract only the last set bit
uint64_t y = x & -x;
int trailZeros = 0, i = 0 , factor = 0;
while (i < steps) {
factor = ((y & m[i]) == 0 ) ? 1 : 0;
trailZeros += factor * pow(2,i);
++i;
}
return (trailZeros+1);
}
Согласно странице BitScan по шахматному программированию и моим собственным измерениям, вычитание и xor быстрее, чем отрицание и маска.
(Обратите внимание, что если вы собираетесь считать завершающие нули в 0, метод, как у меня это возвращает 63 тогда как отрицание и маска возвращаются 0.)
Вот 64-битное вычитание и xor:
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];
Для справки, вот 64-битная версия метода negate и mask:
unsigned long v; // find the number of trailing zeros in 64-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[64] =
{
0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];
unsigned GetLowestBitPos(unsigned value)
{
if (value & 1) return 1;
if (value & 2) return 2;
if (value & 4) return 3;
if (value & 8) return 4;
if (value & 16) return 5;
if (value & 32) return 6;
if (value & 64) return 7;
if (value & 128) return 8;
if (value & 256) return 9;
if (value & 512) return 10;
if (value & 1024) return 11;
if (value & 2048) return 12;
if (value & 4096) return 13;
if (value & 8192) return 14;
if (value & 16384) return 15;
if (value & 32768) return 16;
if (value & 65536) return 17;
if (value & 131072) return 18;
if (value & 262144) return 19;
if (value & 524288) return 20;
if (value & 1048576) return 21;
if (value & 2097152) return 22;
if (value & 4194304) return 23;
if (value & 8388608) return 24;
if (value & 16777216) return 25;
if (value & 33554432) return 26;
if (value & 67108864) return 27;
if (value & 134217728) return 28;
if (value & 268435456) return 29;
if (value & 536870912) return 30;
return 31;
}
50% всех чисел вернутся в первой строке кода.
75% всех чисел вернутся в первые 2 строки кода.
87% всех чисел вернутся в первые 3 строки кода.
94% всех чисел вернутся в первые 4 строки кода.
97% всех чисел вернутся в первые 5 строк кода.
и т.п.
Я думаю, что люди, которые жалуются на то, насколько неэффективен сценарий наихудшего случая для этого кода, не понимают, как редко это будет происходить.
Другой метод (разделение по модулям и поиск) заслуживает особого упоминания здесь по той же ссылке, предоставленной @anton-tykhyy. этот метод очень похож по производительности на метод умножения и поиска Дебрюйна с небольшим, но важным отличием.
модуль деления и поиска
unsigned int v; // find the number of trailing zeros in v
int r; // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37];
метод деления и поиска модуля возвращает разные значения для v=0x00000000 и v=FFFFFFFF, тогда как метод умножения и поиска DeBruijn возвращает ноль на обоих входах.
тестовое задание:-
unsigned int n1=0x00000000, n2=0xFFFFFFFF;
MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */
Еще одно решение, возможно, не самое быстрое, но, кажется, довольно хорошее.
По крайней мере, у него нет ветвей.;)
uint32 x = ...; // 0x00000001 0x0405a0c0 0x00602000
x |= x << 1; // 0x00000003 0x0c0fe1c0 0x00e06000
x |= x << 2; // 0x0000000f 0x3c3fe7c0 0x03e1e000
x |= x << 4; // 0x000000ff 0xffffffc0 0x3fffe000
x |= x << 8; // 0x0000ffff 0xffffffc0 0xffffe000
x |= x << 16; // 0xffffffff 0xffffffc0 0xffffe000
// now x is filled with '1' from the least significant '1' to bit 31
x = ~x; // 0x00000000 0x0000003f 0x00001fff
// now we have 1's below the original least significant 1
// let's count them
x = x & 0x55555555 + (x >> 1) & 0x55555555;
// 0x00000000 0x0000002a 0x00001aaa
x = x & 0x33333333 + (x >> 2) & 0x33333333;
// 0x00000000 0x00000024 0x00001444
x = x & 0x0f0f0f0f + (x >> 4) & 0x0f0f0f0f;
// 0x00000000 0x00000006 0x00000508
x = x & 0x00ff00ff + (x >> 8) & 0x00ff00ff;
// 0x00000000 0x00000006 0x0000000d
x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
// 0x00000000 0x00000006 0x0000000d
// least sign.bit pos. was: 0 6 13
Вы можете проверить, установлены ли какие-либо биты младшего разряда. Если это так, то посмотрите на нижний порядок оставшихся битов. например,:
32bit int - проверить, установлены ли какие-либо из первых 16. Если так, проверьте, установлены ли какие-либо из первых 8. если так,....
если нет, проверьте, установлены ли какие-либо из верхних 16..
По сути это бинарный поиск.
Смотрите мой ответ здесь, чтобы узнать, как это сделать с помощью одной инструкции x86, за исключением того, что для поиска младшего значащего набора битов вам понадобится BSF ("bit scan forward") вместо BSR описано там.
Если C++11 доступен для вас, компилятор иногда может выполнить задачу за вас:)
constexpr std::uint64_t lssb(const std::uint64_t value)
{
return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}
Результат - индекс на основе 1.
Это в отношении @Anton Tykhyy ответа
Вот моя реализация constexpr на C++11, которая покончила с приведениями и сняла предупреждение в VC++17, урезав 64-битный результат до 32 бит:
constexpr uint32_t DeBruijnSequence[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
constexpr uint32_t ffs ( uint32_t value )
{
return DeBruijnSequence[
(( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
>> 27];
}
Чтобы обойти проблему 0x1 и 0x0, возвращающих 0, вы можете сделать:
constexpr uint32_t ffs ( uint32_t value )
{
return (!value) ? 32 : DeBruijnSequence[
(( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
>> 27];
}
но если компилятор не может или не будет предварительно обрабатывать вызов, он добавит пару циклов к вычислению.
Наконец, если интересно, вот список статических утверждений для проверки того, что код выполняет то, для чего предназначен:
static_assert (ffs(0x1) == 0, "Find First Bit Set Failure.");
static_assert (ffs(0x2) == 1, "Find First Bit Set Failure.");
static_assert (ffs(0x4) == 2, "Find First Bit Set Failure.");
static_assert (ffs(0x8) == 3, "Find First Bit Set Failure.");
static_assert (ffs(0x10) == 4, "Find First Bit Set Failure.");
static_assert (ffs(0x20) == 5, "Find First Bit Set Failure.");
static_assert (ffs(0x40) == 6, "Find First Bit Set Failure.");
static_assert (ffs(0x80) == 7, "Find First Bit Set Failure.");
static_assert (ffs(0x100) == 8, "Find First Bit Set Failure.");
static_assert (ffs(0x200) == 9, "Find First Bit Set Failure.");
static_assert (ffs(0x400) == 10, "Find First Bit Set Failure.");
static_assert (ffs(0x800) == 11, "Find First Bit Set Failure.");
static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure.");
static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure.");
static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure.");
static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure.");
static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure.");
static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure.");
static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure.");
static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure.");
static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure.");
static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure.");
static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure.");
static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure.");
static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure.");
static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure.");
static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure.");
static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure.");
static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure.");
static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure.");
static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure.");
static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure.");
Вот одна простая альтернатива, хотя поиск журналов немного дорогостоящий.
if(n == 0)
return 0;
return log2(n & -n)+1; //Assuming the bit index starts from 1
Недавно я увидел, что сингапурский премьер опубликовал программу, которую он написал на Facebook, есть одна строка, чтобы упомянуть об этом..
Логика просто "value & -value", предположим, что у вас есть 0x0FF0, затем 0FF0 & (F00F+1), что равно 0x0010, что означает, что младший 1 находится в 4-м бите..:)
Если у вас есть ресурсы, вы можете пожертвовать памятью, чтобы улучшить скорость:
static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
return bitPositions[value];
}
Примечание. Эта таблица будет занимать не менее 4 ГБ (16 ГБ, если оставить тип возврата как unsigned). Это пример обмена одного ограниченного ресурса (ОЗУ) на другой (скорость выполнения).
Если ваша функция должна оставаться переносимой и работать максимально быстро любой ценой, это будет путь. В большинстве реальных приложений таблица 4 ГБ нереальна.