# Formula for given Input-Output Set

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))

• @Useless check the edit Commented Feb 6, 2018 at 14:20
• Is the output for $2$ and $3$ is $4 \cdot 2^3$ or $4 \cdot 2^2$? Commented Feb 6, 2018 at 14:21
• @JaideepKhare return 2 when the input is 1 Commented Feb 6, 2018 at 14:22

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

• That's it thanks ! Commented Feb 6, 2018 at 15:31

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);