Как определить количество правильных битовых сдвигов, необходимых для степени двойки?

Question

У меня есть функция, которая получает степень двух значений.

Мне нужно преобразовать его в диапазон перечисления (0, 1, 2, 3 и т. Д.), А затем сдвинуть его обратно в степень двух диапазонов.

 0         1
 1         2
 2         4
 3         8
 4        16
 5        32
 6        64
 7       128
 8       256
 9       512
10      1024
... and so on.

Если моя функция получает значение 1024, мне нужно преобразовать его в 10. Каков наилучший способ сделать это в C #? Должен ли я просто делить на 2 в цикле и считать итерации?

Я знаю, что могу вернуть его обратно с помощью (1 << 10). </p>

Answer 1

Просто используйте логарифм основания 2:

Math.Log(/* your number */, 2)

Например, Math.Log(1024, 2) возвращает 10.

Обновление:

Вот довольно надежная версия, которая проверяет, является ли переданное число степенью двойки:

public static int Log2(uint number)
{
  var isPowerOfTwo = number > 0 && (number & (number - 1)) == 0;
  if (!isPowerOfTwo)
  {
    throw new ArgumentException("Not a power of two", "number");
  }

  return (int)Math.Log(number, 2);
}

Чек для number, являющийся степенью двойки, взят из http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

На этой странице есть еще несколько хитростей, чтобы найти log2 целого числа: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

Answer 2

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

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

См. эту статью , если вы хотите знать, как она работает, это просто идеальный хеш.

Answer 3

Использование _BitScanForward . Это именно так.