Zaokrąglenie do następnej potęgi 2


189

Chcę napisać funkcję, która zwraca najbliższą następną potęgę liczby 2. Na przykład, jeśli mój sygnał wejściowy to 789, wynik powinien wynosić 1024. Czy jest jakiś sposób na osiągnięcie tego bez użycia żadnych pętli, a jedynie z wykorzystaniem operatorów bitowych?



4
Dla wyjaśnienia, czy potrzebujesz najbliższej potęgi 2 (tj. 65 da 64, ale 100 da 128), czy najbliższej powyżej (tj. 65 da 128, a więc 100)?
Kim Reece

1
Jest wiele pytań pasujących do tego. Na przykład: stackoverflow.com/questions/364985/...
Yann Droneaud

1
możliwy duplikat Biorąc
Nathan

7
@Nathan Twój link jest 8 miesięcy później niż to pytanie.
Joseph Quinsey

Odpowiedzi:


148

Sprawdź Bit Twiddling Hacks . Musisz uzyskać logarytm podstawowy 2, a następnie dodać 1 do tego. Przykład wartości 32-bitowej:

Zaokrąglij w górę do następnej najwyższej potęgi 2

unsigned int v; // compute the next highest power of 2 of 32-bit v

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

Rozszerzenie na inne szerokości powinno być oczywiste.


11
Nie jest to najbardziej wydajne rozwiązanie, ponieważ wiele procesorów ma specjalne instrukcje do zliczania zer wiodących, których można użyć do bardzo wydajnego obliczenia log2. Zobacz en.wikipedia.org/wiki/Find_first_set
Simon

7
@ Simon: to przenośne rozwiązanie. Nie ma wspólnego wydajnego algorytmu dla wszystkich architektur
phuclv

5
Co jeśli sama liczba jest potęgą dwóch?
Litherum,

5
Wątek ten jest nadal dobrze przywoływany, ale ta odpowiedź (i większość innych) jest bardzo nieaktualna. Procesory mają instrukcje, które mogą w tym pomóc (a właściwie już w tym czasie?). Od: jameshfisher.com/2018/03/30/round-up-power-2.html uint64_t next_pow2(uint64_t x) { return x == 1 ? 1 : 1<<(64-__builtin_clzl(x-1)); } I dla wersji 32-bitowej: uint32_t next_pow2(uint32_t x) { return x == 1 ? 1 : 1<<(32-__builtin_clz(x-1)); }To znaczy, jeśli używasz GCC (i chyba Clanga?), Ale rozsądnie byłoby poświęcić czas na znajdź połączenie do CLZ zamiast kopiowania i wklejania wszystkich dostępnych opcji.
MappaM

2
@MappaM Ta odpowiedź jest nadal bardzo aktualna i jest najlepszym przenośnym sposobem na to. Twoja wersja 64-bitowa ma niezdefiniowane zachowanie, jeśli x > UINT32_MAXnie jest bez rozgałęzienia. Ponadto GCC i Clang używają -mtune=genericdomyślnie (podobnie jak większość dystrybucji), więc twój kod NIE będzie rozwijał się do lzcntinstrukcji na x86_64 - w rzeczywistości rozwinie się do DUŻO wolniejszego (procedura libgcc), chyba że użyjesz czegoś takiego -march=native. Tak więc proponowana zamiana jest nieprzenośna, zawiera błędy i (zazwyczaj) jest wolniejsza.
Craig Barnes

76
next = pow(2, ceil(log(x)/log(2)));

Działa to poprzez znalezienie liczby, o którą podniesionobyś 2, aby uzyskać x (weź dziennik liczby i podziel przez dziennik żądanej bazy, więcej informacji na stronie wikipedia ). Następnie zaokrąglij to w górę, aby uzyskać najbliższą liczbę całkowitą.

Jest to metoda bardziej ogólnego przeznaczenia (tj. Wolniejsza!) Niż metody bitowe powiązane gdzie indziej, ale dobrze jest znać matematykę, co?


3
Od C99 możesz także użyć log2, jeśli jest obsługiwany przez twoje narzędzia. GCC i VS nie wydają się :(
Matthew

2
Brakuje Ci nawiasu ... next = pow (2, ceil (log (x) / log (2)));
Matthieu Cormier

13
Uważaj jednak na dokładność pływaka. log(pow(2,29))/log(2)= 29,000000000000004, więc wynik to 2 30 zamiast zwracania 2 29. Myślę, że właśnie dlatego istnieją funkcje log2?
endolith

48
Koszt tego wynosi prawdopodobnie co najmniej 200 cykli i nawet nie jest poprawny. Dlaczego to ma tak wiele pozytywnych opinii?
Axel Gneiting,

4
@ SuperflyJon Ale wspomina o bitowych operatorach i zakładam, że poprawność wynika z każdego pytania, chyba że zaznaczono inaczej.
BlackJack

50
unsigned long upper_power_of_two(unsigned long v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;

}

62
Byłoby miło, gdybyś go przypisał (chyba że go odkryłeś). Pochodzi ze strony nieco kręcących się hacków.
florin

3
Czy to dla liczby 32-bitowej? Rozszerzenie do wersji 64-bitowej
Jonathan Leffler

Jonathan, musisz to zrobić dla górnej połowy, a jeśli jest to zero, zrób to dla dolnej połowy.
florin

5
@florin, jeśli v jest typem 64-bitowym, czy nie możesz po prostu dodać „c | = v >> 32” po tym dla 16?
Evan Teran

3
Kod, który działa tylko dla określonej szerokości bitu, powinien używać typów o stałej szerokości zamiast typów o minimalnej szerokości. Ta funkcja powinna przyjąć i zwrócić a uint32_t.
Craig Barnes

50

Myślę, że to też działa:

int power = 1;
while(power < x)
    power*=2;

A odpowiedź jest power.


19
Uczciwie zadane pytanie o brak pętli. Ale tak sprytne jak niektóre inne funkcje, dla kodu, który nie jest wrażliwy na wydajność, odpowiedź, która jest szybko i łatwo zrozumiała i zweryfikowana pod kątem poprawności, zawsze wygrywa dla mnie.
Tim MB

2
To nie zwraca najbliższej potęgi 2, ale ta moc jest natychmiast większa niż X. Nadal bardzo dobra
CoffeDeveloper

1
Zamiast pomnożenia można użyć trochę „magii” bitowejpower <<= 1
Vallentin,

5
@Vallentin To powinno być automatycznie zoptymalizowane przez kompilator.
MarkWeston

4
Uważaj na nieskończoną pętlę, jeśli xjest za duża (tj. Za mało bitów, aby przedstawić następną potęgę 2).
alban

36

Jeśli używasz GCC, możesz rzucić okiem na Optymalizowanie funkcji next_pow2 () przez Lockless Inc .. Ta strona opisuje sposób korzystania z funkcji wbudowanej builtin_clz()(liczenie zera wiodącego), a później bezpośredniego używania x86 (ia32) instrukcja asemblera bsr(reverse nieco scan), tak jak to opisano w innym odpowiedź „s link miejscu GameDev . Ten kod może być szybszy niż opisany w poprzedniej odpowiedzi .

Nawiasem mówiąc, jeśli nie zamierzasz używać instrukcji asemblera i 64-bitowego typu danych, możesz tego użyć

/**
 * return the smallest power of two value
 * greater than x
 *
 * Input range:  [2..2147483648]
 * Output range: [2..2147483648]
 *
 */
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 1);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif

    return 1 << (32 - __builtin_clz (x - 1));
}

3
Zauważ, że to zwraca najmniejszą moc 2 większą niż OR równą x. Zmiana (x -1) na x zmienia funkcję zwracającą mniejszą moc 2 większą niż x.
Guillaume

2
Możesz używać _BitScanForwardw Visual C ++
KindDragon

Możesz także użyć__builtin_ctz()
MarkP

@MarkP __builtin_ctz()nie przyda się zaokrąglić żadną potęgę 2 liczby do następnej potęgi dwóch
Yann Droneaud

2
Dodaj w odpowiedzi link do listy Wikipedii wbudowanych funkcji bitowych dla innych kompilatorów: en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support                                Podaj także wersję 64-bitową. Proponuję następującą funkcję C ++ 11:              constexpr uint64_t nextPowerOfTwo64 (uint64_t x) { return 1ULL<<(sizeof(uint64_t) * 8 - __builtin_clzll(x)); }
olibre

15

Jeszcze jeden, chociaż używam cyklu, ale jest on znacznie szybszy niż operandy matematyczne

moc dwóch opcji „podłogowych”:

int power = 1;
while (x >>= 1) power <<= 1;

moc dwóch opcji „sufitu”:

int power = 2;
x--;    // <<-- UPDATED
while (x >>= 1) power <<= 1;

AKTUALIZACJA

Jak wspomniano w komentarzach, błąd polegał na tym, ceilże jego wynik był błędny.

Oto pełne funkcje:

unsigned power_floor(unsigned x) {
    int power = 1;
    while (x >>= 1) power <<= 1;
    return power;
}

unsigned power_ceil(unsigned x) {
    if (x <= 1) return 1;
    int power = 2;
    x--;
    while (x >>= 1) power <<= 1;
    return power;
}

2
wynik jest niepoprawny, jeśli xjest mocą 2. Potrzebny jest mikro do sprawdzenia, czy moc wejściowa wynosi 2. #define ISPOW2(x) ((x) > 0 && !((x) & (x-1)))
pgplus1628,

@zorksylar bardziej efektywnie byłobyif (x == 0) return 1; /* Or 0 (Which is what I use) */ x--; /* Rest of program */
2016

Dobre rozwiązanie! ale power of two "ceil" optionto nie jest poprawne. Na przykład, kiedy x = 2wynik powinien być 2zamiast4
MZD

10

W przypadku dowolnego niepodpisanego typu, opierając się na Bit Twiddling Hacks:

#include <climits>
#include <type_traits>

template <typename UnsignedType>
UnsignedType round_up_to_power_of_2(UnsignedType v) {
  static_assert(std::is_unsigned<UnsignedType>::value, "Only works for unsigned types");
  v--;
  for (size_t i = 1; i < sizeof(v) * CHAR_BIT; i *= 2) //Prefer size_t "Warning comparison between signed and unsigned integer"
  {
    v |= v >> i;
  }
  return ++v;
}

Tak naprawdę nie ma tam pętli, ponieważ kompilator zna w czasie kompilacji liczbę iteracji.


4
Zwróć uwagę, że pytanie dotyczy C.
martinkunev

@martinkunev Wystarczy wymienić UnsignedType i przetworzyć go ręcznie. Jestem prawie pewien, że programista C może rozwinąć ten prosty szablon, ignorując to std::is_unsigned<UnsignedType>::valuestwierdzenie.
user877329

2
@ user877329 Jasne, byłoby miło mieć odpowiedź w JavaScript, na wypadek, gdyby ktoś chciał przetłumaczyć to na C.
martinkunev

@martinkunev UnsignedType w JavaScript? W każdym razie to rozwiązanie pokazuje, jak to zrobić dla dowolnego UnsignedType, i zdarza się, że jest napisane w C ++, a nie w pseudokodzie [sizeof (v) * CHAR_BIT zamiast czegoś w rodzaju liczby bitów w obiekcie UnsignedType].
user877329

9

Dla pływaków IEEE możesz zrobić coś takiego.

int next_power_of_two(float a_F){
    int f = *(int*)&a_F;
    int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1

    f >>= 23; // remove factional part of floating point number
    f -= 127; // subtract 127 (the bias) from the exponent

    // adds one to the exponent if were not a power of two, 
    // then raises our new exponent to the power of two again.
    return (1 << (f + b)); 
}

Jeśli potrzebujesz rozwiązania liczb całkowitych i możesz użyć wbudowanego zestawu, BSR da ci log2 liczby całkowitej na x86. Zlicza, ile odpowiednich bitów jest ustawionych, co jest dokładnie równe log2 tej liczby. Inne procesory mają podobne instrukcje (często), takie jak CLZ, a w zależności od kompilatora może istnieć nieodłączny element do wykonania pracy za Ciebie.


To interesujące wydarzenie, choć niezwiązane z pytaniem (chcę zaokrąglić tylko liczby całkowite), wypróbuję to ...
Naveen

Przyszło do głowy po przeczytaniu artykułu w Wikipedii na temat pływaków. Poza tym użyłem go do obliczenia pierwiastków kwadratowych z dokładnością całkowitą. Również miłe, ale jeszcze bardziej niezwiązane.
Jasper Bekkers

To łamie surowe zasady aliasingu. W niektórych kompilatorach może nie działać lub wyświetlać ostrzeżenie.
martinkunev


5
/*
** http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
*/
#define __LOG2A(s) ((s &0xffffffff00000000) ? (32 +__LOG2B(s >>32)): (__LOG2B(s)))
#define __LOG2B(s) ((s &0xffff0000)         ? (16 +__LOG2C(s >>16)): (__LOG2C(s)))
#define __LOG2C(s) ((s &0xff00)             ? (8  +__LOG2D(s >>8)) : (__LOG2D(s)))
#define __LOG2D(s) ((s &0xf0)               ? (4  +__LOG2E(s >>4)) : (__LOG2E(s)))
#define __LOG2E(s) ((s &0xc)                ? (2  +__LOG2F(s >>2)) : (__LOG2F(s)))
#define __LOG2F(s) ((s &0x2)                ? (1)                  : (0))

#define LOG2_UINT64 __LOG2A
#define LOG2_UINT32 __LOG2B
#define LOG2_UINT16 __LOG2C
#define LOG2_UINT8  __LOG2D

static inline uint64_t
next_power_of_2(uint64_t i)
{
#if defined(__GNUC__)
    return 1UL <<(1 +(63 -__builtin_clzl(i -1)));
#else
    i =i -1;
    i =LOG2_UINT64(i);
    return 1UL <<(1 +i);
#endif
}

Jeśli nie chcesz zapuszczać się w sferę nieokreślonego zachowania, wartość wejściowa musi wynosić od 1 do 2 ^ 63. Makro jest również przydatne do ustawienia stałej w czasie kompilacji.


Jest to prawdopodobnie najgorsze rozwiązanie (brakuje też sufiksu ULL na 64-bitowej stałej). To wygeneruje 32 testy na wejście we wszystkich przypadkach. Lepiej użyć pętli while, zawsze będzie ona szybsza lub z tą samą prędkością.
xryl669,

1
ALE ... to może być ocenione przez preprocesor, jeśli dane wejściowe są stałe, a zatem ZERO działa w czasie wykonywania!
Michael

4

Dla kompletności oto implementacja zmiennoprzecinkowa w standardzie torfowiska C.

double next_power_of_two(double value) {
    int exp;
    if(frexp(value, &exp) == 0.5) {
        // Omit this case to round precise powers of two up to the *next* power
        return value;
    }
    return ldexp(1.0, exp);
}

1
Losowe przeglądarki, jeśli czytasz ten komentarz, wybierz ten kod. Jest to zdecydowanie najlepsza odpowiedź, bez specjalnych instrukcji, nie kręci się trochę, po prostu wydajny, przenośny i standardowy kod. Zgadywanie, dlaczego nikt inny go nie ocenił ^^
CoffeDeveloper,

5
Losowe przeglądarki, to będzie bardzo powolne, jeśli nie masz specjalistycznego sprzętu zmiennoprzecinkowego. Na x86 możesz biegać w kółko wokół tego kodu za pomocą bitów kręcących. rep bsr ecx,eax; mov eax,0; cmovnz eax,2; shl eax,cljest około 25 razy szybszy.
Johan

4

Wydajne rozwiązanie specyficzne dla Microsoft (np. Visual Studio 2017) w C / C ++ dla wprowadzania liczb całkowitych. Obsługuje przypadek wejścia dokładnie dopasowującego potęgę dwóch wartości poprzez zmniejszenie przed sprawdzeniem lokalizacji najbardziej znaczącego 1 bitu.

inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
    unsigned long Index;
    _BitScanReverse(&Index, Value - 1);
    return (1U << (Index + 1));
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

#if defined(WIN64) // The _BitScanReverse64 intrinsic is only available for 64 bit builds because it depends on x64

inline unsigned long long ExpandToPowerOf2(unsigned long long Value)
{
    unsigned long Index;
    _BitScanReverse64(&Index, Value - 1);
    return (1ULL << (Index + 1));
}

#endif

To generuje 5 lub mniej instrukcji dla procesora Intel podobnego do następującego:

dec eax
bsr rcx, rax
inc ecx
mov eax, 1
shl rax, cl

Najwyraźniej kompilator Visual Studio C ++ nie jest zakodowany w celu zoptymalizowania tego pod kątem wartości czasu kompilacji, ale nie jest tak, że zawiera wiele instrukcji.

Edytować:

Jeśli chcesz, aby wartość wejściowa 1 dawała 1 (2 do mocy zerowej), niewielka modyfikacja powyższego kodu nadal generuje bezpośrednie instrukcje bez rozgałęzienia.

inline unsigned int ExpandToPowerOf2(unsigned int Value)
{
    unsigned long Index;
    _BitScanReverse(&Index, --Value);
    if (Value == 0)
        Index = (unsigned long) -1;
    return (1U << (Index + 1));
}

Generuje tylko kilka instrukcji. Sztuka polega na tym, że indeks można zastąpić testem, a następnie instrukcją cmove.


Mały błąd: powinien zwrócić 1 za 1, ale tak nie jest.
0kcats

Dzięki. W aplikacji, dla której został opracowany, wyraźnie potrzebowaliśmy 2 do pierwszej mocy, gdy 1 jest wprowadzane. Mogę to potraktować jako przypadek specjalny bez warunkowania, bez generowania zbyt wielu dodatkowych instrukcji, jakie sobie wyobrażam.
NoelC

Zaktualizowano odpowiedź, aby uwzględnić wersję, która zwraca 1 dla wartości wejściowej 1.
NoelC

3

W x86 możesz użyć instrukcji manipulacji bitem sse4, aby przyspieszyć.

//assume input is in eax
popcnt edx,eax
lzcnt ecx,eax
cmp edx,1
jle @done       //popcnt says its a power of 2, return input unchanged
mov eax,2
shl eax,cl
@done: rep ret

W c można użyć pasujących elementów wewnętrznych.


Bezużyteczne, ale NIESAMOWITE!
Marco

3

Oto moje rozwiązanie w C. Mam nadzieję, że to pomaga!

int next_power_of_two(int n) {
    int i = 0;
    for (--n; n > 0; n >>= 1) {
        i++;
    }
    return 1 << i;
}

0

Wiele architektur procesorów obsługuje log base 2lub bardzo podobne operacje - count leading zeros. Wiele kompilatorów ma w tym coś wewnętrznego. Zobacz https://en.wikipedia.org/wiki/Find_first_set


nie chodzi o znalezienie najwyższego ustawionego bitu (= bsr) lub zliczanie wiodących zer. chce zaokrąglić w górę do najbliższej potęgi 2. odpowiedź brzmi „odejmij 1, a następnie zrób bsr i przesuń w lewo 1” robi to.
Flo

0

Zakładając, że masz dobry kompilator i to może zrobić trochę kręcenie przed ręką, która jest nade mną w tym momencie, ale i tak to działa !!!

    // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
    #define SH1(v)  ((v-1) | ((v-1) >> 1))            // accidently came up w/ this...
    #define SH2(v)  ((v) | ((v) >> 2))
    #define SH4(v)  ((v) | ((v) >> 4))
    #define SH8(v)  ((v) | ((v) >> 8))
    #define SH16(v) ((v) | ((v) >> 16))
    #define OP(v) (SH16(SH8(SH4(SH2(SH1(v))))))         

    #define CB0(v)   ((v) - (((v) >> 1) & 0x55555555))
    #define CB1(v)   (((v) & 0x33333333) + (((v) >> 2) & 0x33333333))
    #define CB2(v)   ((((v) + ((v) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24)
    #define CBSET(v) (CB2(CB1(CB0((v)))))
    #define FLOG2(v) (CBSET(OP(v)))

Kod testowy poniżej:

#include <iostream>

using namespace std;

// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
#define SH1(v)  ((v-1) | ((v-1) >> 1))  // accidently guess this...
#define SH2(v)  ((v) | ((v) >> 2))
#define SH4(v)  ((v) | ((v) >> 4))
#define SH8(v)  ((v) | ((v) >> 8))
#define SH16(v) ((v) | ((v) >> 16))
#define OP(v) (SH16(SH8(SH4(SH2(SH1(v))))))         

#define CB0(v)   ((v) - (((v) >> 1) & 0x55555555))
#define CB1(v)   (((v) & 0x33333333) + (((v) >> 2) & 0x33333333))
#define CB2(v)   ((((v) + ((v) >> 4) & 0xF0F0F0F) * 0x1010101) >> 24)
#define CBSET(v) (CB2(CB1(CB0((v)))))
#define FLOG2(v) (CBSET(OP(v))) 

#define SZ4         FLOG2(4)
#define SZ6         FLOG2(6)
#define SZ7         FLOG2(7)
#define SZ8         FLOG2(8) 
#define SZ9         FLOG2(9)
#define SZ16        FLOG2(16)
#define SZ17        FLOG2(17)
#define SZ127       FLOG2(127)
#define SZ1023      FLOG2(1023)
#define SZ1024      FLOG2(1024)
#define SZ2_17      FLOG2((1ul << 17))  // 
#define SZ_LOG2     FLOG2(SZ)

#define DBG_PRINT(x) do { std::printf("Line:%-4d" "  %10s = %-10d\n", __LINE__, #x, x); } while(0);

uint32_t arrTble[FLOG2(63)];

int main(){
    int8_t n;

    DBG_PRINT(SZ4);    
    DBG_PRINT(SZ6);    
    DBG_PRINT(SZ7);    
    DBG_PRINT(SZ8);    
    DBG_PRINT(SZ9); 
    DBG_PRINT(SZ16);
    DBG_PRINT(SZ17);
    DBG_PRINT(SZ127);
    DBG_PRINT(SZ1023);
    DBG_PRINT(SZ1024);
    DBG_PRINT(SZ2_17);

    return(0);
}

Wyjścia:

Line:39           SZ4 = 2
Line:40           SZ6 = 3
Line:41           SZ7 = 3
Line:42           SZ8 = 3
Line:43           SZ9 = 4
Line:44          SZ16 = 4
Line:45          SZ17 = 5
Line:46         SZ127 = 7
Line:47        SZ1023 = 10
Line:48        SZ1024 = 10
Line:49        SZ2_16 = 17

0

Próbuję uzyskać najbliższą niższą moc 2 i włączyć tę funkcję. Może ci to pomóc. Wystarczy pomnożyć najbliższą dolną liczbę razy 2, aby uzyskać najbliższą górną potęgę 2

int nearest_upper_power(int number){
    int temp=number;
    while((number&(number-1))!=0){
        temp<<=1;
        number&=temp;
    }
    //Here number is closest lower power 
    number*=2;
    return number;
}

0

Dostosowana odpowiedź Paula Dixona do Excela działa idealnie.

 =POWER(2,CEILING.MATH(LOG(A1)/LOG(2)))

0

Odmiana odpowiedzi @YannDroneaud jest ważna dla x==1, tylko dla platform x86, kompilatorów, gcc lub clang:

__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 0);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif
  int clz;
  uint32_t xm1 = x-1;
  asm(
    "lzcnt %1,%0"
    :"=r" (clz)
    :"rm" (xm1)
    :"cc"
    );
    return 1 << (32 - clz);
}

0

Oto, czego używam, aby mieć to stałe wyrażenie, jeśli dane wejściowe są stałym wyrażeniem.

#define uptopow2_0(v) ((v) - 1)
#define uptopow2_1(v) (uptopow2_0(v) | uptopow2_0(v) >> 1)
#define uptopow2_2(v) (uptopow2_1(v) | uptopow2_1(v) >> 2)
#define uptopow2_3(v) (uptopow2_2(v) | uptopow2_2(v) >> 4)
#define uptopow2_4(v) (uptopow2_3(v) | uptopow2_3(v) >> 8)
#define uptopow2_5(v) (uptopow2_4(v) | uptopow2_4(v) >> 16)

#define uptopow2(v) (uptopow2_5(v) + 1)  /* this is the one programmer uses */

Na przykład wyrażenie takie jak:

uptopow2(sizeof (struct foo))

ładnie zredukuje się do stałej.



0

Konwertuj go na liczbę zmiennoprzecinkową, a następnie użyj .hex (), który pokazuje znormalizowaną reprezentację IEEE.

>>> float(789).hex() '0x1.8a80000000000p+9'

Następnie wyodrębnij wykładnik potęgi i dodaj 1.

>>> int(float(789).hex().split('p+')[1]) + 1 10

I podnieś 2 do tej mocy.

>>> 2 ** (int(float(789).hex().split('p+')[1]) + 1) 1024


Zauważ, że ta odpowiedź jest w pythonie
David Wallace

0
import sys


def is_power2(x):
    return x > 0 and ((x & (x - 1)) == 0)


def find_nearest_power2(x):
    if x <= 0:
        raise ValueError("invalid input")
    if is_power2(x):
        return x
    else:
        bits = get_bits(x)
        upper = 1 << (bits)
        lower = 1 << (bits - 1)
        mid = (upper + lower) // 2
        if (x - mid) > 0:
            return upper
        else:
            return lower


def get_bits(x):
    """return number of bits in binary representation"""
    if x < 0:
        raise ValueError("invalid input: input should be positive integer")
    count = 0
    while (x != 0):
        try:
            x = x >> 1
        except TypeError as error:
            print(error, "input should be of type integer")
            sys.exit(1)
        count += 1
    return count

-1

Jeśli potrzebujesz go do rzeczy związanych z OpenGL:

/* Compute the nearest power of 2 number that is 
 * less than or equal to the value passed in. 
 */
static GLuint 
nearestPower( GLuint value )
{
    int i = 1;

    if (value == 0) return -1;      /* Error! */
    for (;;) {
         if (value == 1) return i;
         else if (value == 3) return i*4;
         value >>= 1; i *= 2;
    }
}

8
„for” to pętla.
florin

1
florin: jest. i jest tutaj używany jako pętla, prawda?
Tamas Czinege

9
DrJokepu - Myślę, że Florin chciał tutaj powiedzieć, że OP poprosił o rozwiązanie bez pętli
Eli Bendersky,

-1

Jeśli chcesz szablon z jedną linią. Oto jest

int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>1)>>2)>>4)>>8)>>16); }

lub

int nxt_po2(int n) { return 1 + (n|=(n|=(n|=(n|=(n|=(n-=1)>>(1<<0))>>(1<<1))>>(1<<2))>>(1<<3))>>(1<<4)); }

Jest to niezdefiniowane zachowanie w C lub C ++ i prowadzi do błędów. nWielokrotne modyfikowanie bez punktu sekwencji jest nieprawidłowe. Napisałeś to tak, jakby to n-=1miało być pierwsze, ale jedyną gwarancją jest to, że nzawiera nową wartość po, ;a nawiasy nie zmieniają tego.
sam hocevar

Co więcej, powoduje to, że moje oczy krwawią.
Donal Fellows
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.