Битовое чередование в C: как конвертировать из 2 ^ N в N?

Question

Что такое хорошая подпрограмма преобразования битов для преобразования числа в диапазоне [2 ^ N, 2 ^ (N-1) -1] в N?

Некоторые примеры:

• f (1) -> 0
• f ([2-3]) -> 1
• f ([4-7]) -> 2
• f ([8-15]) -> 3

Вот одна из реализаций:

uint f(uint num)
{
    for (uint shifts = 0; num; shifts++) 
        num >>= 1;
    return (shifts - 1);
}

Answer 1

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

Другие подходы см. В http://www -graphics.stanford.edu / ~ seander / bithacks.html # IntegerLogObvious и последующих разделах.

Answer 2

Как наиболее общий подход, бинарный поиск может помочь.Для значений 0..31 требуется всего 5 этапов.

y = 0;
if(x >= 0x10000<<y) y += 0x10;
if(x >= 0x100<<y) y += 0x08;
if(x >= 0x10<<y) y += 0x04;
if(x >= 0x4<<y) y += 0x02;
if(x >= 0x2<<y) y += 0x01;

Answer 3

Посмотрите на хаки для вычисления логарифма по основанию 2 (или начального нуля, они одинаковые) на этой странице: http://www -graphics.stanford.edu / ~ seander / bithacks.html

Вы также можете найти полезную функцию __builtin_clz (или _BitScanReverse для VS) для x86.