文章目录
  1. 1. Round up to the next power of two
  2. 2. Is power of two
  3. 3. Wap two number

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

Many thanks to STEPHAN BRUMME

Round up to the next power of two

将一个数向上对齐到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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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之后再移位。

Is power of two

判断一个数是否是2的幂

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

算法原理

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

Wap two number

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

文章目录
  1. 1. Round up to the next power of two
  2. 2. Is power of two
  3. 3. Wap two number