使用，並與數

的否定我的地方閱讀這條線，我無法弄清楚它的使用使用，並與數

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

使用，並與數

回答

相關問題