Какой самый быстрый способ вычислить log2 целого числа в C #?

Question

Как наиболее эффективно подсчитать количество бит, необходимое для целого числа (основание журнала 2) в C #? Например:

int bits = 1 + log2(100);

=> bits == 7

Answer 1

Незначительное улучшение ответа Гуффы ... Поскольку сумма, которую вы добавляете к результату, всегда равна степени двух, использование битовых операций может привести к небольшому улучшению в некоторых архитектурах.Кроме того, поскольку наш контекст является битовым шаблоном, он немного более удобен для использования в шестнадцатеричном формате.В этом случае полезно сдвинуть арифметику на степень 2.

int bits = 0;

if (n > 0xffff) {
  n >>= 16;
  bits = 0x10;
}

if (n > 0xff) {
  n >>= 8;
  bits |= 0x8;
}

if (n > 0xf) {
  n >>= 4;
  bits |= 0x4;
}

if (n > 0x3) {
  n >>= 2;
  bits |= 0x2;
}

if (n > 0x1) {
  bits |= 0x1;
}

Далее следует добавить проверку для n == 0, поскольку приведенное выше даст результат 0 и Log (0).не определено (независимо от базы).

В сборке ARM этот алгоритм создает очень компактный код, так как ветвь после сравнения может быть устранена с помощью условных инструкций, позволяющих избежать очистки конвейера.Например:

if (n > 0xff) {
   n >>= 8;
   bits |= 0x8;
}

становится (пусть R0 = n, R1 = биты)

CMP R0, $0xff
MOVHI R0, R0, LSR $8
ORRHI R1, R1, $0x8

Answer 2

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

int bits = 0;
while (n > 0) {
  bits++;
  n >>= 1;
}

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

int bits = 0;
while (n > 255) {
  bits += 8;
  n >>= 8;
}
while (n > 0) {
  bits++;
  n >>= 1;
}

Edit:

Наиболее эффективным методом было бы использование двоичных шагов, предложенных Flynn1179 (голосование за вдохновение :), но расширение цикла в жестко закодированные проверки. Это как минимум вдвое быстрее, чем в предыдущем методе, но также и больше кода:

int bits = 0;
if (n > 32767) {
  n >>= 16;
  bits += 16;
}
if (n > 127) {
  n >>= 8;
  bits += 8;
}
if (n > 7) {
  n >>= 4;
  bits += 4;
}
if (n > 1) {
  n >>= 2;
  bits += 2;
}
if (n > 0) {
  bits++;
}

Answer 3

Эффективность с точки зрения количества строк кода или скорости выполнения во время выполнения?

Код прост: Math.log(n, 2).

Скорость выполнения немного сложнее, но вы можете сделать это с помощью «двоичного поиска»:

int bits = 1;
for (int b = 16; b >=1; b/=2)
{
  int s = 1 << b;
  if (n >= s) { n>>=b; bits+=b; }
}

Я не уверен на 100%, что у меня есть логика, но, надеюсь, идея ясна. В .NET VM могут быть некоторые издержки, но в принципе это должно быть быстрее.

Значение 16 в инициализаторе цикла for основано на половине количества бит, необходимых для int. Если вы работаете с длинными, начните с 32 и т. Д.