Zaokrąglenie do następnej potęgi 2

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?

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.

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?

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;

}

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

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

A odpowiedź jest power.

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

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

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.

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.

Pomimo tego pytania jest oznaczone jako cmoje pięć centów. Na szczęście, C ++ 20 będzie zawierać std::ceil2i std::floor2(patrz tutaj ). Są to consexprfunkcje szablonów, obecna implementacja GCC wykorzystuje przesunięcie bitów i działa z dowolnym zintegrowanym typem bez znaku.

/*
** 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.

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

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.

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.

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

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

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

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

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

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

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

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.

Pomocne w osiągnięciu celu może być następujące wyjaśnienie:

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

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

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

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