Lunghezza in bit di un numero intero positivo in Python

Question

1 = 0b1 -> 1 
5 = 0b101 -> 3 
10 = 0b1010 -> 4 
100 = 0b1100100 -> 7 
1000 = 0b1111101000 -> 10 
… 

Come posso ottenere la lunghezza di bit di un intero, cioè il numero di bit necessari per rappresentare un intero positivo in Python?

Answer 1

def bitcounter(n): 
    return math.floor(math.log(n,2)) + 1 

EDIT fissato in modo che funzioni con 1

Answer 2

>>> len(bin(1000))-2 
10 
>>> len(bin(100))-2 
7 
>>> len(bin(10))-2 
4 

Nota: non funzionerà per i numeri negativi, può essere necessario sottrarre 3 invece di 2

Answer 3

In pitone 2.7+ c'è un metodo int.bit_length():

>>> a = 100 
>>> a.bit_length() 
7 

Answer 4

Se la versione di Python lo ha (≥2.7 per Python 2, ≥3.1 per Python 3), utilizzare il metodo bit_length dalla libreria standard.

Altrimenti, len(bin(n))-2as suggested by YOU è veloce (perché implementato in Python). Si noti che questo restituisce 1 per 0.

Altrimenti, un metodo semplice è ripetutamente dividere per 2 (che è un po 'spostamento lineare), e contare il tempo necessario per raggiungere 0.

def bit_length(n): # return the bit size of a non-negative integer 
    bits = 0 
    while n >> bits: bits += 1 
    return bits 

Si è significativamente più veloce (almeno per grandi numeri - un rapido benchmark dice più di 10 volte più veloce per 1000 cifre) per spostarsi di parole intere alla volta, quindi tornare indietro e lavorare sui bit dell'ultima parola.

def bit_length(n): # return the bit size of a non-negative integer 
    if n == 0: return 0 
    bits = -32 
    m = 0 
    while n: 
     m = n 
     n >>= 32; bits += 32 
    while m: m >>= 1; bits += 1 
    return bits 

Nel mio punto di riferimento rapido, len(bin(n)) venuto fuori significativamente più veloce anche la versione pezzo parola di dimensioni. Sebbene bin(n) costruisca una stringa che viene scartata immediatamente, viene visualizzata in primo piano perché ha un ciclo interno che viene compilato per codice macchina. (math.log è ancora più veloce, ma non è importante dal momento che è sbagliato.)

Answer 5

Questa soluzione sfrutta lo .bit_length() se disponibile e torna a len(hex(a)) per le versioni precedenti di Python. Ha il vantaggio rispetto a bin che crea una stringa temporanea più piccola, quindi utilizza meno memoria.

Si prega di notare che restituisce 1 per 0, ma è facile da cambiare.

_HEX_BIT_COUNT_MAP = { 
    '0': 0, '1': 1, '2': 2, '3': 2, '4': 3, '5': 3, '6': 3, '7': 3} 

def bit_count(a): 
    """Returns the number of bits needed to represent abs(a). Returns 1 for 0.""" 
    if not isinstance(a, (int, long)): 
    raise TypeError 
    if not a: 
    return 1 
    # Example: hex(-0xabc) == '-0xabc'. 'L' is appended for longs. 
    s = hex(a) 
    d = len(s) 
    if s[-1] == 'L': 
    d -= 1 
    if s[0] == '-': 
    d -= 4 
    c = s[3] 
    else: 
    d -= 3 
    c = s[2] 
    return _HEX_BIT_COUNT_MAP.get(c, 4) + (d << 2) 


# Use int.bit_length and long.bit_length introduced in Python 2.7 and 3.x. 
if getattr(0, 'bit_length', None): 
    __doc = bit_count.__doc__ 
    def bit_count(a): 
    return a.bit_length() or 1 
    bit_count.__doc__ = __doc 

assert bit_count(0) == 1 
assert bit_count(1) == 1 
assert bit_count(2) == 2 
assert bit_count(3) == 2 
assert bit_count(63) == 6 
assert bit_count(64) == 7 
assert bit_count(75) == 7 
assert bit_count(2047) == 11 
assert bit_count(2048) == 12 
assert bit_count(-4007) == 12 
assert bit_count(4095) == 12 
assert bit_count(4096) == 13 
assert bit_count(1 << 1203) == 1204 
assert bit_count(-(1 << 1203)) == 1204 
assert bit_count(1 << 1204) == 1205 
assert bit_count(1 << 1205) == 1206 
assert bit_count(1 << 1206) == 1207 

Answer 6

Ecco un altro modo:

def number_of_bits(n): 
    return len('{:b}'.format(n)) 

Non è così efficiente suppongo, ma non si presenta in nessuna delle risposte precedenti ...