Im learning BIT (Fenwick tree), i saw a expression that is x & -x to find largest power of two don't larger than x.
But i can't clear this expression, please tell me the truth. Thank you very much!
I searched google and don't have any more knowledge that it is a trick.
I asked GPT but it have just give example but don't proof. I've just known that this expression is a trick :'( and no more.
And more, could you give me some bitwise-research-documents? I hope that learn more about bitwise, thank you.
search in google how the negative numbers are represented in binary
It's not just the largest power of two not larger than $$$x$$$. It is about getting the $$$2 ^ {(least\ significant\ bit)}$$$.
If $$$x$$$ in binary is $$$11110$$$, then $$$x & -x$$$ will return a number whose binary representation is $$$10$$$. You can also interpret it as "isolating the rightmost set bit".
I assume that you are familiar with 2's complement (how negative numbers are represented in binary)
$$$-x = $$$ ~$$$x + 1$$$ where ~$$$x$$$ is 1's complement, i.e. just flipping all bits.
So, $$$x & -x = x & (~x + 1)$$$.
You can consider ~$$$x = 0001010 1111$$$ and try it out yourself too.
If I add $$$1$$$ to ~$$$x$$$ then all consecutive $$$1$$$ will get converted to $$$0$$$ and a carry of $$$1$$$ will be propogated further, until you find a $$$0$$$, which will not allow carry to propogate any further, and thus you will set the rightmost bit in ~$$$x$$$ to $$$1$$$. So,
If you see carefully this is also the rightmost setbit of $$$x$$$, (since ~$$$x$$$ and $$$x$$$ have all bits different and carry is not getting propogated any further so no more bit to the left will change. Now if you do $$$x & (~x + 1)$$$, except for the one bit which was flipped, every other bit will be $$$0$$$. Why? Because all bits towards the right of "the bit we just set" is $$$0$$$, and all bits to its left will be different than $$$x$$$, because $$$x$$$ and ~$$$x$$$ have all different bits and those leftward bits aren't changed when we added $$$1$$$.
UPD: Some Bitwise hacks: https://catonmat.net/low-level-bit-hacks
So, in most modern systems, negative numbers are represented in computer using complement
So, you know that $$$x + (-x)$$$ should be the size of what you can represent.
For simplicity, I will from now on think about standard int, what would make $$$x + (-x) = 2^{32}$$$. Note that I'm just taking the values of binary representation and adding them as natural numbers in maths, not the way computer would (computer would mod them with $$$2^{32}$$$ and got 0 you expect).
So, let $$$i$$$ be the smallest set bit in $$$x$$$. E.g. in number 12 = 1100, that would be 3 (because there is 1 on 3rd place from right, and 1st and 2nd place are 0). That means that x is divisible by $$$2^{i-1}$$$, but not with $$$2^i$$$.
Now lets use our observation that $$$x + (-x) = 2^{32}$$$. Using simple modular maths, we can look at the equation modulo $$$2^{i-1}$$$ to get that $$$-x$$$ is also divisible, therefore first $$$i-1$$$ digits in binary representation of $$$x-1$$$ are also 0. Looking at equation modulo $$$2^i$$$ give that $$$-x$$$ is also not divisible, so $$$i$$$th bit is set to 1. So, $$$x$$$ and $$$-x$$$ have the same representation until the $$$i$$$th bit. Furthermore, that same representation is exactly equal to the biggest power of 2 that divides $$$x$$$ (or $$$-x$$$ since it is the same). So, we now just need to prove that non of digits in the rest of representation match up.
This can be simply done with going back to $$$x + (-x) = 2^{32}$$$. Look at "carry-over" of addition when you look at binary representations of numbers — because of carry-over from the $$$i$$$th place, every later bit is set in exactly one of $$$x$$$ or $$$-x$$$. If you need more help, I can write it out, but simple example on exact numbers should do the trick. To prove it, find a contradiction if that is not the case (you will find some set bit in representation of $$$2^{32}$$$).
So... first part of representations that matches up — it is exactly $$$2^{i-1}$$$ what is the largest power of 2 that divides $$$x$$$. And for the second part, one will have 0 and other one will have 1 at any bit. So, since $$$0&1=0$$$, this part will not contribute to binary AND of numbers.
So that is the proof. Feel free to ask more questions if needed! :)
thanks all, i got it