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;
}
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).
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,
x
is 0000 1100b
(its lowest set bit is at position 2
(index starts from left at 0
)-x
is 1111 0100b
as 0000 1100b + 1111 0100b = 0b
-x & x
results in 0100b
. The only set bit is at the same position as the rightmost bit in x
- at position 2
. 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:
X = 10
, then X&-X
will give 2
.X = 7
, then X&-X
will give 1
.X = 4
, then X&-X
will give 4
.If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With