Бит тиддлинг: какой бит установлен?

Question

У меня 64-разрядное целое число без знака с установленным ровно 1 битом. Я хотел бы присвоить значение каждому из возможных 64 значений (в этом случае нечетные простые числа, поэтому 0x1 соответствует 3, 0x2 соответствует 5, ..., 0x8000000000000000 соответствует 313).

Похоже, что лучшим способом было бы преобразовать 1 -> 0, 2 -> 1, 4 -> 2, 8 -> 3, ..., 2 ^ 63 -> 63 и найти значения в массив. Но даже если это так, я не уверен, что самый быстрый способ получить в двоичном показателе. И все же могут быть более быстрые / лучшие способы.

Эта операция будет использоваться от 10 ¹⁴ до 10 ¹⁶ раз, поэтому производительность является серьезной проблемой.

Answer 1

Наконец-то оптимальное решение. Смотрите в конце этого раздела, что делать, когда на входе гарантированно будет ровно один ненулевой бит: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

Вот код:

static const int MultiplyDeBruijnBitPosition2[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 = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];

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

Обновление: вот по крайней мере одну 64-битную версию, которую я только что разработал сам, но она использует деление (на самом деле по модулю).

r = Table[v%67];

Для каждой степени 2, v%67 имеет отдельное значение, поэтому просто поместите ваши нечетные простые числа (или битовые индексы, если вы не хотите, чтобы нечетные простые числа) в правильные позиции в таблице. 3 позиции (0, 17 и 34) не используются, что может быть удобно, если вы также хотите принять все биты ноль в качестве входа.

Обновление 2: 64-разрядная версия.

r = Table[(uint64_t)(val * 0x022fdd63cc95386dull) >> 58];

Это моя оригинальная работа, но я получил B(2,6) последовательность де Брюйна с этого шахматного сайта , поэтому я не могу взять кредит ни за что, кроме как выяснить, что за де Последовательность Брюйна есть и с помощью Google. ; -)

Некоторые дополнительные замечания о том, как это работает:

Магическое число - это последовательность B(2,6) Де Брюйна. Он обладает свойством, что, если вы посмотрите на 6-битное окно, вы можете получить любое 6-битное значение в этом окне, повернув число соответствующим образом, и что каждое возможное 6-битное значение получается ровно одним поворотом.

Мы фиксируем рассматриваемое окно, чтобы оно заняло 6 верхних битовых позиций, и выбираем последовательность Де Брюина с 0 в старших 6 битах. Это позволяет нам никогда не иметь дело с ротациями битов, а только со сдвигами, так как нули будут входить в нижние биты естественным образом (и мы никогда не сможем в конечном итоге посмотреть более чем на 5 бит снизу в окне верхних 6 бит) .

Теперь входное значение этой функции является степенью 2. Таким образом, умножение последовательности Де Брюина на входное значение приводит к сдвигу битов на log2(value) бит. Теперь у нас есть в верхних 6 битах число, которое однозначно определяет, на сколько бит мы сместились, и можем использовать это в качестве индекса в таблице, чтобы получить фактическую длину сдвига.

Этот же подход можно использовать для произвольно больших или произвольно малых целых чисел, если вы хотите реализовать умножение. Вам просто нужно найти последовательность B(2,k) De Bruijn, где k - это количество битов. Ссылка на шахматную вики, которую я привел выше, содержит последовательности Де Брюина для значений k в диапазоне от 1 до 6, и некоторые быстрые поиски в Google показывают, что есть несколько статей об оптимальных алгоритмах их генерации в общем случае.

Answer 2

Если производительность является серьезной проблемой, то вы должны использовать встроенные функции / встроенные функции, чтобы использовать специфичные для процессора инструкции, такие как приведенные здесь для gcc:

http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html

- Встроенная функция: int __builtin_ffs (unsigned int x) Возвращает один плюс индекс младшего значащего 1-бита x или, если x равен нулю, возвращает ноль.

- Встроенная функция: int __builtin_clz (unsigned int x) Возвращает количество ведущих 0-битов в x, начиная с самой старшей позиции бита. Если x равен 0, результат не определен.

- Встроенная функция: int __builtin_ctz (unsigned int x) Возвращает количество завершающих 0 битов в x, начиная с позиции младшего разряда. Если х равен 0, результат не определен.

Подобные вещи являются ядром многих алгоритмов O (1), таких как планировщики ядра, которым необходимо найти первую непустую очередь, обозначенную массивом битов.

ПРИМЕЧАНИЕ: Я перечислил unsigned int версии, но у gcc также есть unsigned long long версии.

Answer 3

Вы можете использовать метод бинарного поиска:

int pos = 0;
if ((value & 0xffffffff) == 0) {
    pos += 32;
    value >>= 32;
}
if ((value & 0xffff) == 0) {
    pos += 16;
    value >>= 16;
}
if ((value & 0xff) == 0) {
    pos += 8;
    value >>= 8;
}
if ((value & 0xf) == 0) {
    pos += 4;
    value >>= 4;
}
if ((value & 0x3) == 0) {
    pos += 2;
    value >>= 2;
}
if ((value & 0x1) == 0) {
    pos += 1;
}

Это имеет преимущество перед циклами в том, что цикл уже развернут.Однако, если это действительно критично для производительности, вам нужно протестировать и измерить каждое предлагаемое решение.

Answer 4

Некоторые архитектуры (на самом деле удивительное число) имеют единственную инструкцию, которая может выполнять необходимые вычисления. На ARM это была бы инструкция CLZ (считать начальные нули). Для Intel вам помогут инструкции BSF (прямое сканирование битов) или BSR (обратное сканирование битов).

Полагаю, это не совсем C ответ, но он даст вам необходимую скорость!

Answer 5

@ Rs решение превосходно, это всего лишь 64-битный вариант, с таблицей, уже рассчитанной ...

static inline unsigned char bit_offset(unsigned long long self) {
    static const unsigned char mapping[64] = {
        [0]=0,   [1]=1,   [2]=2,   [4]=3,   [8]=4,   [17]=5,  [34]=6,  [5]=7,
        [11]=8,  [23]=9,  [47]=10, [31]=11, [63]=12, [62]=13, [61]=14, [59]=15,
        [55]=16, [46]=17, [29]=18, [58]=19, [53]=20, [43]=21, [22]=22, [44]=23,
        [24]=24, [49]=25, [35]=26, [7]=27,  [15]=28, [30]=29, [60]=30, [57]=31,
        [51]=32, [38]=33, [12]=34, [25]=35, [50]=36, [36]=37, [9]=38,  [18]=39,
        [37]=40, [10]=41, [21]=42, [42]=43, [20]=44, [41]=45, [19]=46, [39]=47,
        [14]=48, [28]=49, [56]=50, [48]=51, [33]=52, [3]=53,  [6]=54,  [13]=55,
        [27]=56, [54]=57, [45]=58, [26]=59, [52]=60, [40]=61, [16]=62, [32]=63
    };
    return mapping[((self & -self) * 0x022FDD63CC95386DULL) >> 58];
}

Я построил таблицу, используя предоставленную маску.

>>> ', '.join('[{0}]={1}'.format(((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58, bit) for bit in xrange(64))
'[0]=0, [1]=1, [2]=2, [4]=3, [8]=4, [17]=5, [34]=6, [5]=7, [11]=8, [23]=9, [47]=10, [31]=11, [63]=12, [62]=13, [61]=14, [59]=15, [55]=16, [46]=17, [29]=18, [58]=19, [53]=20, [43]=21, [22]=22, [44]=23, [24]=24, [49]=25, [35]=26, [7]=27, [15]=28, [30]=29, [60]=30, [57]=31, [51]=32, [38]=33, [12]=34, [25]=35, [50]=36, [36]=37, [9]=38, [18]=39, [37]=40, [10]=41, [21]=42, [42]=43, [20]=44, [41]=45, [19]=46, [39]=47, [14]=48, [28]=49, [56]=50, [48]=51, [33]=52, [3]=53, [6]=54, [13]=55, [27]=56, [54]=57, [45]=58, [26]=59, [52]=60, [40]=61, [16]=62, [32]=63'

если компилятор пожалуется:

>>> ', '.join(map(str, {((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58: bit for bit in xrange(64)}.values()))
'0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12'

^^^^ предполагает, что мы перебираем отсортированные ключи, в будущем это может быть не так ...

unsigned char bit_offset(unsigned long long self) {
    static const unsigned char table[64] = {
        0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48,
        28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49,
        18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43,
        21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50,
        31, 19, 15, 30, 14, 13, 12
    };
    return table[((self & -self) * 0x022FDD63CC95386DULL) >> 58];
}

простой тест:

>>> table = {((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58: bit for bit in xrange(64)}.values()
>>> assert all(i == table[(2**i * 0x022fdd63cc95386d % 2**64) >> 58] for i in xrange(64))

Answer 6

Поскольку важна скорость, предположительно не использование памяти, вот сумасшедшая идея:

w1 = первые 16 бит
w2 = 2-й 16 бит
w3 = 3-й 16 бит
w4 = 4-й 16 бит

результат = массив1 [w1] + массив2 [w2] + массив3 [w3] + массив4 [w4]

где array1..4 - это малонаселенные массивы 64K, которые содержат фактические простые значения (и ноль в позициях, которые не соответствуют позициям битов)

Answer 7

• предварительно рассчитать 1 << i (для i = 0..63) и сохранить их в массиве </li>
• использовать двоичный поиск, чтобы найти индекс в массиве заданного значения
• искать простое число в другом массиве, используя этот индекс

По сравнению с другим ответом, который я разместил здесь, для поиска индекса нужно всего 6 шагов (максимум 64). Но мне не ясно, занимает ли один шаг этого ответа больше времени, чем просто сдвиг битов и увеличение счетчика. Вы можете попробовать оба варианта.

Answer 8

Вызовите функцию расширения GNU POSIX ffsll, найденную в glibc. Если функция отсутствует, вернитесь к __builtin_ffsll. Обе функции возвращают index + 1 первого установленного бита или ноль. В Visual-C ++ вы можете использовать _BitScanForward64 .

Answer 9

См. http://graphics.stanford.edu/~seander/bithacks.html - в частности, «Поиск целочисленной логарифмической базы 2 целого числа (она же позиция наибольшего набора битов)» - для некоторых альтернативных алгоритмов. (Если вы действительно серьезно относитесь к скорости, вы можете отказаться от C, если у вашего процессора есть специальная инструкция).

Answer 10

За исключением использования сборочных или специфичных для компилятора расширений для поиска первого / последнего установленного бита, самый быстрый алгоритм - это двоичный поиск.Сначала проверьте, установлен ли какой-либо из первых 32 битов.Если это так, проверьте, установлены ли какие-либо из первых 16.Если это так, проверьте, установлены ли какие-либо из первых 8.И т.д. Ваша функция для этого может напрямую возвращать нечетное простое число на каждом листе поиска, или она может возвращать битовый индекс, который вы используете в качестве индекса массива, в таблицу нечетных простых чисел.

Вот циклреализация бинарного поиска, которую компилятор может развернуть, если она будет оптимальной:

uint32_t mask=0xffffffff;
int pos=0, shift=32, i;
for (i=6; i; i--) {
    if (!(val&mask)) {
        val>>=shift;
        pos+=shift;
    }
    shift>>=1;
    mask>>=shift;
}

val предполагается равным uint64_t, но чтобы оптимизировать его для 32-битных машин,следует в первом случае проверить, а затем выполнить цикл с 32-битной переменной val.