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

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

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

результат = array1 [w1] + array2 [w2] + array3 [w3] + array4 [w4]

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

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

Для каждой степени двойки 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 битах. Это делает так, что нам никогда не придется иметь дело с ротацией битов, а только с сдвигами, поскольку нули будут входить в нижние биты естественным образом (и мы никогда не сможем в конечном итоге смотреть на более чем 5 бит снизу в верхнем 6-битном окне) .

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

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

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

Затем найдите простые числа на основе bit_position, как вы говорите.

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

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

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

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

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

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

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

Из источника 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% операций по сравнению с полным двоичным поиском.

Еще один ответ, предполагающий использование IEEE float:

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

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

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

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

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

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