1
$\begingroup$

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply such transformation the following method is applied:

1) Find 2's complement of the index.
2) AND the result of 1 with index.
3) Subtract the result from 2 with index.

If the following method is applied to 1010 then we get 1000 as the answer. Now I want to understand how to create such formulas? In Algebra we solve such type of problems by solving linear equations. How do we do it with Binary numbers to achieve such answers?

$\endgroup$
1
$\begingroup$

This is a one-off trick which is not part of a complete methodology. To see why the trick works, suppose that the index has the form $x10^m$. To calculate its two's complement, we first complement it to $\bar{x}01^m$, then add 1 to get $\bar{x}10^m$. ANDing the index and its two's complement, we get $0^{|x|}10^m$. Subtracting this from the index, we get $x0^{m+1}$, as needed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.