Как найти позицию бита с единственным битом в 64-битном значении, используя бит-манипуляцию?

Просто скажите, что у меня есть значение типа uint64_t рассматривается как последовательность октетов (1 октет = 8 бит). Значение uint64_t известно только с одним битом в позиции MSB. Таким образом, значение uint64_t может быть в одном из следующих двоичных представлений:

 00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7 00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000 pos = 15 00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000 pos = 23 00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000 pos = 31 00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000 pos = 39 00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000 pos = 47 00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 pos = 55 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 pos = 63 

Мне нужна быстрая функция, которая возвращает заданную позицию бита , но возвращает 0, если бит не установлен.

Если возможно, я хочу это без каких-либо циклов и ветвлений.

Умножьте значение на тщательно разработанную 64-битную константу, затем закройте верхние 4 бита. Для любого процессора с быстрым 64-битным умножением это, вероятно, так же оптимально, как вы можете получить.

 int field_set(uint64_t input) { uint64_t field = input * 0x20406080a0c0e1ULL; return (field >> 60) & 15; } // field_set(0x0000000000000000ULL) = 0 // field_set(0x0000000000000080ULL) = 1 // field_set(0x0000000000008000ULL) = 2 // field_set(0x0000000000800000ULL) = 3 // field_set(0x0000000080000000ULL) = 4 // field_set(0x0000008000000000ULL) = 5 // field_set(0x0000800000000000ULL) = 6 // field_set(0x0080000000000000ULL) = 7 // field_set(0x8000000000000000ULL) = 8 

clang реализует это в трех инструкциях x86_64, не считая установки и очистки кадра:

 _field_set: push %rbp mov %rsp,%rbp movabs $0x20406080a0c0e1,%rax imul %rdi,%rax shr $0x3c,%rax pop %rbp retq 

Обратите внимание, что результаты для любого другого ввода будут в значительной степени случайными. (Так что не делай этого.)

Я не думаю, что существует какой-либо возможный способ расширить этот метод, чтобы возвращать значения в диапазоне 7..63 напрямую (структура константы не позволяет этого), но вы можете преобразовать результаты в этот диапазон, умножив результат на 7.


Что касается того, как была создана эта константа, я начал со следующих замечаний:

  • Беззнаковое умножение является быстрой операцией на большинстве процессоров и может иметь полезные эффекты. Мы должны использовать его. 🙂
  • Умножение чего угодно на ноль приводит к нулю. Так как это соответствует желаемому результату для ввода без бит-бит, мы все хорошо себя чувствуем.
  • Умножение всего на 1ULL<<63 (т. 1ULL<<63 Ваше значение «pos = 63») может привести только к тому же значению или нулю. (У него не могут быть установлены более низкие биты, и нет более высоких битов для изменения.) Поэтому мы должны найти способ, чтобы это значение считалось правильным результатом.
  • Удобным способом сделать это значение является его собственный правильный результат, сдвинув его на 60 бит. Это сдвигает его до «8», что является достаточно удобным представлением. Мы можем перейти к кодированию других выходов с 1 по 7.
  • Умножение нашей константы на каждое из других битовых полей эквивалентно смещению влево на несколько бит, равное его «позиции». Смещение вправо на 60 бит приводит к появлению только 4 бит слева от данной позиции. Таким образом, мы можем создать все случаи, за исключением одного :

      uint64_t constant = ( 1ULL << (60 - 7) | 2ULL << (60 - 15) | 3ULL << (60 - 23) | 4ULL << (60 - 31) | 5ULL << (60 - 39) | 6ULL << (60 - 47) | 7ULL << (60 - 55) ); 

Пока константа 0x20406080a0c0e0ULL . Однако это не дает правильного результата для pos=63 ; эта константа четная, поэтому ее умножение на этот вход дает нуль. Мы должны установить младший бит (т. constant |= 1ULL ), чтобы заставить этот случай работать, давая нам окончательное значение 0x20406080a0c0e1ULL .

Обратите внимание, что приведенная выше конструкция может быть изменена для кодирования результатов по-разному. Однако выход 8 фиксируется, как описано выше, и весь другой выход должен вписываться в 4 бита (то есть от 0 до 15).

Вот портативное решение, которое, однако, будет медленнее, чем решения, использующие специализированные инструкции, такие как clz (подсчет ведущих нhive). Я добавил комментарии на каждом шаге алгоритма, который объясняет, как это работает.

 #include  #include  #include  /* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8] return 0 if no bit is set */ int bit_pos (uint64_t a) { uint64_t t, c; t = a - 1; // create mask c = t >> 63; // correction for zero inputs t = t + c; // apply zero correction if necessary t = t & 0x0101010101010101ULL; // mark each byte covered by mask t = t * 0x0101010101010101ULL; // sum the byte markers in uppermost byte t = (t >> 53) - 1; // retrieve count and diminish by 1 for bit position t = t + c; // apply zero correction if necessary return (int)t; } int main (void) { int i; uint64_t a; a = 0; printf ("a=%016llx bit_pos=%2d reference_pos=%2d\n", a, bit_pos(a), 0); for (i = 7; i < 64; i += 8) { a = (1ULL << i); printf ("a=%016llx bit_pos=%2d reference_pos=%2d\n", a, bit_pos(a), i); } return EXIT_SUCCESS; } 

Результат этого кода должен выглядеть так:

 a=0000000000000000 bit_pos= 0 reference_pos= 0 a=0000000000000080 bit_pos= 7 reference_pos= 7 a=0000000000008000 bit_pos=15 reference_pos=15 a=0000000000800000 bit_pos=23 reference_pos=23 a=0000000080000000 bit_pos=31 reference_pos=31 a=0000008000000000 bit_pos=39 reference_pos=39 a=0000800000000000 bit_pos=47 reference_pos=47 a=0080000000000000 bit_pos=55 reference_pos=55 a=8000000000000000 bit_pos=63 reference_pos=63 

На платформе x86_64 мой компилятор переводит bit_pos() в этот машинный код:

 bit_pos PROC lea r8, QWORD PTR [-1+rcx] shr r8, 63 mov r9, 0101010101010101H lea rdx, QWORD PTR [-1+r8+rcx] and rdx, r9 imul r9, rdx shr r9, 53 lea rax, QWORD PTR [-1+r8+r9] ret 

[Позднее обновление]

Ответ duskwuff дал мне понять, что мое первоначальное мышление было излишне запутанным. Фактически, используя подход duskwuff, желаемая функциональность может быть выражена гораздо более сжато следующим образом:

 /* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8] return 0 if no bit is set */ int bit_pos (uint64_t a) { const uint64_t magic_multiplier = (( 7ULL << 56) | (15ULL << 48) | (23ULL << 40) | (31ULL << 32) | (39ULL << 24) | (47ULL << 16) | (55ULL << 8) | (63ULL << 0)); return (int)(((a >> 7) * magic_multiplier) >> 56); } 

Любой разумный компилятор будет прекомпилировать магический множитель, который равен 0x070f171f272f373fULL . Код, испущенный для цели x86_64, сокращается до

 bit_pos PROC mov rax, 070f171f272f373fH shr rcx, 7 imul rax, rcx shr rax, 56 ret 

Если вы можете использовать POSIX, используйте функцию ffs() из strings.h (not string.h !). Он возвращает позицию наименее значимого битового набора (один индексированный) или ноль, если аргумент равен нулю. В большинстве реализаций вызов ffs() встроен и скомпилирован в соответствующую машинную команду, например bsf на x86. ffsll() также имеет ffsll() для long long аргументов, которые должны быть еще более подходящими для вашей проблемы, если они доступны.

Значение mod 0x8C дает уникальное значение для каждого из случаев.

Это значение mod 0x11 по-прежнему уникально.

Второе значение в таблице – результат mod 0x11.

 128 9 32768 5 8388608 10 2147483648 0 549755813888 14 140737488355328 2 36028797018963968 4 9223372036854775808 15 

Поэтому достаточно простой таблицы поиска.

 int find_bit(uint64_t bit){ int lookup[] = { the seventeen values }; return lookup[ (bit % 0x8C) % 0x11]; } 

Нет разветвлений, никаких трюков компилятора.

Для полноты, массив

 { 31, 0, 47, 15, 55, 0, 0, 7, 23, 0, 0, 0, 39, 63, 0, 0} 

Если вам нужен алгоритм работы, а не встроенный, это сделает это. Он дает бит число наиболее значимых 1 бит, даже если установлено более одного бита. Он сужает положение, итеративно разделяя рассматриваемый диапазон бит на половину, проверяя, есть ли какие-либо биты, установленные в верхней половине, занимая половину, как новый бит, если это так, и в противном случае принимают нижнюю половину в качестве нового битового диапазона ,

 #define TRY_WINDOW(bits, n, msb) do { \ uint64_t t = n >> bits; \ if (t) { \ msb += bits; \ n = t; \ } \ } while (0) int msb(uint64_t n) { int msb = 0; TRY_WINDOW(32, n, msb); TRY_WINDOW(16, n, msb); TRY_WINDOW( 8, n, msb); TRY_WINDOW( 4, n, msb); TRY_WINDOW( 2, n, msb); TRY_WINDOW( 1, n, msb); return msb; } 

Тег C ++ был удален, но вот переносимый C ++-ответ, тем не менее, поскольку вы можете скомпилировать его с C ++ и использовать интерфейс extern C :

Если у вас есть сила 2, и вы вычитаете ее, вы получаете двоичное число с количеством установленных битов, равным положению

Способ подсчета количества заданных битов (двоичный 1 с) завернут, предположительно наиболее эффективно каждой реализацией stl, в std::bitset функции std::bitset

Обратите внимание, что ваша спецификация имеет 0 возвращенных для 0 или 1 , поэтому я добавил as_specified_pos для удовлетворения этого требования. Лично я бы просто оставил, чтобы вернуть натуральное значение 64 когда прошло 0 чтобы иметь возможность дифференцировать и для скорости.

Следующий код должен быть чрезвычайно переносимым и, скорее всего, оптимизированным на платформу поставщиками компиляторов:

 #include  uint64_t pos(uint64_t val) { return std::bitset<64>(val-1).count(); } uint64_t as_specified_pos(uint64_t val) { return (val) ? pos(val) : 0; } 

В Linux с g ++ я получаю следующий дизассемблированный код:

 0000000000000000 : 0: 48 8d 47 ff lea -0x1(%rdi),%rax 4: f3 48 0f b8 c0 popcnt %rax,%rax 9: c3 retq a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1) 0000000000000010 : 10: 31 c0 xor %eax,%eax 12: 48 85 ff test %rdi,%rdi 15: 74 09 je 20  17: 48 8d 47 ff lea -0x1(%rdi),%rax 1b: f3 48 0f b8 c0 popcnt %rax,%rax 20: f3 c3 repz retq 

Современное оборудование имеет специальные инструкции для этого (LZCNT, TZCNT на процессорах Intel).

Большинство компиляторов имеют встроенные функции, которые легко сгенерируют их. См. Следующую страницу wikipedia .

 00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7 

…, но возвращает 0, если бит не установлен.

Это вернет то же самое, если первый бит или бит не установлен; однако на x86_64 это именно то, что делает bsrq:

 int bsrq_x86_64(uint64_t x){ int ret; asm("bsrq %0, %1":"=r"(ret):"r"(x)); return ret; } 

Тем не мение; если первый бит установлен, он также вернет 0; это метод, который будет выполняться в постоянное время (без циклов или ветвлений) и возвращает -1, если не установлены биты (чтобы отличить от того, когда установлен первый бит).

 int find_bit(unsigned long long x){ int ret=0, cmp = (x>(1LL<<31))<<5; //32 if true else 0 ret += cmp; x >>= cmp; cmp = (x>(1<<15))<<4; //16 if true else 0 ret += cmp; x >>= cmp; cmp = (x>(1<<7))<<3; //8 ret += cmp; x >>= cmp; cmp = (x>(1<<3))<<2; //4 ret += cmp; x >>= cmp; cmp = (x>(1<<1))<<1; //2 ret += cmp; x >>= cmp; cmp = (x>1); ret += cmp; x >>= cmp; ret += x; return ret-1; } 

Технически это просто возвращает положение наиболее значимого бита. В зависимости от типа используемого поплавка это можно сделать за меньшее количество операций, используя быстрый обратный квадрат или другие бит-хаки

BTW, Если вы не против использования встроенных компиляторов, вы можете просто сделать:

__builtin_popcountll(n-1) или __builtin_ctzll(n) или __builtin_ffsll(n)-1

Простое решение для поиска. m=67 – наименьшее целое число, для которого значения (1< различны, for k . С (python транспонируемый код):

 lut = [-1]*67 for i in range(0,64) : lut[(1< 

Тогда lut[a%67] дает k если a = 1< . -1 не используются.