关于位操作的奇淫技巧

Determining if an integer is a power of 2

unsigned int v; // we want to see if v is a power of 2 bool f; // the result goes here

f = (v & (v - 1)) == 0;

Note that 0 is incorrectly considered a power of 2 here. To remedy this, use:

f = v && !(v & (v - 1));

这里用到了一个很常用的技巧,2的乘方必然是以这个形式出现: 最高一位为1后面的位全部为0. v-1就是那个最高位变成了0,其余全为1. 这就好像10进制里1000和999的关系一样. 反之关系也一样成立.

Refrence

Stanford大学一个家伙写的Bit Twiddling Hacks