位运算

• 1. 判断奇偶
• 2. 两数交换
• 3. 2的n次方
• 4. 找出不大于N的最大的2的幂指数

1. 判断奇偶

if((n & 1) == 1){
    // n 是个奇数。
}

只需要判断n的二进制的最后一位即可。

2. 两数交换

x = x ^ y //（1）
y = x ^ y //（2）
x = x ^ y //（3）

不使用辅助变量完成交换。

• 两个相同的数异或之后是0：n ^ n = 0

• 任何数与0异或等于其本身：n ^ 0 = n

• 异或运算支持运算的交换律和结合律

推导：

把（1）中的 x 带入 （2）中的 x，有

y = x^y = (x^y)^y = x^(y^y) = x^0 = x。 x 的值成功赋给了 y。

对于（3）,推导如下：

x = x^y = (x^y)^x = (x^x)^y = 0^y = y。

3. 2的n次方

int pow(int n){
    int sum = 1;
    int tmp = 2; //存储下一位的2的次方数
    while(n != 0){
        if((n & 1) == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }

    return sum;
}

例如 n = 13，则 n 的二进制表示为 1101, 那么 2 的 13 次方可以拆解为:

2¹¹⁰¹ = 2⁰⁰⁰¹ * 2⁰¹⁰⁰ * 2¹⁰⁰⁰。

我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。

4. 找出不大于N的最大的2的幂指数

int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    // return (n + 1) >> 1;
    return (n >> 1) + 1;
}

把二进制中最左边的 1 保留，后面的 1 全部变为 0，此数即是不大于N的最大的2的幂指数。

推导：

1. 找到最左边的 1，然后把它右边的所有 0 变成 1
2. 右移一位再加 1 即可得到