n&(n-1)的用途//转载
二进制中1的个数
https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&&tqId=11164&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
n&(n-1)的用途
最近做LeetCode上面的题目，发现很多题目都用到了n&(n-1)。感觉真是神通广大，下面就目前所看到的一些用途总结一下：
1，求一个int类型数是否为2的幂
n&(n-1)==0则表示该数为2的幂
2,一个数的二进制中有多少位为1
while（n>0）{
count++;
n = n&(n-1);
}
3，一个数是否为4的幂
一个数是4的幂，那么必然是2的幂，反之，则不然
那么首先确定条件n&（n-1）==0，确定出该数是否为2的幂，这就找到了一项必要条件
刚才说了一个数是2的幂却不一定是4的幂，比如2,8,32等这些都是2的级数次方
但是，我们可以发现，2的偶数次方，比如20=1,22=4,2^4=16,这些数减去1，都能被3整除，而2的奇数次方的数减去1之后无法被3整除，不信可以试试
这样的话，我们就可以很容易找到4的幂的充要条件，即 n>0 && ((n&(n-1))==0) && ((n-1)%3==0)
4,接下来还有一些可以用到符号&运算的例子，比如求一个数32位二进制的倒序
int result =0；
for（int i=0；i<32；i++）{
result<<=1;//result先左移一位，低位补0
result = result+(n&1)；
n>>=1;//n右移一位，高位补0
}
5，将一个数表示为16进制,并返回相应字符串
if(n==0) return "0";
String result =""；
String[] map={"0"，"1"，"2"，"3"，"4"，"5"，"6"，"7"，"8"，"9"，"a"，"b"，"c"，"d"，"e"，"f"};
while（n!=0）{
result = map[n&15]+result;
n>>=4;
}
作者：lenny611
链接：https://www.jianshu.com/p/1450e23ee2e7
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
