常用算法整理
...
此处记录常用的算法,可以用在平时的解题中,提高解题效率。
判断奇数偶数
判断n & 1
的结果,如果是1,则n是奇数,否则是偶数。
0和1交替替换
int i = 0;
i ^= 1;
应用:
常用在部分奇偶变化、boolean类型的标志位持续变化的题目中。持续调用时,i会在0和1之间不断切换。
消除二进制表示中最后一个1
n = n & (n - 1)
如,n
为 1001101
时,n - 1 = 1001100
,二者相与赋值给n,结果为 1001100
,最后一位的1被去掉了。
再次计算,n-1 = 100101
1,二者相与,结果为 1001000
,最后一位的1被去掉了。
应用:
剑指 Offer 15. 二进制中1的个数:n不为0时持续进行上述计算,每计算一次sum+1。循环结束后,sum的值就是要求的结果。
JDK中的实现,时间复杂度 `O(1)`
// java.lang.Integer#bitCount
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
你认为这篇文章怎么样?
- 0很棒
- 0不错
- 0一般
- 0???