稀有猿诉

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

编码常见技巧总结

在日常编码中有一些非常常用,但却很细节的小技巧,虽然有朴素的实现的方式,但如果能掌握一些高级技巧不但性能会更好,并且因为技巧比较流行,也不会影响可读性。最简单的例子就是除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;

有符号和无符号的右移

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

异或

一个数异或它自己结果会是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一样

边界

二分查找中间防溢出

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

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相等时,如果后半部分不加括号还是会出错。

参考资料

Comments