blog:algorithms:bit_twiddling [LinuxToy]

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
#Bit operations algorithms

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 
```
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的幂

```
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