Бит-скручивание: какой бит установлен?

Ответ 1

Если производительность является серьезной проблемой, вы должны использовать встроенные/встроенные функции для использования инструкций, специфичных для процессора, таких как те, которые были найдены здесь для 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, результат равен undefined.

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

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

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

Ответ 2

Наконец, оптимальное решение. См. Конец этого раздела, что делать, когда на вход гарантируется ровно один ненулевой бит: 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) последовательность De Bruijn из этот шахматный сайт, поэтому я не могу взять на себя ответственность за что-либо, кроме определения последовательности De Bruijn и использования Google.; -)

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

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

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

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

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

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

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

Ответ 4

В некоторых архитектурах (на самом деле, на верхнем уровне) есть одна команда, которая может выполнить нужный вам расчет. В ARM это будет команда CLZ (count leading zeroes). Для Intel команда BSF (бит-сканирование вперед) или BSR (бит-сканирование назад) поможет вам.

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

Ответ 5

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

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

Ответ 6

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

w1 = 1-й 16 бит
w2 = второй 16 бит
w3 = третий 16 бит
w4 = 4-й 16 бит

result = array1 [w1] + array2 [w2] + array3 [w3] + array4 [w4]

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

Ответ 7

@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))

Ответ 8

За исключением использования расширений для сборки или компилятора, чтобы найти установленный первый/последний бит, самым быстрым алгоритмом является двоичный поиск. Сначала проверьте, установлен ли какой-либо из первых 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.

Ответ 9

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

Ответ 10

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

Ответ 11

unsigned bit_position = 0;
while ((value & 1) ==0)
{
   ++bit_position;
   value >>= 1;
}

Затем посмотрите на простые числа, основанные на бит_позиции, как вы говорите.

Ответ 12

Вы можете обнаружить, что log (n)/log (2) дает вам 0, 1, 2,... вы в разумные сроки. В противном случае может быть полезной некоторая форма подхода, основанного на хэш-таблице.

Ответ 13

Другой ответ, предполагающий IEEE float:

int get_bit_index(uint64_t val)
{
    union { float f; uint32_t i; } u = { val };
    return (u.i>>23)-127;
}

Он работает так, как указано для введенных вами значений (в точности, 1 бит), а также имеет полезное поведение для других значений (попытайтесь выяснить, что именно такое поведение). Не знаю, быстро или медленно; вероятно, зависит от вашего компьютера и компилятора.

Ответ 14

Из источника GnuChess:

unsigned char leadz (BitBoard b)
/**************************************************************************
 *
 *  Returns the leading bit in a bitboard.  Leftmost bit is 0 and
 *  rightmost bit is 63.  Thanks to Robert Hyatt for this algorithm.
 *
 ***************************************************************************/
{
  if (b >> 48) return lzArray[b >> 48];
  if (b >> 32) return lzArray[b >> 32] + 16;
  if (b >> 16) return lzArray[b >> 16] + 32;
  return lzArray[b] + 48;
}

Здесь lzArray - это прегенерированный массив размером 2 ^ 16. Это сэкономит вам 50% операций по сравнению с полным бинарным поиском.