Potenza precedente di 2

Question

Ci sono molte informazioni su come trovare la potenza successiva di 2 di un dato valore (vedi i riferimenti) ma non ne trovo nessuna per ottenere la potenza precedente di due.

L'unico modo che ho trovato finora è quello di mantenere un tavolo con tutta la potenza di due fino a 2^64 e fare una semplice ricerca.

• Acius' Snippets
• gamedev
• Bit Twiddling Hacks
• Stack Overflow

Answer 1

Questa è la mia soluzione corrente per trovare il potere precedente e successivo di due di qualsiasi numero intero positivo n e anche una piccola funzione per determinare se un numero è potenza di due.

Questa implementazione è per Ruby.

class Integer 

    def power_of_two? 
    (self & (self - 1) == 0) 
    end 

    def next_power_of_two 
    return 1 if self <= 0 
    val = self 
    val = val - 1 
    val = (val >> 1) | val 
    val = (val >> 2) | val 
    val = (val >> 4) | val 
    val = (val >> 8) | val 
    val = (val >> 16) | val 
    val = (val >> 32) | val if self.class == Bignum 
    val = val + 1 
    end 

    def prev_power_of_two 
    return 1 if self <= 0 
    val = self 
    val = val - 1 
    val = (val >> 1) | val 
    val = (val >> 2) | val 
    val = (val >> 4) | val 
    val = (val >> 8) | val 
    val = (val >> 16) | val 
    val = (val >> 32) | val if self.class == Bignum 
    val = val - (val >> 1) 
    end 
end 

uso Esempio:

10.power_of_two? => false 
16.power_of_two? => true 
10.next_power_of_two => 16 
10.prev_power_of_two => 8 

Per la potenza di due precedenti, trovando il successivo e dividendo per due è leggermente più lento del metodo di cui sopra.

Non sono sicuro di come funzioni con Bignums.

Answer 2

Probabilmente l'approccio più semplice (per i numeri positivi):

// find next (must be greater) power, and go one back 
p = 1; while (p <= n) p <<= 1; p >>= 1; 

Puoi mak e variazioni in molti modi se vuoi ottimizzare.

Answer 3

Da Hacker's Delight, una bella soluzione branchless:

uint32_t flp2 (uint32_t x) 
{ 
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >> 16); 
    return x - (x >> 1); 
} 

Questo in genere dura 12 istruzioni. Puoi farlo in meno se la tua CPU ha un'istruzione "count leading zeroes".

Answer 4

Quando lavori in base 2, puoi passare da una potenza di due a quella successiva semplicemente aggiungendo o rimuovendo una cifra dalla destra.

Ad esempio, la potenza precedente due del numero 8 è il numero 4. binario:

01000 -> 0100 (togliamo lo zero finale per ottenere il numero 4)

Quindi l'algoritmo per risolvere il calcolo della potenza di due precedente è:

previousPower: = numero SHR 1

previousPower = numero >> 1

(o qualsiasi altra sintassi)

Answer 5

Se si ottiene la potenza successiva di 2, la potenza inferiore di 2 è quella successiva o superiore o metà. Dipende da ciò che consideri essere il "prossimo più alto" per qualsiasi potere di 2 (e ciò che consideri essere il potere minore di 2).

Answer 6

Questo può essere fatto in una riga.

int nextLowerPowerOf2 = i <= 0 
         ? 0 
         : ((i & (~i + 1)) == i) 
          ? i >> 1 
          : (1 << (int)Math.Log(i, 2)); 

risultato

i power_of_2 
-2 0 
-1 0 
0 0 
1 0 
2 1 
3 2 
4 2 
5 4 
6 4 
7 4 
8 4 
9 8 

Ecco una versione più leggibile in C#, con la clausola di guardia < = 0 distribuito ai metodi di utilità.

int nextLowerPowerOf2 = IsPowerOfTwo(i) 
    ? i >> 1 // shift it right 
    : GetPowerOfTwoLessThanOrEqualTo(i); 

public static int GetPowerOfTwoLessThanOrEqualTo(int x) 
{ 
    return (x <= 0 ? 0 : (1 << (int)Math.Log(x, 2))); 
} 

public static bool IsPowerOfTwo(int x) 
{ 
    return (((x & (~x + 1)) == x) && (x > 0)); 
} 

Answer 7

uint32_t previous_power_of_two(uint32_t x) { 
    if (x == 0) { 
     return 0; 
    } 
    // x--; Uncomment this, if you want a strictly less than 'x' result. 
    x |= (x >> 1); 
    x |= (x >> 2); 
    x |= (x >> 4); 
    x |= (x >> 8); 
    x |= (x >> 16); 
    return x - (x >> 1); 
} 

Grazie per le risposte. Cercherò di riassumerli e spiegare un po 'più chiaramente. Ciò che questo algoritmo fa è cambiare in "tutti" tutti i bit dopo il primo bit "uno", perché questi sono gli unici bit che possono rendere la nostra 'x' più grande della sua precedente potenza di due. Dopo essersi assicurati che siano "quelli", li rimuove semplicemente, lasciando intatto il primo bit "uno". Quel singolo bit al suo posto è il nostro precedente potere di due.

Answer 8

Prova questo: ~((x + ~x)>>1) È breve e davvero facile.

Answer 9

Che dire

if (tt = v >> 16) 
{ 
    r = (t = tt >> 8) ? 0x1000000 * Table256[t] : 0x10000 * Table256[tt]; 
} 
else 
{ 
    r = (t = v >> 8) ? 0x100 * Table256[t] : Table256[v]; 
} 

E 'solo metodo modificato da http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup. Ciò richiede come 7 operazioni e potrebbe essere più veloce sostituire le moltiplicazioni con lo spostamento.

Answer 10

Ecco un uno di linea per i posteri (ruby):

2**Math.log(input, 2).floor(0) 

Answer 11

sottostante Codice troveranno la forza precedente di 2:

int n = 100; 
    n /= 2;//commenting this will gives the next power of 2 
    n |= n>>1; 
    n |= n>>2; 
    n |= n>>4; 
    n |= n>>16; 

System.out.println(n+1);