Skuteczna obliczanie mocy 2

Question

mam wymóg obliczenia k jak najmniejszej mocy 2, który jest> = liczba całkowita, n (n jest zawsze> 0)

obecnie ja z:

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

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

to w wydajności krytycznej funkcji

Czy jest bardziej efektywny obliczeniowo sposób obliczania 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))); 

Można skorzystać z faktu, że cyfry binarne reprezentują moce dwóch (1 to 1, 10 2, 100 wynosi 4, etc). Przesunięcie 1 o wykładnik 2 daje tę samą wartość, ale jest znacznie szybsze.

Chociaż jeśli uda Ci się jakoś ominąć sufit (log2 (n)), zobaczysz znacznie większy wzrost wydajności.

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

To zabawne, aby go zbadać i zobaczyć, jak działa. Myślę, że jedyny sposób, abyś wiedział na pewno, które z rozwiązań, które widzisz, będą optymalne dla twojej sytuacji, to wykorzystać je wszystkie w opcjach tekstowych i profilować je i zobaczyć, które jest najbardziej efektywne dla twojego celu.

Będąc bez gałęzi, ten prawdopodobnie będzie dość dobry pod względem wydajności w stosunku do niektórych innych, ale powinieneś przetestować go bezpośrednio, aby mieć pewność.

Jeśli chcesz najmniejszą moc dwóch większą lub równą X, można użyć nieco inne rozwiązanie:

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

pomnożyć liczbę przez 2 aż będzie większy niż Lim.

Lewy przesunięcie jednej wartości mnoży przez 2.

Answer 5

Tak, można obliczyć biorąc to po prostu numer, o którym mowa, i używając-bitowych przesunięcia, aby określić moc 2.
prawym przesunięcia bierze wszystko bity liczby i przesuwają je w prawo, upuszczając cyfrę skrajnie prawą (najmniej znaczącą). Jest to równoważne wykonywaniu dzielenia całkowitoliczbowego przez 2. Przesunięcie w prawo wartości przenosi wszystkie bity w lewo, upuszczając bity, które przesuwają się z lewego końca, i dodając zera do prawego końca, skutecznie pomnażając wartość przez 2. Jeśli więc policzycie, ile razy trzeba przesunąć w prawo, zanim liczba osiągnie zero, obliczono całkowitą część logarytmu podstawowego 2. Następnie użyj go, aby utworzyć wynik, przesuwając wielokrotnie wartość 1 wiele razy.

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

EDIT: Ewentualnie, i nieco prostsze: nie trzeba obliczyć Hrabia

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

Answer 6

Źródło: 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; 
} 

Należy pamiętać trzeba będzie dodać:

x = x | (x >> 32); 

Dla liczb 64-bitowych.