6

I found that many people use x += x & (-x), x -= x & (-x) to solve the interval tree problem (While implementing data structures like segment tree, binary indexed tree etc).

Can you explain what that equation means?

For Example:

void update(int m, int x) { 
    m++;
    while (m < N) {
        t[m] = t[m] + x;
        m += m & -m;
    }
}

int query(int m) { 
    int result= 0;
    m++;
    while (m > 0) {
        result = result + t[m];
        m -= m & -m;
    }
    return result;
}
Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
eleven22
  • 83
  • 2
  • 7
  • This is some bitwise trick, but I'm too bored to work it out myself. You should be able to figure it out simply by trying to test various values of `m` and seeing what you get as a result, repeating with different values of `m` until you see a pattern. – Sam Varshavchik Nov 22 '19 at 13:22
  • Do you know how an `int` is represented in binary? What's the difference between the representations of `m` and `-m`? The `&` results in only having the 1-bits that both of them have. – n314159 Nov 22 '19 at 13:28
  • I know each of `m`, `-m`, and `&`, but I don't know What I can get from the equation. As @SamVarshavchik says, I think I should try various test cases. Thanks everyone! – eleven22 Nov 22 '19 at 13:53
  • duplicates: [Why is `i & (i ^ (i - 1))` equivalent to `i & (-i)`](https://stackoverflow.com/q/24772669/995714), [What does `number & -number` mean in bit programming?](https://stackoverflow.com/q/35861228/995714), [What does `i+=(i&-i)` do? Is it portable?](https://stackoverflow.com/q/51415536/995714), [what is the meaning of `k-=(k & (-k))`?](https://stackoverflow.com/q/49352148/995714) – phuclv Dec 05 '22 at 15:44
  • Does this answer your question? [What does i+=(i&-i) do? Is it portable?](https://stackoverflow.com/questions/51415536/what-does-i-i-i-do-is-it-portable) – phuclv Dec 05 '22 at 15:44

4 Answers4

13

Note: This answer (like the method itself) assumes signed integers are represented in two's complement form.

The expression x & -x is a quick - but admittedly arcane - way of getting the value represented by the lowest set bit in x (when all other bits are clear). This is sometimes known as the weight of the bit, and is numerically equal to 2 raised to the power of the bit's position (where the least significant bit is position 0).

The method relies on the fact that there can only be a single bit that is set in the binary (2s-comp) representations of both x and -x - and this will actually be the least significant set bit in x.

There are some good explanations of how this works, with many examples, here on Quora.

In the update and query functions you show, the amount by which to increase/decrease m in the while loops is thus weighted according to the position of the least significant set bit in the (original) m.

Feel free to ask for further clarification and/or explanation (but I don't wish to copy/paste or paraphrase too much of the discussion I've linked).

Adrian Mole
  • 49,934
  • 160
  • 51
  • 83
  • https://catonmat.net/low-level-bit-hacks is a nice article about bithacks, especially ones involving +1 or -1 to flip a range of contiguous 1s or 0s at the bottom of a register. It starts from basics of bitwise operators themselves and has nice 8-bit binary examples. – Peter Cordes Dec 05 '22 at 14:37
5

Another way of interpreting it can be as follows:

Let X be a number. Then X&-X represents the greatest power of 2 that divides X.

Examples:

  1. Let X = 10, then X&-X will give 2.
  2. Let X = 7, then X&-X will give 1.
  3. Let X = 4, then X&-X will give 4.
sudhanshu.3
  • 51
  • 1
  • 4
4

As @Adrian has already given an excellent answer about what the expression means I'll just complement it with a simple example on how it works.

Let's consider that our x is a 4-bit number(for simplicity) 1100b. Then,

  1. x is 0000 1100b (its lowest set bit is at position 2 (index starts from left at 0)
  2. -x is 1111 0100b as 0000 1100b + 1111 0100b = 0b
  3. -x & x results in 0100b. The only set bit is at the same position as the rightmost bit in x - at position 2.
Anatolii
  • 14,139
  • 4
  • 35
  • 65
3

In Binary Indexed Tree (Fenwick_tree) these operations are updating and querying the Tree. To query the Tree you are finding the parent of an element by resetting it's rightmost set bit. To update the Tree you keep adding least significant bit to the current index to find all the elements to update.

Lyudmila
  • 81
  • 2