Write a C function that round up a number to next power of 2

Question

I got the following question in an interview: "Write a C function that round up a number to next power of 2."

I wrote the following answer:

#include <stdio.h>

int next_pwr_of_2(int num)
{
    int tmp;

    do
    {
        num++;
        tmp=num-1;
    }
    while (tmp & num != 0);

    return num;
}

void main()
{
    int num=9;
    int next_pwr;
    next_pwr=next_pwr_of_2(num);
    printf(" %d \n",next_pwr);
}

The question is: why does the program go out of its do-while loop when getting to the values 11 and 10?

Answer 1

The loop exits because you did not put parentheses around your condition. This should teach you not to put the unnecessary != 0 in your C/C++ conditions.

You can simplify your code quite a bit, though.

First, observe that temp equals the prior value of num, so you can change your loop to

int tmp;
do {
    tmp = mum++;
} while (tmp & num); // Don't put unnecessary "!= 0"

Second, the interviewer was probably looking to see if you are familiar with this little trick:

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

Unlike your code that may take up to 1,000,000,000 operations to complete, the above always completes after twelve operations (a decrement, an increment, five shifts, and five ORs).

Answer 2

Precedence my friend, precedence.

while ((tmp & num) != 0);

Will fix it. ( note the parenthesis around the expression tmp & num)

!= has higher precedence than &, so num != 0 is evaluated before tmp & num.

If you skip the parenthesis, the expression that is evaluated is : tmp & (num != 0)

1. First time round, tmp = 9 (1001) and num != 0 is 1 (0001) so & evaluates to 1 (true), and the loop continues.

2. Now at the end of second iteration, we have, tmp = 10 (1010). num != 0 is again 0001, so 1010 & 0001 evaluates to 0, hence the loop breaks.

Here is the table for reference.

The precedence order is quite unusual, as noted here. Happens all the time :).

Of course you don't have to remember any precedence order, which is just to help the compiler in deciding what is done first if the programmer does not make it clear. You can just correctly parenthesize the expression and avoid such situations.