Alex Rivera | Logout

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

Asked 2013-02-11T13:30:06.330
11

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?

c
Edit
Report

1 Answer

20

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

answered 2013-02-11T13:39:25.393

Your Answer