Base-2 (двоичное) представление с использованием Python

Question

Опираясь на Как вы выражаете двоичные литералы в Python , я думал о разумных, интуитивно понятных способах сделать это Программирование 101 каштана отображения целых чисел в форме base-2. Это лучшее из того, что я придумал, но я бы хотел заменить его на лучший алгоритм или, по крайней мере, такой, который должен иметь высокую скорость работы.

def num_bin(N, places=8):
    def bit_at_p(N, p):
        ''' find the bit at place p for number n '''
        two_p = 1 << p   # 2 ^ p, using bitshift, will have exactly one
                         # bit set, at place p
        x = N & two_p    # binary composition, will be one where *both* numbers
                         # have a 1 at that bit.  this can only happen 
                         # at position p.  will yield  two_p if  N has a 1 at 
                         # bit p
        return int(x > 0)

    bits =  ( bit_at_p(N,x) for x in xrange(places))
    return "".join( (str(x) for x in bits) )

    # or, more consisely 
    # return "".join([str(int((N & 1 << x)>0)) for x in xrange(places)])

Answer 1

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

def _bin(x, width):
    return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1))

_bin (x, 8) теперь будет давать заполненное нулями представление младших 8 битов x. Это может быть использовано для построения справочной таблицы, позволяющей вашему конвертеру обрабатывать 8 бит за раз (или больше, если вы хотите посвятить ему память).

_conv_table = [_bin(x,8) for x in range(256)]

Затем вы можете использовать это в своей реальной функции, удаляя начальные нули при возврате. Я также добавил обработку для чисел со знаком, так как без него вы получите бесконечный цикл (концептуально, что у отрицательных целых чисел есть бесконечное число битов заданного знака).

def bin(x):
    if x == 0: 
        return '0' #Special case: Don't strip leading zero if no other digits
    elif x < 0:
        sign='-'
        x*=-1
    else:
        sign = ''
    l=[]
    while x:
        l.append(_conv_table[x & 0xff])
        x >>= 8
    return sign + ''.join(reversed(l)).lstrip("0")

[Редактировать] Изменен код для обработки целых чисел со знаком.
[Edit2] Вот некоторые временные диаграммы различных решений. bin - функция выше, constantin_bin от ответ Константина , а num_bin - оригинальная версия. Из любопытства я также попробовал 16-битный вариант таблицы поиска выше (bin16 ниже) и попробовал встроенную функцию Python3 bin (). Все тайминги были для 100000 прогонов с использованием битовой комбинации 01010101.

Num Bits:              8       16       32       64      128      256
---------------------------------------------------------------------
bin                0.544    0.586    0.744    1.942    1.854    3.357 
bin16              0.542    0.494    0.592    0.773    1.150    1.886
constantin_bin     2.238    3.803    7.794   17.869   34.636   94.799
num_bin            3.712    5.693   12.086   32.566   67.523  128.565
Python3's bin      0.079    0.045    0.062    0.069    0.212    0.201 

Как вы можете видеть, когда обработка длинных значений с использованием больших кусков действительно окупается, но ничто не сравнится с низкоуровневым кодом C встроенного в python3 (который кажется странно быстрее при 256 битах, чем 128!) Использование 16-битной таблицы поиска улучшает ситуацию, но, вероятно, оно того не стоит, если оно вам действительно не нужно, поскольку оно использует большой кусок памяти и может вводить небольшую, но незначительную задержку при запуске для предварительного вычисления таблицы.

Answer 2

Не кричащий-быстрый, но прямой:

>>> def bin(x):
...     sign = '-' if x < 0 else ''
...     x = abs(x)
...     bits = []
...     while x:
...             x, rmost = divmod(x, 2)
...             bits.append(rmost)
...     return sign + ''.join(str(b) for b in reversed(bits or [0]))

Это также быстрее, чем num_bin:

>>> import timeit
>>> t_bin = timeit.Timer('bin(0xf0)', 'from __main__ import bin')
>>> print t_bin.timeit(number=100000)
4.19453350997
>>> t_num_bin = timeit.Timer('num_bin(0xf0)', 'from __main__ import num_bin')
>>> print t_num_bin.timeit(number=100000)
4.70694716882

Более того, он действительно работает правильно (для моего определения «правильности»:)):

>>> bin(1)
'1'
>>> num_bin(1)
'10000000'