### ivplay's blog

By ivplay, history, 20 months ago, 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.  Comments (3)
 » 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-indexedYou can check out my blog if this isn't clear.
 » First lets proof idx + (idx&-idx) covers idxidx&-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 > xso, idx+P-2^z < idx+P-2^x=> idx+P-2^z < idxso 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^xit's obvious that y < x where y is the lowest significant bit of Qsince 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^yHence, idx + Q-2^y >= idxSo 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.
•  » » btw if i can add to this , the BIT property/objective is if the least significant bit of i in binary is x, tree[i] will contain cumulative result of (i-2^x+1)th to ith elementfor example for i=20 , binary(20) = 10100 . so tree will contain cumulative result of decimal(10000)+1 to decimal(10100) => 17th to 20th element