Rounding up to next power of 2

Question

I want to write a function that returns the nearest next power of 2 number  For example if my input is 789  the output should be 1024  Is there any way of achieving this without using any loops but just using some bitwise operators

User · Answer

A variant of  YannDroneaud answer valid for x  1  only for x86 plateforms  compilers  gcc or clang     attribute     const   static inline uint32 t p2 uint32 t x     if 0     assert x  gt  0       assert x  lt     UINT32 MAX 2    1     endif   int clz    uint32 t xm1   x-1    asm       lzcnt  1  0         r   clz        rm   xm1        cc             return 1  lt  lt   32 - clz

User · Answer

Convert it to a float and then use  hex   which shows the normalized IEEE representation    gt  gt  gt  float 789  hex    0x1 8a80000000000p 9    Then just extract the exponent and add 1    gt  gt  gt  int float 789  hex   split  p    1     1 10   And raise 2 to this power    gt  gt  gt  2     int float 789  hex   split  p    1     1  1024

User · Answer

If you need it for OpenGL related stuff      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  gt  gt   1  i    2

User · Answer

unsigned long upper power of two unsigned long v        v--      v    v  gt  gt  1      v    v  gt  gt  2      v    v  gt  gt  4      v    v  gt  gt  8      v    v  gt  gt  16      v        return v

User · Answer

For any unsigned type  building on the Bit Twiddling Hacks    include  lt climits gt   include  lt type traits gt   template  lt typename UnsignedType gt  UnsignedType round up to power of 2 UnsignedType v      static assert std  is unsigned lt UnsignedType gt   value   Only works for unsigned types      v--    for  size t i   1  i  lt  sizeof v    CHAR BIT  i    2    Prefer size t  Warning comparison between signed and unsigned integer          v    v  gt  gt  i        return   v      There isn t really a loop there as the compiler knows at compile time the number of iterations

User · Answer

Convert it to a float and then use  hex   which shows the normalized IEEE representation    gt  gt  gt  float 789  hex    0x1 8a80000000000p 9    Then just extract the exponent and add 1    gt  gt  gt  int float 789  hex   split  p    1     1 10   And raise 2 to this power    gt  gt  gt  2     int float 789  hex   split  p    1     1  1024

User · Answer

Here s my solution in C  Hope this helps   int next power of two int n        int i   0      for  --n  n  gt  0  n  gt  gt   1            i              return 1  lt  lt  i

User · Answer

next   pow 2  ceil log x  log 2       This works by finding the number you d have raise 2 by to get x  take the log of the number  and divide by the log of the desired base  see wikipedia for more   Then round that up with ceil to get the nearest whole number power   This is a more general purpose  i e  slower   method than the bitwise methods linked elsewhere  but good to know the maths  eh

User · Answer

Despite the question is tagged as c here my five cents  Lucky us  C   20 would include std  ceil2 and std  floor2  see here   It is consexpr template functions  current GCC implementation uses bitshifting and works with any integral unsigned type

User · Answer

Portable solution in C   long value   27 long nextPowerOfTwo   1  lt  lt   int Math Ceiling Math Log2 value     nextPowerOfTwo is 32  Math Ceiling Math Log2 value   calculates the exponent of the next power of two  the 1  lt  lt  calculates the real value through bitshifting

User · Answer

Many processor architectures support log base 2 or very similar operation     count leading zeros  Many compilers have intrinsics for it  See https   en wikipedia org wiki Find first set

User · Answer

One more  although I use cycle  but thi is much faster than math operands  power of two  floor  option   int power   1  while  x  gt  gt   1  power  lt  lt   1    power of two  ceil  option   int power   2  x--         lt  lt -- UPDATED while  x  gt  gt   1  power  lt  lt   1      UPDATE  As mentioned in comments there was mistake in ceil where its result was wrong   Here are full functions   unsigned power floor unsigned x        int power   1      while  x  gt  gt   1  power  lt  lt   1      return power     unsigned power ceil unsigned x        if  x  lt   1  return 1      int power   2      x--      while  x  gt  gt   1  power  lt  lt   1      return power

User · Answer

unsigned long upper power of two unsigned long v        v--      v    v  gt  gt  1      v    v  gt  gt  2      v    v  gt  gt  4      v    v  gt  gt  8      v    v  gt  gt  16      v        return v

User · Answer

I m trying to get nearest lower power of 2 and made this function  May it help you Just multiplied nearest lower number times 2 to get nearest upper power of 2  int nearest upper power int number       int temp number      while  number amp  number-1    0           temp lt  lt  1          number amp  temp              Here number is closest lower power      number  2      return number

User · Answer

I think this works  too   int power   1  while power  lt  x      power  2    And the answer is power

User · Answer

next   pow 2  ceil log x  log 2       This works by finding the number you d have raise 2 by to get x  take the log of the number  and divide by the log of the desired base  see wikipedia for more   Then round that up with ceil to get the nearest whole number power   This is a more general purpose  i e  slower   method than the bitwise methods linked elsewhere  but good to know the maths  eh

User · Answer

If you re using GCC  you might want to have a look at Optimizing the next pow2   function by Lockless Inc   This page describes a way to use built-in function builtin clz    count leading zero  and later use directly x86  ia32  assembler instruction bsr  bit scan reverse   just like it s described in another answer s link to gamedev site  This code might be faster than those described in previous answer   By the way  if you re not going to use assembler instruction and 64bit data type  you can use this         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  gt  1       assert x  lt     UINT32 MAX 2    1     endif      return 1  lt  lt   32 -   builtin clz  x - 1

User · Answer

One more  although I use cycle  but thi is much faster than math operands  power of two  floor  option   int power   1  while  x  gt  gt   1  power  lt  lt   1    power of two  ceil  option   int power   2  x--         lt  lt -- UPDATED while  x  gt  gt   1  power  lt  lt   1      UPDATE  As mentioned in comments there was mistake in ceil where its result was wrong   Here are full functions   unsigned power floor unsigned x        int power   1      while  x  gt  gt   1  power  lt  lt   1      return power     unsigned power ceil unsigned x        if  x  lt   1  return 1      int power   2      x--      while  x  gt  gt   1  power  lt  lt   1      return power

User · Answer

import sys   def is power2 x       return x  gt  0 and   x  amp   x - 1      0    def find nearest power2 x       if x  lt   0          raise ValueError  invalid input       if is power2 x           return x     else          bits   get bits x          upper   1  lt  lt   bits          lower   1  lt  lt   bits - 1          mid    upper   lower     2         if  x - mid   gt  0              return upper         else              return lower   def get bits x          return number of bits in binary representation        if x  lt  0          raise ValueError  invalid input  input should be positive integer       count   0     while  x    0           try              x   x  gt  gt  1         except TypeError as error              print error   input should be of type integer               sys exit 1          count    1     return count

User · Answer

next   pow 2  ceil log x  log 2       This works by finding the number you d have raise 2 by to get x  take the log of the number  and divide by the log of the desired base  see wikipedia for more   Then round that up with ceil to get the nearest whole number power   This is a more general purpose  i e  slower   method than the bitwise methods linked elsewhere  but good to know the maths  eh

User · Answer

If you want an one-line-template  Here it is  int nxt po2 int n    return 1    n   n   n   n   n   n- 1  gt  gt 1  gt  gt 2  gt  gt 4  gt  gt 8  gt  gt 16       or   int nxt po2 int n    return 1    n   n   n   n   n   n- 1  gt  gt  1 lt  lt 0   gt  gt  1 lt  lt 1   gt  gt  1 lt  lt 2   gt  gt  1 lt  lt 3   gt  gt  1 lt  lt 4

User · Answer

Despite the question is tagged as c here my five cents  Lucky us  C   20 would include std  ceil2 and std  floor2  see here   It is consexpr template functions  current GCC implementation uses bitshifting and works with any integral unsigned type

User · Answer

For IEEE floats you d be able to do something like this   int next power of two float a F       int f     int   amp a F      int b   f  lt  lt  9    0     If we re a power of two this is 0  otherwise this is 1      f  gt  gt   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  lt  lt   f   b         If you need an integer solution and you re able to use inline assembly  BSR will give you the log2 of an integer on the x86  It counts how many right bits are set  which is exactly equal to the log2 of that number  Other processors have similar instructions  often   such as CLZ and depending on your compiler there might be an intrinsic available to do the work for you

User · Answer

An efficient Microsoft  e g   Visual Studio 2017  specific solution in C   C   for integer input   Handles the case of the input exactly matching a power of two value by decrementing before checking the location of the most significant 1 bit   inline unsigned int ExpandToPowerOf2 unsigned int Value        unsigned long Index       BitScanReverse  amp Index  Value - 1       return  1U  lt  lt   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  amp Index  Value - 1       return  1ULL  lt  lt   Index   1        endif   This generates 5 or so inlined instructions for an Intel processor similar to the following   dec eax bsr rcx  rax inc ecx mov eax  1 shl rax  cl   Apparently the Visual Studio C   compiler isn t coded to optimize this for compile-time values  but it s not like there are a whole lot of instructions there   Edit   If you want an input value of 1 to yield 1  2 to the zeroth power   a small modification to the above code still generates straight through instructions with no branch   inline unsigned int ExpandToPowerOf2 unsigned int Value        unsigned long Index       BitScanReverse  amp Index  --Value       if  Value    0          Index    unsigned long  -1      return  1U  lt  lt   Index   1        Generates just a few more instructions   The trick is that Index can be replaced by a test followed by a cmove instruction

User · Answer

For IEEE floats you d be able to do something like this   int next power of two float a F       int f     int   amp a F      int b   f  lt  lt  9    0     If we re a power of two this is 0  otherwise this is 1      f  gt  gt   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  lt  lt   f   b         If you need an integer solution and you re able to use inline assembly  BSR will give you the log2 of an integer on the x86  It counts how many right bits are set  which is exactly equal to the log2 of that number  Other processors have similar instructions  often   such as CLZ and depending on your compiler there might be an intrinsic available to do the work for you

User · Answer

For IEEE floats you d be able to do something like this   int next power of two float a F       int f     int   amp a F      int b   f  lt  lt  9    0     If we re a power of two this is 0  otherwise this is 1      f  gt  gt   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  lt  lt   f   b         If you need an integer solution and you re able to use inline assembly  BSR will give you the log2 of an integer on the x86  It counts how many right bits are set  which is exactly equal to the log2 of that number  Other processors have similar instructions  often   such as CLZ and depending on your compiler there might be an intrinsic available to do the work for you

User · Answer

I m trying to get nearest lower power of 2 and made this function  May it help you Just multiplied nearest lower number times 2 to get nearest upper power of 2  int nearest upper power int number       int temp number      while  number amp  number-1    0           temp lt  lt  1          number amp  temp              Here number is closest lower power      number  2      return number

User · Answer

Check the Bit Twiddling Hacks  You need to get the base 2 logarithm  then add 1 to that   Example for a 32-bit value      Round up to the next highest power of 2  unsigned int v     compute the next highest power of 2 of 32-bit v  v--  v    v  gt  gt  1  v    v  gt  gt  2  v    v  gt  gt  4  v    v  gt  gt  8  v    v  gt  gt  16  v       The extension to other widths should be obvious

User · Answer

Assuming you have a good compiler  amp  it can do the bit twiddling before hand thats above me at this point  but anyway this works            http   graphics stanford edu  seander bithacks html IntegerLogObvious      define SH1 v     v-1      v-1   gt  gt  1                 accidently came up w  this         define SH2 v     v      v   gt  gt  2        define SH4 v     v      v   gt  gt  4        define SH8 v     v      v   gt  gt  8        define SH16 v    v      v   gt  gt  16        define OP v   SH16 SH8 SH4 SH2 SH1 v                      define CB0 v      v  -    v   gt  gt  1   amp  0x55555555        define CB1 v       v   amp  0x33333333       v   gt  gt  2   amp  0x33333333        define CB2 v        v      v   gt  gt  4   amp  0xF0F0F0F    0x1010101   gt  gt  24       define CBSET v   CB2 CB1 CB0  v           define FLOG2 v   CBSET OP v      Test code below    include  lt iostream gt   using namespace std      http   graphics stanford edu  seander bithacks html IntegerLogObvious  define SH1 v     v-1      v-1   gt  gt  1       accidently guess this     define SH2 v     v      v   gt  gt  2    define SH4 v     v      v   gt  gt  4    define SH8 v     v      v   gt  gt  8    define SH16 v    v      v   gt  gt  16    define OP v   SH16 SH8 SH4 SH2 SH1 v                  define CB0 v      v  -    v   gt  gt  1   amp  0x55555555    define CB1 v       v   amp  0x33333333       v   gt  gt  2   amp  0x33333333    define CB2 v        v      v   gt  gt  4   amp  0xF0F0F0F    0x1010101   gt  gt  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  lt  lt  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       Outputs   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

User · Answer

Adapted Paul Dixon s answer to Excel  this works perfectly     POWER 2 CEILING MATH LOG A1  LOG 2

User · Answer

If you want an one-line-template  Here it is  int nxt po2 int n    return 1    n   n   n   n   n   n- 1  gt  gt 1  gt  gt 2  gt  gt 4  gt  gt 8  gt  gt 16       or   int nxt po2 int n    return 1    n   n   n   n   n   n- 1  gt  gt  1 lt  lt 0   gt  gt  1 lt  lt 1   gt  gt  1 lt  lt 2   gt  gt  1 lt  lt 3   gt  gt  1 lt  lt 4

User · Answer

next   pow 2  ceil log x  log 2       This works by finding the number you d have raise 2 by to get x  take the log of the number  and divide by the log of the desired base  see wikipedia for more   Then round that up with ceil to get the nearest whole number power   This is a more general purpose  i e  slower   method than the bitwise methods linked elsewhere  but good to know the maths  eh

User · Answer

I think this works  too   int power   1  while power  lt  x      power  2    And the answer is power

User · Answer

import sys   def is power2 x       return x  gt  0 and   x  amp   x - 1      0    def find nearest power2 x       if x  lt   0          raise ValueError  invalid input       if is power2 x           return x     else          bits   get bits x          upper   1  lt  lt   bits          lower   1  lt  lt   bits - 1          mid    upper   lower     2         if  x - mid   gt  0              return upper         else              return lower   def get bits x          return number of bits in binary representation        if x  lt  0          raise ValueError  invalid input  input should be positive integer       count   0     while  x    0           try              x   x  gt  gt  1         except TypeError as error              print error   input should be of type integer               sys exit 1          count    1     return count

User · Answer

Here s my solution in C  Hope this helps   int next power of two int n        int i   0      for  --n  n  gt  0  n  gt  gt   1            i              return 1  lt  lt  i

User · Answer

You might find the following clarification to be helpful towards your purpose

User · Answer

http   graphics stanford edu  seander bithacks html IntegerLog     define   LOG2A s    s  amp 0xffffffff00000000     32    LOG2B s  gt  gt 32       LOG2B s     define   LOG2B s    s  amp 0xffff0000             16    LOG2C s  gt  gt 16       LOG2C s     define   LOG2C s    s  amp 0xff00                 8     LOG2D s  gt  gt 8        LOG2D s     define   LOG2D s    s  amp 0xf0                   4     LOG2E s  gt  gt 4        LOG2E s     define   LOG2E s    s  amp 0xc                    2     LOG2F s  gt  gt 2        LOG2F s     define   LOG2F s    s  amp 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  lt  lt  1   63 -  builtin clzl i -1      else     i  i -1      i  LOG2 UINT64 i       return 1UL  lt  lt  1  i    endif     If you do not want to venture into the realm of undefined behaviour the input value must be between 1 and 2 63  The macro is also useful to set constant at compile time

User · Answer

Here is what I m using to have this be a constant expression  if the input is a constant expression    define uptopow2 0 v    v  - 1   define uptopow2 1 v   uptopow2 0 v    uptopow2 0 v   gt  gt  1   define uptopow2 2 v   uptopow2 1 v    uptopow2 1 v   gt  gt  2   define uptopow2 3 v   uptopow2 2 v    uptopow2 2 v   gt  gt  4   define uptopow2 4 v   uptopow2 3 v    uptopow2 3 v   gt  gt  8   define uptopow2 5 v   uptopow2 4 v    uptopow2 4 v   gt  gt  16    define uptopow2 v   uptopow2 5 v    1      this is the one programmer uses      So for instance  an expression like   uptopow2 sizeof  struct foo     will nicely reduce to a constant

User · Answer

In x86 you can use the sse4 bit manipulation instructions to make it fast     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   In c you can use the matching intrinsics

User · Answer

For any unsigned type  building on the Bit Twiddling Hacks    include  lt climits gt   include  lt type traits gt   template  lt typename UnsignedType gt  UnsignedType round up to power of 2 UnsignedType v      static assert std  is unsigned lt UnsignedType gt   value   Only works for unsigned types      v--    for  size t i   1  i  lt  sizeof v    CHAR BIT  i    2    Prefer size t  Warning comparison between signed and unsigned integer          v    v  gt  gt  i        return   v      There isn t really a loop there as the compiler knows at compile time the number of iterations

User · Answer

In x86 you can use the sse4 bit manipulation instructions to make it fast     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   In c you can use the matching intrinsics

User · Answer

If you re using GCC  you might want to have a look at Optimizing the next pow2   function by Lockless Inc   This page describes a way to use built-in function builtin clz    count leading zero  and later use directly x86  ia32  assembler instruction bsr  bit scan reverse   just like it s described in another answer s link to gamedev site  This code might be faster than those described in previous answer   By the way  if you re not going to use assembler instruction and 64bit data type  you can use this         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  gt  1       assert x  lt     UINT32 MAX 2    1     endif      return 1  lt  lt   32 -   builtin clz  x - 1

User · Answer

Check the Bit Twiddling Hacks  You need to get the base 2 logarithm  then add 1 to that   Example for a 32-bit value      Round up to the next highest power of 2  unsigned int v     compute the next highest power of 2 of 32-bit v  v--  v    v  gt  gt  1  v    v  gt  gt  2  v    v  gt  gt  4  v    v  gt  gt  8  v    v  gt  gt  16  v       The extension to other widths should be obvious

User · Answer

Many processor architectures support log base 2 or very similar operation     count leading zeros  Many compilers have intrinsics for it  See https   en wikipedia org wiki Find first set

User · Answer

Portable solution in C   long value   27 long nextPowerOfTwo   1  lt  lt   int Math Ceiling Math Log2 value     nextPowerOfTwo is 32  Math Ceiling Math Log2 value   calculates the exponent of the next power of two  the 1  lt  lt  calculates the real value through bitshifting

User · Answer

unsigned long upper power of two unsigned long v        v--      v    v  gt  gt  1      v    v  gt  gt  2      v    v  gt  gt  4      v    v  gt  gt  8      v    v  gt  gt  16      v        return v

User · Answer

Check the Bit Twiddling Hacks  You need to get the base 2 logarithm  then add 1 to that   Example for a 32-bit value      Round up to the next highest power of 2  unsigned int v     compute the next highest power of 2 of 32-bit v  v--  v    v  gt  gt  1  v    v  gt  gt  2  v    v  gt  gt  4  v    v  gt  gt  8  v    v  gt  gt  16  v       The extension to other widths should be obvious

User · Answer

You might find the following clarification to be helpful towards your purpose

User · Answer

For IEEE floats you d be able to do something like this   int next power of two float a F       int f     int   amp a F      int b   f  lt  lt  9    0     If we re a power of two this is 0  otherwise this is 1      f  gt  gt   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  lt  lt   f   b         If you need an integer solution and you re able to use inline assembly  BSR will give you the log2 of an integer on the x86  It counts how many right bits are set  which is exactly equal to the log2 of that number  Other processors have similar instructions  often   such as CLZ and depending on your compiler there might be an intrinsic available to do the work for you

User · Answer

If you need it for OpenGL related stuff      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  gt  gt   1  i    2

User · Answer

http   graphics stanford edu  seander bithacks html IntegerLog     define   LOG2A s    s  amp 0xffffffff00000000     32    LOG2B s  gt  gt 32       LOG2B s     define   LOG2B s    s  amp 0xffff0000             16    LOG2C s  gt  gt 16       LOG2C s     define   LOG2C s    s  amp 0xff00                 8     LOG2D s  gt  gt 8        LOG2D s     define   LOG2D s    s  amp 0xf0                   4     LOG2E s  gt  gt 4        LOG2E s     define   LOG2E s    s  amp 0xc                    2     LOG2F s  gt  gt 2        LOG2F s     define   LOG2F s    s  amp 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  lt  lt  1   63 -  builtin clzl i -1      else     i  i -1      i  LOG2 UINT64 i       return 1UL  lt  lt  1  i    endif     If you do not want to venture into the realm of undefined behaviour the input value must be between 1 and 2 63  The macro is also useful to set constant at compile time

User · Answer

Check the Bit Twiddling Hacks  You need to get the base 2 logarithm  then add 1 to that   Example for a 32-bit value      Round up to the next highest power of 2  unsigned int v     compute the next highest power of 2 of 32-bit v  v--  v    v  gt  gt  1  v    v  gt  gt  2  v    v  gt  gt  4  v    v  gt  gt  8  v    v  gt  gt  16  v       The extension to other widths should be obvious

User · Answer

If you need it for OpenGL related stuff      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  gt  gt   1  i    2

User · Answer

Adapted Paul Dixon s answer to Excel  this works perfectly     POWER 2 CEILING MATH LOG A1  LOG 2

User · Answer

For completeness here is a floating-point implementation in bog-standard C   double next power of two double value        int exp      if frexp value   amp exp     0 5               Omit this case to round precise powers of two up to the  next  power         return value            return ldexp 1 0  exp

User · Answer

Here is what I m using to have this be a constant expression  if the input is a constant expression    define uptopow2 0 v    v  - 1   define uptopow2 1 v   uptopow2 0 v    uptopow2 0 v   gt  gt  1   define uptopow2 2 v   uptopow2 1 v    uptopow2 1 v   gt  gt  2   define uptopow2 3 v   uptopow2 2 v    uptopow2 2 v   gt  gt  4   define uptopow2 4 v   uptopow2 3 v    uptopow2 3 v   gt  gt  8   define uptopow2 5 v   uptopow2 4 v    uptopow2 4 v   gt  gt  16    define uptopow2 v   uptopow2 5 v    1      this is the one programmer uses      So for instance  an expression like   uptopow2 sizeof  struct foo     will nicely reduce to a constant

User · Answer

For completeness here is a floating-point implementation in bog-standard C   double next power of two double value        int exp      if frexp value   amp exp     0 5               Omit this case to round precise powers of two up to the  next  power         return value            return ldexp 1 0  exp

User · Answer

A variant of  YannDroneaud answer valid for x  1  only for x86 plateforms  compilers  gcc or clang     attribute     const   static inline uint32 t p2 uint32 t x     if 0     assert x  gt  0       assert x  lt     UINT32 MAX 2    1     endif   int clz    uint32 t xm1   x-1    asm       lzcnt  1  0         r   clz        rm   xm1        cc             return 1  lt  lt   32 - clz

User · Answer

An efficient Microsoft  e g   Visual Studio 2017  specific solution in C   C   for integer input   Handles the case of the input exactly matching a power of two value by decrementing before checking the location of the most significant 1 bit   inline unsigned int ExpandToPowerOf2 unsigned int Value        unsigned long Index       BitScanReverse  amp Index  Value - 1       return  1U  lt  lt   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  amp Index  Value - 1       return  1ULL  lt  lt   Index   1        endif   This generates 5 or so inlined instructions for an Intel processor similar to the following   dec eax bsr rcx  rax inc ecx mov eax  1 shl rax  cl   Apparently the Visual Studio C   compiler isn t coded to optimize this for compile-time values  but it s not like there are a whole lot of instructions there   Edit   If you want an input value of 1 to yield 1  2 to the zeroth power   a small modification to the above code still generates straight through instructions with no branch   inline unsigned int ExpandToPowerOf2 unsigned int Value        unsigned long Index       BitScanReverse  amp Index  --Value       if  Value    0          Index    unsigned long  -1      return  1U  lt  lt   Index   1        Generates just a few more instructions   The trick is that Index can be replaced by a test followed by a cmove instruction

User · Answer

unsigned long upper power of two unsigned long v        v--      v    v  gt  gt  1      v    v  gt  gt  2      v    v  gt  gt  4      v    v  gt  gt  8      v    v  gt  gt  16      v        return v

User · Answer

Assuming you have a good compiler  amp  it can do the bit twiddling before hand thats above me at this point  but anyway this works            http   graphics stanford edu  seander bithacks html IntegerLogObvious      define SH1 v     v-1      v-1   gt  gt  1                 accidently came up w  this         define SH2 v     v      v   gt  gt  2        define SH4 v     v      v   gt  gt  4        define SH8 v     v      v   gt  gt  8        define SH16 v    v      v   gt  gt  16        define OP v   SH16 SH8 SH4 SH2 SH1 v                      define CB0 v      v  -    v   gt  gt  1   amp  0x55555555        define CB1 v       v   amp  0x33333333       v   gt  gt  2   amp  0x33333333        define CB2 v        v      v   gt  gt  4   amp  0xF0F0F0F    0x1010101   gt  gt  24       define CBSET v   CB2 CB1 CB0  v           define FLOG2 v   CBSET OP v      Test code below    include  lt iostream gt   using namespace std      http   graphics stanford edu  seander bithacks html IntegerLogObvious  define SH1 v     v-1      v-1   gt  gt  1       accidently guess this     define SH2 v     v      v   gt  gt  2    define SH4 v     v      v   gt  gt  4    define SH8 v     v      v   gt  gt  8    define SH16 v    v      v   gt  gt  16    define OP v   SH16 SH8 SH4 SH2 SH1 v                  define CB0 v      v  -    v   gt  gt  1   amp  0x55555555    define CB1 v       v   amp  0x33333333       v   gt  gt  2   amp  0x33333333    define CB2 v        v      v   gt  gt  4   amp  0xF0F0F0F    0x1010101   gt  gt  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  lt  lt  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       Outputs   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

User · Answer

If you need it for OpenGL related stuff      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  gt  gt   1  i    2

[c] Rounding up to next power of 2

Examples related to c

Examples related to optimization

Examples related to bit-manipulation