Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What does "x += x & (-x)" mean?

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;
}
like image 462
eleven22 Avatar asked Nov 22 '19 13:11

eleven22


3 Answers

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).

like image 182
Adrian Mole Avatar answered Oct 22 '22 00:10

Adrian Mole


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.
like image 34
Anatolii Avatar answered Oct 22 '22 00:10

Anatolii


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.
like image 23
sudhanshu.3 Avatar answered Oct 21 '22 22:10

sudhanshu.3