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

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.

Answer 2

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 3

Such questions always deserve counter questions to clarify requirements, if only to demonstrate your thinking and analytical skills and even creativity - that is what the interview should be about.

For example in the absence of any specification that the "number" in question is necessarily an integer, you might propose the following:

int nextPow2( double x )
{
    return (int)pow( 2, ceil(log10(x) / log10(2))) ;
}

But if you did you might also express concern about the applicability of such a solution to an embedded system with possibly no floating-point unit.

Answer 4

I would answer by saying no one should write that in pure C. Especially in an embedded environment. If the chipset does not provide a feature to count the number of leading zeros in a word, then it's probably pretty old, and certainly not something you want to be using. If it does, you would want to use that feature.

As an example of a non-standard way to round an unsigned integer up to a power of two (you really need to clarify the type of the argument, as "number" is ambiguous) using gcc, you could do:

unsigned
round_up( unsigned x )
{
    if( x < 2 ) {
        return 1U;
    } else {
        return 1U << ( CHAR_BIT * sizeof x - __builtin_clz( x - 1 ));
    }
}

Answer 5

In contrast to what others have said, the bit-twiddling trick actually can be used on any number of bits portably. Just change it a bit:

unsigned int shift = 1;

for (v--; shift < 8 * sizeof v; shift <<= 1)
{
    v |= v >> shift;
}

return ++v;

I believe any compiler will optimize the loop away, so it should be the same performence-wise (plus I think it looks better).

Answer 6

Yet another variant.

int rndup (int num)
{
    int tmp=1;
    while (tmp<num)
    {
        tmp*=2;

    }
    return tmp;

}

Answer 7

Another variant using while loop and bit-wise operator

int next_pwr_of_2(unsigned &num)
{
    unsigned int number = 1;
    while (number < num)
    {
    number<<=1;
    }
    return number;
};