Тема: Log(n, base:2) для цілих [ushort]
Маю інтриґуючу задачу: Написати функцію GetLog2, яка приймає число типу System.UInt16, в якому { поставлено 1 біт, решта нулі }, і вертає зміщеня відносно 1, тобто вертає степінь двійки. Приклади даних:
Input : Output
0b_00000000_00000001 : 0b_0000
0b_00000000_00000010 : 0b_0001
0b_00000000_00000100 : 0b_0010
0b_00000000_00001000 : 0b_0011
0b_00000000_00010000 : 0b_0100
0b_00000000_00100000 : 0b_0101
0b_00000000_01000000 : 0b_0110
0b_00000000_10000000 : 0b_0111
0b_00000001_00000000 : 0b_1000
0b_00000010_00000000 : 0b_1001
0b_00000100_00000000 : 0b_1010
0b_00001000_00000000 : 0b_1011
0b_00010000_00000000 : 0b_1100
0b_00100000_00000000 : 0b_1101
0b_01000000_00000000 : 0b_1110
0b_10000000_00000000 : 0b_1111Що фунція верне для всіх інших значень - не важливо. Ми будемо ґарантувати шо на вхід буде подано зміщену одиницю (не 0).
І заборонено користувати тип double, тобто кликати System.Math.Log(d) не можна.
Є така заготовка, якою можна перевірити чи реалізація добра:
public static int GetLog2(ushort v) {
// тут має бути реалізація
return _something_;
}
public static void PrintLog2Table() {
const int n = 16;
for(int i = 0; i < n; ++i) {
int pow = 1 << i;
int log = GetLog2((ushort)pow);
Console.WriteLine(
"i: {0,2}, Pow2: {1,10}, Log2: {2,2} {3} {0,2};"
, i, pow, log, log == i ? "==" : "!="
);
if(log != i) throw new Exception();
}
}Покишо я зробив код, який легко маштабувати для інших типів:
public static int GetLog2(ushort v) {
return (int)(
((v & 0xFF00u) / v) << 3 |
((v & 0xF0F0u) / v) << 2 |
((v & 0xCCCCu) / v) << 1 |
((v & 0xAAAAu) / v)
);
}Але в даному випадку треба максимально тиснути на швидкість виконаня і дешеві оператори.
Ходить легенда, шо ці 4 діленя (/) можна замінити на 1 множеня (*). Як?: ще шукаю.
