记录一些算法常用的
Tricks
,想起来的话会在这里补充。
一:位运算
-
n & (-n)
:取得最低位的1
所代表的值; -
n & (n - 1)
:把n
中最低位的1
抹掉; -
n & (n - 1) == 0 && n != 0
:检查n
是否为2
的幂;解释:因为
n & n-1
会把n
中最低位的1
抹掉,比如1100 & 1011 == 1000
把第二位上的1
给抹掉了。又因为2
的幂的二进制表示中只有一个1
,如1000
或0100
等,将这个唯一的1
抹除后数值就变为0
了。
在这里帮楼主补充一下,检查
n
是否为2^x
只有lowbit(n) == 0一个条件不够,还要满足n
不为0
啊对对,太细了,
0
确实不属于2
的幂。感谢