Нахождение показателя n = 2 ** x с использованием побитовых операций [логарифм по основанию 2 из n]

Question

Есть ли простой способ извлечь показатель степени из степени 2, используя только побитовые операции?

РЕДАКТИРОВАТЬ: Хотя изначально вопрос был о побитовых операциях, поток хорошо читать, если вам интересно "Какой самый быстрый способ найти X, учитывая Y = 2 X в Python ? "**

В настоящее время я пытаюсь оптимизировать процедуру ( тест Рабина-Миллера ), которая уменьшает четное число N в формах 2**s * d. Я могу получить 2**s часть по:

two_power_s = N & -N

но я не могу найти способ извлечь просто " s " с помощью побитовой операции. Обходные пути, которые я сейчас тестирую без особого удовлетворения (все они довольно медленные):

• с использованием функции логарифма
• манипулирование двоичным представлением 2 ** с (то есть подсчет завершающих нулей)
• зацикливание на делении на 2, пока результат не станет 1

Я использую python, но ответ на этот вопрос должен быть независимым от языка, я полагаю.

Answer 1

«независимость от языка» и беспокойство по поводу производительности - в значительной степени несовместимые понятия.

Большинство современных процессоров имеют инструкцию CLZ «считать ведущие нули». В GCC вы можете добраться до него с помощью __builtin_clz (x) (который также производит разумный, если не самый быстрый, код для целей, в которых отсутствует clz). Обратите внимание, что этот CLZ не определен для нуля, поэтому вам понадобится дополнительная ветвь для определения этого случая, если это имеет значение в вашем приложении.

В CELT (http://celt -codec.org ) CLZ без ветвей, который мы используем для компиляторов без CLZ, был написан Тимоти Б. Терриберри:

int ilog(uint32 _v){
  int ret;
  int m;
  ret=!!_v;
  m=!!(_v&0xFFFF0000)<<4;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xFF00)<<3;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xF0)<<2;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xC)<<1;
  _v>>=m;
  ret|=m;
  ret+=!!(_v&0x2);
  return ret;
}

(в комментариях указано, что это оказалось быстрее, чем версия с ветвлением и версия на основе таблицы поиска)

Но если производительность настолько критична, вы, вероятно, не должны реализовывать эту часть своего кода на python.

Answer 2

Краткий ответ

Что касается питона:

• Самый быстрый метод из всех для нахождения показателя 2 ** x - это поиск в словаре, хэши которого являются степенями 2 (см. « hashlookup » в код)
• Самый быстрый побитовый метод - это метод с именем " unrolled_bitwise ".
• Оба предыдущих метода имеют четко определенные (но расширяемые) верхние пределы. Самый быстрый метод без жестко заданных верхних пределов (который масштабируется настолько, насколько Python может обрабатывать числа) - это " log_e ".

Предварительные заметки

1. Все приведенные ниже измерения скорости были получены с помощью timeit.Timer.repeat(testn, cycles), где testn было установлено на 3, а cycles было автоматически настроено сценарием для получения времен в диапазоне секунд ( примечание: в этом механизме автоматической настройки была ошибка, исправленная 18.02.2010).
2. Не все методы могут масштабироваться , поэтому я не проверял все функции на различные степени 2
3. Мне не удалось заставить некоторые из предложенных методов работать (функция возвращает неправильный результат). У меня еще не было возможности сделать пошаговую сессию отладки: я включил код (закомментированный) на тот случай, если кто-то обнаружит ошибку путем проверки (или захочет выполнить отладку самостоятельно)

Результаты

FUNC (2 5) **

hashlookup:          0.13s     100%
lookup:              0.15s     109%
stringcount:         0.29s     220%
unrolled_bitwise:    0.36s     272%
log_e:               0.60s     450%
bitcounter:          0.64s     479%
log_2:               0.69s     515%
ilog:                0.81s     609%
bitwise:             1.10s     821%
olgn:                1.42s    1065%

FUNC (2 31) **

hashlookup:          0.11s     100%
unrolled_bitwise:    0.26s     229%
log_e:               0.30s     268%
stringcount:         0.30s     270%
log_2:               0.34s     301%
ilog:                0.41s     363%
bitwise:             0.87s     778%
olgn:                1.02s     912%
bitcounter:          1.42s    1264%

FUNC (2 128) **

hashlookup:     0.01s     100%
stringcount:    0.03s     264%
log_e:          0.04s     315%
log_2:          0.04s     383%
olgn:           0.18s    1585%
bitcounter:     1.41s   12393%

FUNC (2 1024) **

log_e:          0.00s     100%
log_2:          0.01s     118%
stringcount:    0.02s     354%
olgn:           0.03s     707%
bitcounter:     1.73s   37695%

Код

import math, sys

def stringcount(v):
    """mac"""    
    return len(bin(v)) - 3

def log_2(v):
    """mac"""    
    return int(round(math.log(v, 2), 0)) # 2**101 generates 100.999999999

def log_e(v):
    """bp on mac"""    
    return int(round(math.log(v)/0.69314718055994529, 0))  # 0.69 == log(2)

def bitcounter(v):
    """John Y on mac"""
    r = 0
    while v > 1 :
        v >>= 1
        r += 1
    return r

def olgn(n) :
    """outis"""
    if n < 1:
        return -1
    low = 0
    high = sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
    while True:
        mid = (low+high)//2
        i = n >> mid
        if i == 1:
            return mid
        if i == 0:
            high = mid-1
        else:
            low = mid+1

def hashlookup(v):
    """mac on brone -- limit: v < 2**131"""
#    def prepareTable(max_log2=130) :
#        hash_table = {}
#        for p in range(1, max_log2) :
#            hash_table[2**p] = p
#        return hash_table

    global hash_table
    return hash_table[v] 

def lookup(v):
    """brone -- limit: v < 2**11"""
#    def prepareTable(max_log2=10) :
#        log2s_table=[0]*((1<<max_log2)+1)
#        for i in range(max_log2+1):
#            log2s_table[1<<i]=i
#        return tuple(log2s_table)

    global log2s_table
    return log2s_table[v]

def bitwise(v):
    """Mark Byers -- limit: v < 2**32"""
    b = (0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000)
    S = (1, 2, 4, 8, 16)
    r = 0
    for i in range(4, -1, -1) :
        if (v & b[i]) :
            v >>= S[i];
            r |= S[i];
    return r

def unrolled_bitwise(v):
    """x4u on Mark Byers -- limit:   v < 2**33"""
    r = 0;
    if v > 0xffff : 
        v >>= 16
        r = 16;
    if v > 0x00ff :
        v >>=  8
        r += 8;
    if v > 0x000f :
        v >>=  4
        r += 4;
    if v > 0x0003 : 
        v >>=  2
        r += 2;
    return r + (v >> 1)

def ilog(v):
    """Gregory Maxwell - (Original code: B. Terriberry) -- limit: v < 2**32"""
    ret = 1
    m = (not not v & 0xFFFF0000) << 4;
    v >>= m;
    ret |= m;
    m = (not not v & 0xFF00) << 3;
    v >>= m;
    ret |= m;
    m = (not not v & 0xF0) << 2;
    v >>= m;
    ret |= m;
    m = (not not v & 0xC) << 1;
    v >>= m;
    ret |= m;
    ret += (not not v & 0x2);
    return ret - 1;


# following table is equal to "return hashlookup.prepareTable()" 
hash_table = {...} # numbers have been cut out to avoid cluttering the post

# following table is equal to "return lookup.prepareTable()" - cached for speed
log2s_table = (...) # numbers have been cut out to avoid cluttering the post

Answer 3

Есть страница с множеством этих трюков и хаков. Он написан для C, но многие из них должны работать и на Python (хотя производительность, очевидно, будет другой). Вы хотите бит здесь и далее.

Вы можете попробовать это , например:

register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
  if (v & b[i])
  {
    v >>= S[i];
    r |= S[i];
  } 
}

Похоже, что он может быть легко преобразован в Python.

Answer 4

Вы можете сделать это за O (lg s) для целых чисел произвольной длины, используя binsearch.

import sys
def floorlg(n):
    if n < 1:
        return -1
    low=0
    high=sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
    while True:
        mid = (low+high)//2
        i = n >> mid
        if i == 1:
            return mid
        if i == 0:
            high = mid-1
        else:
            low = mid+1

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

Answer 5

Поздно на вечеринку, но как насчет int.bit_length(n) - 1? Вы просили прямо, и это кажется самым простым для меня. Реализация CPython выглядит достаточно производительно.

• Справочная документация
• Исходный код CPython

Answer 6

На самом деле это комментарий к тесту производительности, опубликованному Mac. Я отправляю это как ответ, чтобы иметь правильное форматирование кода и отступ

mac, не могли бы вы попробовать развернутую реализацию bitseach, предложенную Марком Байерсом? Может быть, это просто доступ к массиву, который замедляет его. Теоретически этот подход должен быть быстрее, чем другие.

Это выглядело бы примерно так, хотя я не уверен, подходит ли форматирование для python, но я думаю, вы можете видеть, что он должен делать.

def bitwise(v):
    r = 0;
    if( v > 0xffff ) : v >>= 16; r = 16;
    if( v > 0x00ff ) : v >>=  8; r += 8;
    if( v > 0x000f ) : v >>=  4; r += 4;
    if( v > 0x0003 ) : v >>=  2; r += 2;
    return r + ( v >> 1 );

Если python разделяет отсутствие в Java неисключенных целых чисел, это должно быть что-то вроде этого:

def bitwise(v):
    r = 0;
    if( v & 0xffff0000 ) : v >>>= 16; r = 16;
    if( v > 0x00ff ) : v >>=  8; r += 8;
    if( v > 0x000f ) : v >>=  4; r += 4;
    if( v > 0x0003 ) : v >>=  2; r += 2;
    return r + ( v >> 1 );

Answer 7

Кажется, диапазон известен. Давайте предположим, что он увеличивается до 1 << 20, просто чтобы сделать его более интересным: </p>

max_log2=20

Итак, составьте список, который (по сути) отображает целое число в его логарифм с основанием 2. Следующее сделает трюк:

log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
    log2s_table[1<<i]=i

(Это не делает ничего полезного для чисел, которые не имеют степеней двойки; постановка задачи предполагает, что их не нужно обрабатывать. Хотя это было бы достаточно легко исправить.)

Функция для получения логарифма очень проста и может быть легко встроена:

def table(v):
    return log2s_table[v]

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

stringcount: 0.43 s.
table: 0.16 s.

Поскольку все значения в таблице меньше 256, я подумал, будет ли использование строки вместо списка более быстрым, или, может быть, array.array байтов, но без кубиков:

string: 0.25 s.
arr: 0.21 s.

Использование dict для поиска - еще одна возможность, использующая способ проверки только степеней двух:

log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])

def map(v):
    return log2s_map[v]

Результаты для этого были не так хороши:

map: 0.20 s.

И просто для удовольствия можно также использовать метод hex для объектов с плавающей точкой, чтобы получить строку, которая включает (как ее последняя часть) показатель степени 2 числа. Это немного медленно для извлечения в целом, но если показатель степени когда-либо будет только одна цифра, это может быть сделано достаточно просто:

def floathex(v):
    return ord(float(v).hex()[-1])-48

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

Похоже, использование списка - это путь.

(Этот подход не будет масштабироваться бесконечно, из-за ограниченного объема памяти, но чтобы восполнить это, скорость выполнения не будет зависеть от max_log2 или входных значений, в любом случае, которые вы заметите при запуске Python-код. Что касается потребления памяти, если я правильно помню свои внутренние компоненты Python, таблица займет около (1<<max_log2)*4 байт, потому что все содержимое представляет собой небольшие целые числа, которые интерпретатор будет автоматически интернировать. Поэтому, когда max_log2 равно 20, это около 4 МБ.)