编码常见技巧总结

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

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

整数相关技巧

判断奇偶

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

乘2

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

除2

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

求2的k次幂

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

有符号和无符号的右移

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

异或

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

取数位

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

放数位

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

典型问题

题目	题解	说明
231. 2 的幂	题解
338. 比特位计数	题解
136. 只出现一次的数字	题解
461. 汉明距离	题解
191. 位1的个数	题解
190. 颠倒二进制位	题解
	题解

不要重复造轮子

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

API	说明
Integer.bitCount	返回1的个数，与题191一样
Integer.reverse	颠倒二进制bits，与题190一样

边界

二分查找中间防溢出

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

int left = 1;
int right = n;
while (left < right) {
    int mid = (left + right) >> 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。

稀有猿诉

十年磨一剑，历炼出锋芒，说话千百句，不如码二行。