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

Ответ 1

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

Код easy: 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. Если вы работаете с longs, запустите его на 32 и т.д.

Ответ 2

Незначительное улучшение ответа Guffa... Поскольку сумма, которую вы добавляете к результату, всегда имеет силу двух операций с использованием бит, может привести к небольшому улучшению некоторых архитектур. Кроме того, поскольку наш контекст - это битовые шаблоны, он немного читабельнее, чтобы использовать шестнадцатеричный. В этом случае полезно сдвинуть арифметику на степень 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) - undefined (независимо от базы).

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

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

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

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

Ответ 3

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

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

Ответ 4

Вот самый быстрый способ вычисления log2 целого числа в С#...

    [StructLayout(LayoutKind.Explicit)]
    private struct ConverterStruct
    {
        [FieldOffset(0)] public int asInt;
        [FieldOffset(0)] public float asFloat;
    }

    public static int Log2_SunsetQuest3(uint val)
    {
        ConverterStruct a;  a.asInt = 0; a.asFloat = val;
        return ((a.asInt >> 23 )+ 1) & 0x1F;
    }

Примечание:

• Идея использования показателя в поплавке была вдохновлена SPWorley 3/22/2009.
• Используйте с осторожностью в производственном коде, так как это, вероятно, приведет к сбою в архитектурах, которые не имеют порядка байтов.

Вот некоторые тесты: (код здесь: https://github.com/SunsetQuest/Fast-Integer-Log2)

Function                 Time1  Time2    Errors  Full-32-Bit Zero_Support
Log2_SunsetQuest3:        18     18       0        (Y)        (N)
Log2_SunsetQuest4:        18     18       0        (Y)        (N)
Log2_SPWorley:            18     18       0        (Y)        (N)
MostSigBit_spender:       20     19       0        (Y)        (Y)
Log2_HarrySvensson:       26     29       0        (Y)        (N)
Log2_WiegleyJ:            27     23       0        (Y)        (N)
Log2_DanielSig:           28     24    3125        (N)        (N)
FloorLog2_Matthew_Watson: 29     25       0        (Y)        (Y)
Log2_SunsetQuest1:        31     28       0        (Y)        (Y)
HighestBitUnrolled_Kaz:   33     33    3125        (Y)        (Y)
Log2_Flynn1179:           58     52       0        (Y)        (N)
GetMsb_user3177100:       58     53       0        (Y)        (N)
Log2floor_greggo:         89    101       0        (Y)        (Y)
FloorLog2_SN17:          102     43       0        (Y)        (N)
Log2_SunsetQuest2:       118    140       0        (Y)        (Y)
Log2_Papayaved:          125     60       0        (Y)        (N)
Msb_Protagonist:         136    118       0        (Y)        (N)
Log2_SunsetQuest0:       206    202       0        (Y)        (Y)
BitScanReverse2:         228    240    3125        (N)        (Y)
UsingStrings_Rob:       2346   1494       0        (Y)        (N)

Zero_Support = Supports Neg Return on Zero
Full-32-Bit  = Supports full 32-bit (some just support 31 bits)
Time1 = benchmark for sizes up to 32-bit (same number tried for each size)
Time2 = benchmark for sizes up to 16-bit (for measuring perf with small numbers)

Benchmark notes: AMD Ryzen CPU, Release mode, no-debugger attached, .net core 2.1

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