efficiente calcolo di una potenza di 2

Question

Ho un requisito per calcolare k come la più piccola potenza di 2 che è> = un valore intero, n (n è sempre> 0)

attualmente sto usando:

#define log2(x) log(x)/log(2) 
#define round(x) (int)(x+0.5) 

k = round(pow(2,(ceil(log2(n))))); 

questo è in una performance funzione critica

c'è un modo più efficiente computazionalmente di calcolo k?

Answer 1

int calculate_least_covering_power_of_two(int x) 
{ 
    int k = 1; 
    while(k < x) k = k << 1; 
    return k; 
} 

Answer 2

k = 1 << (int)(ceil(log2(n))); 

Si può approfittare del fatto che cifre binarie rappresentano potenze di due (1 è 1, 10 è 2, 100 è 4, ecc). Spostando 1 a sinistra dall'esponente di 2 si ottiene lo stesso valore, ma è molto più veloce.

Anche se è possibile in qualche modo evitare il ceil (log2 (n)), si noterà un aumento delle prestazioni molto più grande.

Answer 3

/* returns greatest power of 2 less than or equal to x, branch-free */ 
/* Source: Hacker's Delight, First Edition. */ 
int 
flp2(int 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); 
} 

È divertente studiarlo e vedere come funziona. Penso che l'unico modo per farti sapere con certezza quale delle soluzioni che vedrai sarà ottimale per la tua situazione è di usarli tutti in un dispositivo di testo e di tracciarlo e vedere quale è il più efficiente per il tuo scopo.

Essendo privo di ramificazioni, è probabile che questo rappresenti prestazioni relativamente buone rispetto ad altri, ma è necessario verificarlo direttamente per essere sicuri.

Se si desidera che il minimo potenza di due superiore o uguale a X, è possibile utilizzare una soluzione leggermente diversa:

unsigned 
clp2(unsigned x) 
{ 
    x = x -1; 
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >> 16); 
    return x + 1; 
} 

Answer 4

lim = 123; 
n = 1; 
while((n = n << 1) <= lim); 

Moltiplica il tuo numero da 2 fino a quando è più grande di lim.

spostamento a sinistra di un valore si moltiplica per 2.

Answer 5

Sì, È possibile calcolare questo semplicemente prendendo il numero in questione, e l'utilizzo di bit-turni per determinare la potenza di 2.
destro-shifting prende tutto i bit del numero e li sposta a destra, lasciando cadere la cifra all'estrema destra (meno significativa). È equivalente all'effettuazione di una divisione intera per 2. Spostando a sinistra un valore si spostano tutti i bit a sinistra, lasciando cadere i bit che si spostano dall'estremità sinistra e aggiungendo gli zeri all'estremità destra, moltiplicando effettivamente il valore di 2. Quindi, se contate quante volte avete bisogno di spostare a destra prima che il numero raggiunga lo zero, avete calcolato la parte intera del logaritmo di base 2. Quindi utilizzalo per creare il risultato spostando a sinistra il valore 1 più volte.

int CalculateK(int val) 
    { 
     int cnt = 0; 
     while(val > 0) 
     { 
      cnt++; 
      val = val >> 1; 
     } 
     return 1 << cnt; 
    } 

EDIT: In alternativa, e un po 'più semplice: non c'è bisogno di calcolare il numero di

int CalculateK(int val) 
    { 
     int res = 1; 
     while(res <= val) res <<= 1; 
     return res ; 
    } 

Answer 6

Fonte: hackersdelight.org

/* altered to: power of 2 which is greater than an integer value */ 

unsigned clp2(unsigned x) { 
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >>16); 
    return x + 1; 
} 

Tenete a mente è necessario aggiungere:

x = x | (x >> 32); 

Per i numeri a 64 bit.