Formula for given Input-Output Set

Question

Need to design an Algorithm, which should gave $\mathtt{[Output]}$ as per the $\mathtt{[Input]}$ mentioned below.

$\mathcal{Input}$	$\mathcal{Output}$
$0$	$1$
$1$	$2$
$2$	$4$
$3$	$4$
$4$	$8$
$5$	$8$
$6$	$8$
$7$	$8$
$8$	$16$
$9$	$16$
$10$	$16$
$11$	$16$
$12$	$16$
$13$	$16$
$14$	$16$
$15$	$16$

Can anyone help me in finding correct formula?

As a try, I prepared this Formula

$$\LARGE\boxed{2^{\lfloor\log_2(x)\rfloor}}$$

where $x$ is the input.

In Code

Math.pow(2, Math.floor(Math.log2(K))

Answer 1

Use this function $$f(0)=1 \quad;\;f(n)= 2^{\lfloor \log_2 n \rfloor+1} \; \text{if} ~ n \ge 1$$

Answer 2

If you are looking for computer code only dealing with integers, here is a bit of c++ based on bit operations:

// For simplicity, assume that the input 'n' is of type unsigned int.

unsigned int m = 1;
while (m <= n) m <<= 1; // could be written as m *= 2

return m;

Using this, you do not have to deal with floating point arithmetic and rounding errors. The while loop will run only $O(\log n)$ times.

If you do not want to use additional variables, then use this:

while (n != (n | (n >> 1))) n |= (n >> 1);
return (n + 1);