This article is from http://bits.stephan-brumme.com/

Many thanks to STEPHAN BRUMME

将一个数向上对齐到2的幂

例如

  3  对齐后为 $2^2$ = 4
  5  对齐后为 $2^3$ = 8     
  10 对齐后为 $2^4$ = 16

I get the code from the pipe project of Clark Gaebel cg.wowus.cg@gmail.com Thanks to Clark Gaebel

size_t next_pow2(size_t n)
{
    assert(n != 0);

    size_t top = (~(size_t)0 >> 1) + 1;

    if (n >= top)
        return n;

    n--;

    for(size_t shift = 1; shift < (sizeof n)*8; shift <<= 1)
        n |= n >> shift;

    n++;

    return n;
}

top表示size_t能表示的2的幂的最大值

算法原理

除0之外的每一个数, 用二进制表示，至少有一个bit是1, 
假设对于n, 只考虑为1的最高bit位, 如果将它右边的所有比特设为1, 那么得到的结果加1就是下一个2的幂。
步骤1: 00...001...  ->  00...001111
步骤2：加1  -> 00...010000

实现步骤1的方式:
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    ...
考虑到n本来就已经是2的幂的情况，所以需要先将n减1之后再移位。

判断一个数是否是2的幂

bool isPowerOfTwo(unsigned int x)
{
  return ((x & (x - 1)) == 0);
}

算法原理

2的幂的特征: 二进制表示中只有一个1, 1右边全部为0, 所以x如果为2的幂， 那么x & (x -1) 一定为0

void swapXor(int *a, int *b) {

• a ^= *b;
• b ^= *a;
• a ^= *b;

}

算法原理:

  使用异或的方式，不使用中间变量，交换两个数的值。
  0 XOR 0  -> 0
  0 XOR 1  -> 1
  1 XOR 0  -> 1
  1 XOR 1  -> 0
  相同的bit进行异或，结果为0, 与零异或，结果保持不变  
  a_new     = a XOR b
  b_swapped = b XOR a_new = b XOR (a XOR b) = a XOR (b XOR b) = a
  a_swapped = a_new XOR b_swapped = (a XOR b) XOR a = b