0
$\begingroup$

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))
$\endgroup$
3
  • $\begingroup$ @Useless check the edit $\endgroup$ Commented Feb 6, 2018 at 14:20
  • $\begingroup$ Is the output for $2$ and $3$ is $4 \cdot 2^3$ or $4 \cdot 2^2$? $\endgroup$ Commented Feb 6, 2018 at 14:21
  • $\begingroup$ @JaideepKhare return 2 when the input is 1 $\endgroup$ Commented Feb 6, 2018 at 14:22

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ That's it thanks ! $\endgroup$ Commented Feb 6, 2018 at 15:31
0
$\begingroup$

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);
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .