Реверсивные биты целого числа Python

Учитывая десятичное целое число (например, 65), как можно отбросить базовые биты в Python? то есть. выполните следующую операцию:

65 → 01000001 → 10000010 → 130

Кажется, что эту задачу можно разбить на три этапа:

Преобразование десятичного целого в двоичное представление
Отменить бит
Преобразование обратно в десятичное

Шаги № 2 и 3 кажутся довольно простыми (см. this и this SO вопрос, связанный с шагом # 2), но я застрял на шаге №1. Проблема с шагом # 1 - получение полного десятичного представления с заполняющими нулями (т.е. 65 = 01000001, а не 1000001).

Я искал вокруг, но я не могу найти ничего.

Ответ 1

int('{:08b}'.format(n)[::-1], 2)

Вы можете указать любую длину заполнения вместо 8. Если вы хотите получить действительно фантазию,

b = '{:0{width}b}'.format(n, width=width)
int(b[::-1], 2)

позволяет указать ширину программно.

Ответ 2

Нет необходимости и никоим образом не "преобразовать десятичное целое в двоичное представление". Все целые числа Python представлены как двоичные; они просто преобразуются в десятичные числа, когда вы печатаете их для удобства.

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

Однако, для 65, это даст вам 7, так как нет никакой причины, по которой 65 должны требовать больше бит. (Возможно, вы захотите округлить до ближайшего кратного 8...)

Ответ 3

Если вы используете более высокую скорость, вы можете использовать технику, описанную в http://leetcode.com/2011/08/reverse-bits.html

def reverse_mask(x):
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1)
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2)
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4)
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8)
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16)
    return x

Ответ 4

def reverse_bit(num):
    result = 0
    while num:
        result = (result << 1) + (num & 1)
        num >>= 1
    return result

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

Реверсивная идея похожа на обратное преобразование целых чисел в пространстве.

def reverse_int(x):
    result = 0
    pos_x = abs(x)
    while pos_x:
        result = result * 10 + pos_x % 10
        pos_x /= 10
    return result if x >= 0 else (-1) * result

Для каждого цикла исходный номер отбрасывает самый правый бит (в двоичном формате). Мы получаем этот самый правый бит и умножаем 2 (<<1) в следующем цикле при добавлении нового бита.

Ответ 5

Вы можете проверить i-й бит числа, используя сдвиг и маску. Например, бит 6 из 65 равен (65 >> 6) & 1. Вы можете установить бит аналогичным образом, сдвинув 1 налево в нужное количество раз. Эти идеи дают вам такой код (который меняет x в поле "n" ).

def reverse(x, n):
    result = 0
    for i in xrange(n):
        if (x >> i) & 1: result |= 1 << (n - 1 - i)
    return result

print bin(reverse(65, 8))