n&(n-1) 与 n&-n

时间:2020-11-26 22:38:31

n&(n-1)作用:可将n的二进制表示中的最低位为1的改为0(也就是说去掉最后一个1)

n&(n-1)应用:

1.判断一个非0数是不是2的次方:n&(n-1)==0

2.求某个数二进制表示中1的个数:

while (n >0 ) {
      count ++;
      n &= (n-1);
}

3.计算n!的质因数2的个数:n-(n的二进制表示中1的个数)


n&-n作用:保留二进制表示中的最后一个1

n&-n应用:

求能被2的次方整除的最大数,如:

96/32(2^5)==3,所以96&-96==32;   

19/1(2^0)==19,所以19&-19==1;