2012-10-01 35 views
19

Dato un numero intero decimale (ad esempio 65), come si può invertire i bit sottostanti in Python? vale a dire. la seguente operazione:Bit di inversione del numero intero Python

65 → 01000001 → 10000010 → 130 

Sembra che questo compito può essere suddiviso in tre fasi:

  1. convertire l'intero decimale di rappresentazione binaria
  2. inverso i bit
  3. riconvertire decimale

I passaggi 2 e 3 sembrano piuttosto semplici (vedere this e this SO domanda relativa al passaggio n. 2), ma sono bloccato al passaggio n. Il problema con il passaggio n. 1 è il recupero della rappresentazione decimale completa con zeri di riempimento (ad esempio 65 = 01000001, non 1000001).

Ho cercato in giro, ma non riesco a trovare nulla.

+1

Per il primo passaggio, è possibile utilizzare 'str (bin (65)) [2:]. Zfill (8)'. Per pigro/stanco di guardare oltre in questo ora. Ma probabilmente dovresti fare come dice Larsmans. – BrtH

risposta

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

È possibile specificare qualsiasi lunghezza di riempimento al posto di 8. Se si desidera ottenere veramente fantasia,

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

consente di specificare la larghezza a livello di codice.

+1

Elegante e conciso. Ho dovuto cambiare la stringa di formato in ''{: 08b}'' per funzionare come specificato. –

+0

Ah, sì, voleva che il riempimento si azzerasse. Correggerò – nneonneo

+0

Se faccio 'int ('{: b}'. Format (65) [:: - 1], 2)', ho appena ottenuto '65' come output. L'uso di '{: 08b}' invece di '{: b}' dà comunque il risultato corretto, quindi +1 per una soluzione elegante. – BrtH

4

Non c'è bisogno, e non c'è modo, di "convertire un intero decimale in rappresentazione binaria". Tutti gli interi Python sono rappresentati come binari; sono appena convertiti in decimali quando li stampi per comodità.

Se si desidera seguire this solution per il problema di inversione, è necessario trovare solo numbits appropriato. È possibile specificarlo manualmente o calcolare il numero di bit necessari per rappresentare un numero intero n con n.bit_length().

Tuttavia, per 65, ciò darebbe 7, in quanto non vi è alcun motivo per cui 65 dovrebbe richiedere altri bit. (Si potrebbe desiderare di arrotondare fino al più vicino multiplo di 8 ...)

+0

Non proprio corretto, dato che puoi ottenere una stringa che rappresenta i bit ('bin (n)', o ''{: b}'. Format (n)'). Inoltre, puoi usare '.bit_length()' per trovare il numero esatto di bit necessari per rappresentare un numero. – nneonneo

+0

@nneonneo: stavo partendo dal presupposto che l'OP volesse lavorare sull'intero stesso piuttosto che sulla rappresentazione di una stringa, dati i collegamenti. Ma grazie per il metodo 'bit_length', non lo sapevo. –

4

Se siete dopo più velocità, è possibile utilizzare la tecnica descritta in 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 
2

È possibile verificare il bit-esimo di un numero utilizzando un cambiamento e la maschera. Ad esempio, il bit 6 di 65 è (65 >> 6) & 1. È possibile impostare un bit in modo simile spostando 1 a sinistra il numero giusto di volte. Queste intuizioni ti danno un codice come questo (che inverte x in un campo di bit '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)) 
3
def reverse_bit(num): 
    result = 0 
    while num: 
     result = (result << 1) + (num & 1) 
     num >>= 1 
    return result 

Noi in realtà non hanno bisogno di convertire il numero intero in binario, dal momento che gli interi sono in realtà binaria in Python.

L'idea di inversione è come eseguire l'inversione nello spazio degli interi.

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 

Per ogni ciclo, il numero originale sta perdendo il bit più a destra (in binario). Otteniamo il bit più a destra e moltiplichiamo 2 (<<1) nel ciclo successivo quando viene aggiunto il nuovo bit.

Problemi correlati