使用，并与数

的否定我的地方阅读这条线，我无法弄清楚它的使用使用，并与数

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到和数量与它的否定WH我们是否在与自己及其否定之间达成一致？

来源

2017-10-21 nothing1

我看不出它是什么。这段代码来自哪里？ –

https://www.codechef.com/viewsolution/15400915 – nothing1

来源== ^^^^^^^^^^^^^^^^^^^^^^^^^ – nothing1

idx & -idx是“位扭曲”，实际上由Java运行时库使用。

方法Integer.lowestOneBit(int i)实现为return i & -i;，有评论称这由亨利·沃伦，小（艾迪生韦斯利，2002）黑客的喜悦的2-1节的。

方法的Javadoc说：

返回一个int值与至多一个单个1位，在最低阶的位置在指定int（“最右边的”）的一比特值。如果指定的值在其二进制补码表示中没有一位，即等于零，则返回零。

所以，如果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

来源

2017-10-21 17:51:14 Andreas

让我们使用的idx=1值从一开始就明白什么表达(idx & -idx)呢。

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

现在，使用操作者&，1 & -1给出1。因此，idx在idx+= (idx & -idx);

2 = 00000010, 
-2 = 11111110

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

4 = 00000100, 
-4 = 11111100

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

按照上述，(idx & -idx) = idx。

来源

2017-10-21 18:07:15 Saurabh

使用，并与数

回答

相关问题