使用和否定数字

Question

我在某处读到这一行，但我不知道它的用途

private void bitUpdate(int[] bit, int idx, int val) {
        while (idx < bit.length) {
            bit[idx] += val;
            if (bit[idx] >= MOD)
                                bit[idx] -= MOD;
            idx += (idx & -idx);
    }
}

idx 最初是 1

bit[100100]={0,0,0,0,0,0,0,0,0,0.......}

val=1

MOD = 1000000007

我想不通这条线的用途

idx += (idx & -idx);

它将 idx 添加到数字的 and 及其否定中，我们用 and -ing 自身及其否定实现了什么？

Answer 1

idx & -idx 是 "bit twiddling"，实际上由 Java 运行时库使用。

方法 Integer.lowestOneBit(int i) 实现为 return i & -i;，评论说它来自 Henry S. Warren, Jr 的 Hacker's Delight 的第 2-1 节.（艾迪生韦斯利，2002 年）。

该方法的 javadoc 说：

Returns an int value with at most a single one-bit, in the position of the lowest-order ("rightmost") one-bit in the specified int value. Returns zero if the specified value has no one-bits in its two's complement binary representation, that is, if it is equal to zero.

因此，如果 idx 最初为 1，则 lowestOneBit() 是未更改的值，并且将其重复添加到自身与：

相同

idx <<= 1;

然而，只有当初始数字恰好设置了一位时，这才是正确的。

如果初始数字设置了多个位，则级数不同，例如如果 idx 最初是 52428:

idx                idx & -idx
                                         1100110011001100 =  52428
1100110011001100 + 0000000000000100 =    1100110011010000 =  52432
1100110011010000 + 0000000000010000 =    1100110011100000 =  52448
1100110011100000 + 0000000000100000 =    1100110100000000 =  52480
1100110100000000 + 0000000100000000 =    1100111000000000 =  52736
1100111000000000 + 0000001000000000 =    1101000000000000 =  53248
1101000000000000 + 0001000000000000 =    1110000000000000 =  57344
1110000000000000 + 0010000000000000 =   10000000000000000 =  65536
    then  <<= 1  from here             100000000000000000 = 131072
                                      1000000000000000000 = 262144

为了确认，你可以看到上面的代码是这样的：

int idx = 52428;
while (idx <= 0x40000) {
    String bits1 = Integer.toBinaryString(idx);
    String bits2 = Integer.toBinaryString(idx & -idx);
    idx += (idx & -idx);
    String bits3 = Integer.toBinaryString(idx);
    System.out.printf("%20s + %20s = %20s = %6d%n", bits1, bits2, bits3, idx);
}

    1100110011001100 +                  100 =     1100110011010000 =  52432
    1100110011010000 +                10000 =     1100110011100000 =  52448
    1100110011100000 +               100000 =     1100110100000000 =  52480
    1100110100000000 +            100000000 =     1100111000000000 =  52736
    1100111000000000 +           1000000000 =     1101000000000000 =  53248
    1101000000000000 +        1000000000000 =     1110000000000000 =  57344
    1110000000000000 +       10000000000000 =    10000000000000000 =  65536
   10000000000000000 +    10000000000000000 =   100000000000000000 = 131072
  100000000000000000 +   100000000000000000 =  1000000000000000000 = 262144
 1000000000000000000 +  1000000000000000000 = 10000000000000000000 = 524288

Answer 2

让我们从头开始使用 idx=1 的值来理解表达式 (idx & -idx) 的作用。

8位二进制表示： 1 = 00000001, -1 = 11111111

现在，使用 & 运算符，1 & -1 得到 1。因此，idx 在 idx+= (idx & -idx);

中增加到 2

 2  = 00000010, 
-2 = 11111110

和 2 & -2 给出 2。因此，idx 增加到 4。

4  = 00000100, 
-4 = 11111100

和 4 & -4 给出 4。现在，idx 增加到 8。

同上，(idx & -idx) = idx.

使用和否定数字

Use of and with negation of the number

java

bit-manipulation

bit