1

A function to calculate sum where I encountered with this statement ..plz help

 int get_sum(int x) {
     int p = 0, k;
     for (k = x; k > 0; k -= k & -k)
         p += bit[k];
     return p;
 }
JiaHao Xu
  • 2,452
  • 16
  • 31
Aritra Dutta
  • 105
  • 6
  • Where and how is `bit[]` declared - defined? – Francis Cugler Mar 19 '18 at 01:20
  • Where is `k` defined, and what type of `k` is? – Paul Mar 19 '18 at 01:24
  • 1
    sorry the more correct dupes are [meaning of (number) & (-number)](https://stackoverflow.com/q/12818978/995714), [how to understand `i & -i` in python?](https://stackoverflow.com/q/42192185/995714), [Why the bit operation i & (-i) equals to rightmost bit?](https://stackoverflow.com/q/41969429/995714), [Why is “i & (i ^ (i - 1))” equivalent to “i & (-i)”](https://stackoverflow.com/q/24772669/995714). Those can easily be found if you've googled for `"i & (-i)" site:stackoverflow.com` – phuclv Mar 19 '18 at 02:03

1 Answers1

4

This expression:

k -= (k & (-k))

Is a tricky way of taking the least significant bit that is set in a positive number and clearing that bit. It is dependent on two's compliment representation of negative numbers.

The first part, k & (-k) isolates the least significant bit that is set. For example:

1 & -1:

   00000001
 & 11111111
   --------
   00000001

2 & -2:

   00000010
 & 11111110
   --------
   00000010

24 & -24:

   00011000
 & 11101000
   --------
   00001000

When this value is subtracted from the orignal k, it clears that bit as a result.

So as the loop progresses, the value of k is reduced 1 bit at a time, starting with the lowest. So if for example x was 52, k would be 52, then 48 (52 - 4), then 32 (48 - 16), and would exit at 0 (32 - 32).

As to why the program is doing this, that depends entirely on the definition of bit and what it stores.

dbush
  • 205,898
  • 23
  • 218
  • 273