What is the proof that from any index idx , idx + (idx&-idx) is the next closest index that covers idx? I mean how can I prove that no other index in range ( idx,idx+(idx&-idx) ) actually covers idx? '(' means exclusive and covers idx means contains information of idx ??
Thanks in advance.
Its because the (x & -x) gets you the least significant bit of x.
let a=[A]10...00, then (thanks to 2-complements) -a = [A inverted]01...11 + 1 or [A inverted]10...00. Bitwise ANDing the two gets 000010...000, or the lsb of a.
For the covering, its because the length of the interval corresponding to x is equal to 2^(lsb) 1-indexed
You can check out my blog if this isn't clear.
First lets proof idx + (idx&-idx) covers idx
idx&-idx = 2^x = P (let), where x is the lowest significant bit of idx.
according to binary addtion 1 + 1 = 0 and we carry a 1 to right.
so if z is the lsb of idx + P then z > x
so, idx+P-2^z < idx+P-2^x
=> idx+P-2^z < idx
so idx+P covers idx.
now lets proof P is lowest such amount that we need to add with idx to get the number that covers idx.
If P is not the lowest such amount then let Q < P and idx + Q covers idx.
since Q < P and P = 2^x
it's obvious that y < x where y is the lowest significant bit of Q
since x is the lsb of idx and y is lsb of Q and y < x then of course y is the lsb of idx+Q (binary addtion, 1 + 0 = 1 )
As y is the lsb of Q so, Q >= 2^y
Hence, idx + Q-2^y >= idx
So idx+Q does not cover idx according to BIT property.
Proof by contradiction, P = idx&-idx = 2^lsb_of_idx is the lowest amount we have to add to get the number that covers idx.