取得下一个2的幂
我想写一个函数返回最接近的下一个2的数字的幂。 例如，如果我的input是789，输出应该是1024.有什么办法实现这一点，而不使用任何循环，只是使用一些按位运算符？
检查一下Bit Twiddling Hacks 。 你需要得到基数2的对数，然后加1。
取整到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++;
next = pow(2, ceil(log(x)/log(2)));
这个工作是通过find你想要得到的数字来得到x（把数字logging下来，然后除以所需基数的logging， 详见维基百科 ）。 然后用ceil来取得最接近的整数次方。
这是一个更通用的方法（比较慢！）的方法比其他地方连接的按位方法，但很好的知道math，呃？
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; }
我认为这也是有效的：
int power = 1; while(power < x) power*=2;
答案就是power 。
如果您使用的是GCC，您可能需要查看Lockless Inc的优化next_pow2（）函数 。本页描述了一种使用内置函数builtin_clz() （计数前导零）的方法，稍后直接使用x86 （ia32）汇编程序指令bsr （位扫描反向），就像在另一个答案的gamedev网站的链接中所述 。 这个代码可能比以前的答案中描述的要快。
顺便说一句，如果你不打算使用汇编指令和64位数据types，你可以使用这个
/** * 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)); }
另外，虽然我使用循环，但是比math操作数快得多
两个“楼层”选项的力量：
int power = 1; while (x >>= 1) power <<= 1;
两个“细胞”选项的力量：
int power = 2; while (x >>= 1) power <<= 1;
对于任何未签名的types，build立在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; }
因为编译器在编译时知道迭代次数，所以没有真正的循环。
对于IEEE浮点数，你可以做这样的事情。
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)); }
如果你需要一个整数解决scheme，并且你可以使用内联汇编，BSR会给你在x86上的一个整数的log2。 它计数有多less个右位被设置，这正好等于那个数的log2。 其他处理器也有相似的指令（通常是），比如CLZ，根据你的编译器的不同，可能有一个内在的可用来为你做的工作。
/* ** 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 }
如果你不想冒险进入未定义行为的领域，input值必须在1和2 ^ 63之间。 macros在编译时设置常量也很有用。
为了完整起见，这里是一个浮点标准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); }
许多处理器架构支持log base 2或非常相似的操作 – count leading zeros 。 许多编译器都有内在的东西。 请参阅https://en.wikipedia.org/wiki/Find_first_set
在x86中，您可以使用sse4位操作指令使其更快。
//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
在c中，您可以使用匹配的内在函数。
假设你有一个好的编译器，并且可以在这个位置之前做一些事情，但是无论如何，这是有效的！
// 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)))
testing代码如下：
#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); }
输出：
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
我试图得到最接近的2的低功率，并做出这个function。 可以帮助你。只要乘以最接近的较低的数字乘以2就可以得到最接近的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; }
如果你需要它的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; } }
