0
$\begingroup$

I am trying to prove that $$\left\lfloor{\frac{i}{2^h}}\right\rfloor$$ equals to performing a series of $h$ operations of $$\left\lfloor\frac{\left\lfloor\frac{\left\lfloor\frac{i}{2}\right\rfloor}{2}\right\rfloor}{2}\right\rfloor $$ etc...

I am using this property as part of a larger proof for an algorithm and this property is all I need... any help?

$\endgroup$
  • $\begingroup$ Both correspond to truncating the bottom $h$ digits of the binary expansion of the number. $\endgroup$ – jgon Dec 15 '18 at 18:22
  • $\begingroup$ Thank! any idea how i can formally/mathematically prove it? @jgon $\endgroup$ – Limitless Dec 15 '18 at 18:33
  • $\begingroup$ Yes, I would first prove that dividing by $2^n$ and taking the floor deletes the last $n$ bits of the number, and then prove by induction that therefore since the operation divide by two and then take the floor deletes the least significant bit of the number, iterating that operation $n$ times deletes the last $n$ bits of the number. $\endgroup$ – jgon Dec 15 '18 at 18:53
0
$\begingroup$

Hint: You can show that it is true if $i < 2^h$ easily. In both cases, the evaluation is $0$.

After that, you can prove it easily for $2^h$. Both are equal to $1$ as in the second case each time we have a power of $2$ and the result is integer each time.

For the last case $i > 2^h$. Hence, we can write it likes $i = 2^n + k$ whcih $n \geq h$ and $k < 2^h$. First case is $2^{n-h}$. we can prove for the second case easily by induction over $n$ with base of $n = h$.

$\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.