Arredondando para a próxima potência de 2

Eu quero escrever uma function que retorna a próxima potência mais próxima de 2 números. Por exemplo, se minha input é 789, a saída deve ser 1024. Existe alguma maneira de conseguir isso sem usar nenhum loop, mas apenas usando alguns operadores bitwise?

Verifique os Bit Twins Hacks . Você precisa obter o logaritmo de base 2 e adicionar 1 a ele. Exemplo para um valor de 32 bits:

Arredondar para a próxima maior potência de 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++; 

A extensão para outras larguras deve ser óbvia.

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

Isso funciona encontrando o número que você teria aumentado 2 para obter x (pegue o log do número e divida pelo log da base desejada, veja wikipedia para saber mais ). Em seguida, arredonde isso com ceil para obter o número inteiro mais próximo.

Este é um método mais geral (isto é, mais lento!) Do que os methods bitwise ligados em outro lugar, mas é bom conhecer as matemáticas, hein?

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

Eu acho que isso funciona também:

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

E a resposta é power .

Se você estiver usando o GCC, você pode querer dar uma olhada em Otimizando a function next_pow2 () da Lockless Inc .. Esta página descreve uma maneira de usar a function builtin_clz() (count zero) e depois usar diretamente x86 (ia32) assembler instrução bsr (bit scan reverso), assim como é descrito no link de outra resposta para o site gamedev . Esse código pode ser mais rápido que os descritos na resposta anterior .

By the way, se você não vai usar instrução assembler e tipo de dados de 64 bits, você pode usar este

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

Mais um, embora eu use ciclo, mas isso é muito mais rápido que os operandos matemáticos

poder de dois “andar” opção:

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

poder de dois "ceil" opção:

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

ATUALIZAR

Como mencionado nos comentários, houve erro no ceil onde o resultado foi errado.

Aqui estão as funções completas:

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

Para os carros alegóricos do IEEE, você seria capaz de fazer algo assim.

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

Se você precisar de uma solução inteira e conseguir usar a assembly inline, o BSR fornecerá o log2 de um número inteiro no x86. Conta quantos bits certos estão definidos, o que é exatamente igual ao log2 daquele número. Outros processadores têm instruções semelhantes (frequentemente), como o CLZ e, dependendo do seu compilador, pode haver uma disponibilidade intrínseca para fazer o trabalho para você.

Para qualquer tipo não assinado, baseado nos Bit Twiddling Hacks:

 #include  #include  template  UnsignedType round_up_to_power_of_2(UnsignedType v) { static_assert(std::is_unsigned::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; } 

Não há realmente um loop lá como o compilador sabe em tempo de compilation o número de iterações.

Para completar, aqui está uma implementação de ponto flutuante no pântano-padrão 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); } 
 /* ** 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 } 

Se você não quiser se aventurar no domínio do comportamento indefinido, o valor de input deve estar entre 1 e 2 ^ 63. A macro também é útil para definir constante em tempo de compilation.

Muitas arquiteturas de processadores suportam log base 2 ou count leading zeros operação muito semelhantes. Muitos compiladores possuem intrínsecos para isso. Veja https://en.wikipedia.org/wiki/Find_first_set

Uma solução específica eficiente da Microsoft (por exemplo, Visual Studio 2017) em C / C ++ para input de números inteiros. Lida com o caso da input combinando exatamente com uma potência de dois valores, decrementando antes de verificar a localização do bit mais significativo.

 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 

Isso gera 5 ou mais instruções embutidas para um processador Intel semelhante ao seguinte:

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

Aparentemente, o compilador do Visual Studio C ++ não é codificado para otimizar isso para valores de tempo de compilation, mas não é como se houvesse um monte de instruções lá.

Editar:

Se você quiser um valor de input de 1 para gerar 1 (2 para o poder zeroth), uma pequena modificação para o código acima ainda gera instruções direto com nenhuma ramificação.

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

Gera apenas mais algumas instruções. O truque é que o Index pode ser substituído por um teste seguido por uma instrução cmove.

No x86, você pode usar as instruções de manipulação do bit sse4 para torná-lo rápido.

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

Em c, você pode usar os intrínsecos correspondentes.

Assumindo que você tenha um bom compilador, ele pode fazer o bit girar antes da mão que está acima de mim neste ponto, mas de qualquer forma isso funciona !!!

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

Código de teste abaixo:

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

Saídas:

 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 

Eu estou tentando obter a potência mais baixa de 2 e fiz esta function. Pode ajudá-lo. Apenas multiplicado mais próximo número mais baixo vezes 2 para obter a potência superior mais próxima de 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; } 

Se você precisar de coisas relacionadas ao 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; } }