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

Ответ 1

Умножьте значение на тщательно разработанную 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 (т.е. ваше значение "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; эта константа четная, поэтому ее умножение на этот вход дает нуль. Мы должны установить младший бит (i.e, constant |= 1ULL), чтобы этот случай работал, давая нам окончательное значение 0x20406080a0c0e1ULL.

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

Ответ 2

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

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/* 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

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

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

Ответ 3

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

Ответ 4

Значение 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}

Ответ 5

Если вам нужен алгоритм работы, а не встроенный, это сделает это. Он дает бит число наиболее значимых 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;
}

Ответ 6

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

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

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

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

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

#include <bitset>

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 <pos(unsigned long)>:
   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 <as_specified_pos(unsigned long)>:
  10:   31 c0                   xor    %eax,%eax
  12:   48 85 ff                test   %rdi,%rdi
  15:   74 09                   je     20 <as_specified_pos(unsigned long)+0x10>
  17:   48 8d 47 ff             lea    -0x1(%rdi),%rax
  1b:   f3 48 0f b8 c0          popcnt %rax,%rax
  20:   f3 c3                   repz retq

Ответ 7

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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

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