ivplay's blog

By ivplay, history, 5 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.