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

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

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

static public final int msb(int n) {
    n |= n >>> 1;  
    n |= n >>> 2; 
    n |= n >>> 4; 
    n |= n >>> 8; 
    n |= n >>> 16; 
    n >>>= 1;
    n += 1; 
    return n;
}

static public final int msb_index(int n) {

    final int[] multiply_de_bruijn_bit_position = {
        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
    };
    return multiply_de_bruijn_bit_position[(msb(n) * 0x077CB531) >>> 27];
}

Вот дополнительная информация от: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

// Count the consecutive zero bits (trailing) on the right with multiply and lookup

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[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 = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

// Converting bit vectors to indices of set bits is an example use for this. 
// It requires one more operation than the earlier one involving modulus 
// division, but the multiply may be faster. The expression (v & -v) extracts 
// the least significant 1 bit from v. The constant 0x077CB531UL is a de Bruijn 
// sequence, which produces a unique pattern of bits into the high 5 bits for 
// each possible bit position that it is multiplied against. When there are no 
// bits set, it returns 0. More information can be found by reading the paper 
// Using de Bruijn Sequences to Index 1 in a Computer Word by 
// Charles E. Leiserson, Harald Prokof, and Keith H. Randall. 

и как последнее: http://supertech.csail.mit.edu/papers/debruijn.pdf

Answer 2

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

Answer 3

Другой ответ при условии IEEE float:

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

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

Answer 4

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

Answer 5

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

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