在日常编码中有一些非常常用，但却很细节的小技巧，虽然有朴素的实现的方式，但如果能掌握一些高级技巧不但性能会更好，并且因为技巧比较流行，也不会影响可读性。最简单的例子就是除2和乘2，当然可以直接用乘法和除法，但如果用移位效果更好，也并不影响可读性，因为这是比较流行的做法。

这里就将总结一些常用的小技巧，以供日后查阅。

整数相关技巧

判断奇偶

1
2
3
4
5
6
7
8
9
10
11
12

// 1. 朴素做法
if (n % 2 == 0) {
   // even
} else {
    // odd
}
// 2. 用移位
if ((n & 0x01) == 0) {
   // even
} else {
  // odd
}

乘2

1
2

// 左移1位，相当于乘2
n <<= 1;

除2

1
2

// 右移1位，相当于除2
n >>= 1

求2的k次幂

1
2
3
4

// 朴素做法
a = (int) Math.pow(2, k);
// 1左移k次，就是2的k次幂
a = 1 << k;

有符号和无符号的右移

常规右移是有符号的，它不会动最高位的符号位。而如果要实现『无符号』式右移，需要使用逻辑右移符>>>。

取数位

与1与取，能获取某个数位bit，这就像印章一样，把bit印在提供的1上面，检查 结果如果是1，说明bit是1，如果是0，说明bit是0。

放数位

用0取或，可以放数位，就像印刷中的拓写一样，给源数位刷上颜色，可以把其复制到白布上面(0上面）。

异或

一个数异或它自己结果会是0.

一个数异或0等于它自己，a ^ 0 = a。

异或操作满足交换律和结合律：

a ^ b = b ^ a

a ^ (b ^ c) = (a ^ b) ^ c

典型问题

不要重复造轮子

虽然刷题中尝尝遇到位运算的问题，但其实API中有大量写好的方法供我们调用，不可浪费，实际工作中，应该优先使用API。

边界

二分查找中间防溢出

二分查找通常要计算区间的中间，比如这样：

1
2
3
4
5

int left = 1;
int right = n;
while (left < right) {
    int mid = (left + right) >> 1;
}

但这样计算有问题，当区间特别大时，比如超过了最大整数的一半时，那么用相加来计算就会整数溢出，从而出问题。更好的做法是用减法：

1

int mid = left + ((right - left) >> 1);

另外，这里的括号都是必要的，虽然移位运算符的优先级高，但是当right与left相等时，如果后半部分不加括号还是会出错。

索引相关

数组/列表索引区间个数

对于数组或者列表来说，如果给定一个闭区间索引，如[i,j]，那么它的元素个数（长度）是len=j - i + 1。

数组/列表索引区间子数组个数

有时候是求区间的子数组个数，单个元素也算一个子数组。比如区间[i,j]的子数组个数。子数组的长度可以从1到len，当L=len时，个数 为1，当L=1时个数为len，所以这是一个等差数列，和为S=(len + 1) x len / 2。

数组/列表索引区间定长子数组个数

给定区间，比如[i,j]，再给定子数组长度比如L，那么子数组个数是，这就相当于长度为L在区间内滑动，如果区间长度len < L，为0，否则子数组个数为len-L+1。

参考资料

• 位运算有什么奇技淫巧？
• 优秀程序员不得不知道的20个位运算技巧
• 【算法】位运算技巧
• 位运算的奇“赢”技巧
• 10 cool bitwise operator hacks and tricks every programmer must know
• Bitwise Hacks for Competitive Programming
• Bit Manipulation Tips and Tricks You Should Know