Why are these two floor sequences equal?

102 Views Asked by At

I want to convert from a base-10 integer number to its base-2 equivalent as has been shown in $\eqref{2}$. But after reviewing the MATLAB dec2bin function

>> d = 37;
>> [f,e]=log2(d)
f =
    0.5781
e =
     6
>> 1-e:0
ans =
    -5    -4    -3    -2    -1     0
>> pow2(1-e:0)
ans =
    0.0313    0.0625    0.1250    0.2500    0.5000    1.0000
>> d*pow2(1-e:0)
ans =
    1.1563    2.3125    4.6250    9.2500   18.5000   37.0000
>> floor(d*pow2(1-e:0))
ans =
     1     2     4     9    18    37
>> rem(floor(d*pow2(1-e:0)),2)
ans =
     1     0     0     1     0     1

I noticed that MATLAB uses $\eqref{1}$ instead of the traditional approach $\eqref{2}$.

My question is why

$$ x_1=\left\lfloor \frac{x}{2} \right\rfloor, x_2=\left\lfloor \frac{x}{4} \right\rfloor, x_3=\left\lfloor \frac{x}{8} \right\rfloor, \ldots, x_n=\left\lfloor \frac{x}{2^{n-1}} \right\rfloor \tag{1}\label{1} $$

and

$$ x_1=\left\lfloor \frac{x}{2} \right\rfloor, x_2=\left\lfloor \frac{x_1}{2} \right\rfloor, x_3=\left\lfloor \frac{x_2}{2} \right\rfloor, \ldots,x_n=\left\lfloor \frac{x_{n-1}}{2} \right\rfloor \tag{2}\label{2} $$

give the same results where $x$ is a positive integer number and $n = \left\lceil \log_2 x \right\rceil$?

For example for $x=37$ we have $n = \left\lceil \log_2 37 \right\rceil=6$. Then

$$ x_1=\left\lfloor \frac{37}{2} \right\rfloor=18, x_2=\left\lfloor \frac{37}{4} \right\rfloor=9, x_3=\left\lfloor \frac{37}{8} \right\rfloor=4, x_4=\left\lfloor \frac{37}{16} \right\rfloor=2, x_5=\left\lfloor \frac{37}{32} \right\rfloor=1 $$

and

$$ x_1=\left\lfloor \frac{37}{2} \right\rfloor=18, x_2=\left\lfloor \frac{18}{2} \right\rfloor=9, x_3=\left\lfloor \frac{9}{2} \right\rfloor=4, x_4=\left\lfloor \frac{4}{2} \right\rfloor=2, x_4=\left\lfloor \frac{2}{2} \right\rfloor=1 $$

1

There are 1 best solutions below

0
On

complete solution is $$n\in\mathbb{N}\\ x=⌊\frac{x}{n}⌋\\$$we know $$ k=⌊x⌋\rightarrow k\leq x <k+1$$so $$x=⌊\frac{x}{n}⌋\rightarrow x\leq \frac{x}{n}<x+1\\$$ $$nx \leq x <nx+n\\$$ $$nx \leq x \rightarrow x(n-1) \leq0 \rightarrow x=0,-1,-2,-3,...\\$$ $$ x <nx+n \rightarrow x(1-n)<n \rightarrow x>\frac{n}{1-n} \overset{n\neq 1}{\rightarrow} x>-2 \rightarrow x=-1,0,1,2,...\\$$so "x" just can be two value $$x=0,-1,-2,-3,...\\x=-1,0,1,2,...\\\rightarrow x=0,-1$$