Đảo ngược các bit của số nguyên Python

Question

Cho số nguyên thập phân (ví dụ 65), làm cách nào để đảo ngược các bit cơ bản trong Python? I E. các hoạt động sau:

65 → 01000001 → 10000010 → 130 

Dường như nhiệm vụ này có thể được chia thành ba bước sau:

1. Chuyển đổi số nguyên thập phân để biểu diễn nhị phân
2. Đảo ngược bit
3. Chuyển đổi trở lại thập phân

Các bướC# 2 và 3 có vẻ khá đơn giản (xem this và this SO câu hỏi liên quan đến bướC# 2), nhưng tôi bị mắc kẹt trên bướC# 1. Vấn đề với bướC# 1 là lấy biểu diễn thập phân đầy đủ bằng cách điền số không (ví dụ: 65 = 01000001, không phải 1000001).

Tôi đã tìm kiếm xung quanh, nhưng tôi dường như không thể tìm thấy bất kỳ thứ gì.

Answer 1

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

Bạn có thể chỉ định bất kỳ chiều dài điền ở vị trí của 8. Nếu bạn muốn nhận được sự ưa thích,

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

cho phép bạn chỉ định chiều rộng theo lập trình.

Answer 2

Không cần, và không có cách nào, để "chuyển đổi một số nguyên thập phân thành biểu diễn nhị phân". Tất cả các số nguyên Python được biểu diễn dưới dạng nhị phân; chúng chỉ được chuyển đổi sang thập phân khi bạn in chúng để thuận tiện.

Nếu bạn muốn theo dõi this solution đối với vấn đề đảo ngược, bạn chỉ cần tìm thích hợp numbits. Bạn có thể chỉ định điều này bằng tay hoặc tính số bit cần thiết để biểu thị một số nguyên n với n.bit_length().

Tuy nhiên, đối với 65, điều đó sẽ cung cấp cho bạn 7, vì không có lý do gì khiến 65 yêu cầu thêm bit. (Bạn có thể muốn làm tròn đến bội số gần nhất của 8 ...)

Answer 3

Nếu bạn đang theo đuổi tốc độ nhanh hơn, bạn có thể sử dụng các kỹ thuật được mô tả trong 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 

Answer 4

Bạn có thể kiểm tra các bit i'th của một số bằng cách sử dụng một sự thay đổi và mặt nạ. Ví dụ: bit 6 của 65 là (65 >> 6) & 1. Bạn có thể đặt bit theo cách tương tự bằng cách dịch chuyển 1 sang trái số lần phải. Những thông tin chi tiết này cung cấp cho bạn mã như thế này (ngược lại x trong một trường 'bit').

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)) 

Answer 5

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

Chúng tôi không thực sự cần phải chuyển đổi các số nguyên vào nhị phân, vì số nguyên thực sự nhị phân trong Python.

Ý tưởng đảo ngược giống như thực hiện đảo ngược các số nguyên trong không gian.

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 

Đối với mỗi vòng lặp, số ban đầu sẽ giảm bit ngoài cùng bên phải (theo hệ nhị phân). Chúng tôi nhận được bit phải nhất đó và nhân 2 (<<1) trong vòng lặp tiếp theo khi bit mới được thêm vào.