Java中n&(n-1)和n&(-n)

发表于
字数统计 352 | 阅读时长 1

n&(n-1)

作用

将n的二进制表示中的最低位为1的改为0。

举例：

n = 10100(二进制），则(n-1) = 10011 ==》n&(n-1) = 10000，可见n中从右数第一个1变为了0。

使用场景

  • 求某一个数的二进制表示中1的个数

    1
    2
    3
    4
    while (n ！= 0) {
    	count ++;
    	n &= (n-1);
    }

  • 判断一个数是否是2的方幂

    1
    n > 0 && ((n & (n - 1)) == 0 )  // 若为2的某次方幂，则其二进制表示中只有一个1

  • 计算N!的质因数2的个数

    N!的质因数2的个数为N - (N二进制表示中1的个数)，简单推理：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    N = 10101(二进制表示）
    现在我们跟踪最高位的1，不考虑其他位假定为0，
    则在
    [N / 2] 01000
    [N / 4] 00100
    [N / 8] 00010
    [N / 16] 00001
    则所有相加等于01111 = 10000 - 1
    由此推及其他位可得：(10101)!的质因数2的个数为10000 - 1 + 00100 - 1 + 00001 - 1 = 10101 - 3(二进制表示中1的个数)

n&(-n)

作用

获得从右数第一个1的位置。

使用场景

一个数的因子中形如2^k的数为多少，例如：

1
2
3
4
5
6
7
10: 0000 1010

-10: 1111 0110

10&(-10)为 0010 = 2 所以10的因子中为2的有一个，2^k的形式的为 2^1

8&(-8) = [1000] = 8 所以8的因子中为2的有3个，2^k的形式为2^3

注：转载文章请注明出处，谢谢~