判奇偶

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;
}