位运算一些常用的编程技巧总结

判奇偶

if( n % 2) == 01
    // n 是个奇数
}

等价

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

交换两个数

int tmp = x;
x = y;
y = tmp;

等价

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

这里解释一下，异或运算支持运算的交换律和结合律哦。

解释

实战

找出没有重复的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。

1.哈希表  o(n) o(n)

2.位运算 o(n) o(1)

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

m的n次方

求解 m 的 n 次方，不能使用系统自带的 pow 函数

1.常规做法，循环 o(n)

2.位运算 o(logn)

def pow(m,n):
    res = 1
    temp = m    
    while n:
        if n & 1 == 1:
            res *=temp
        temp *=temp
        n >>= 1
    return res

解释：例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:m^1101 = m^0001 * m^0100 * m^1000

可以看到13次方可以拆考成1，4，8次方相加。而对于任意一个次方都可以通过1，2，4，8...次方的组合得到

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

int findN(int N){
    int sum = 1;
   while(true){
        if(sum * 2 > N){
            return sum;
        }
        sum = sum * 2;
   }
}

int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
    return (n + 1) >> 1;
}