Напишите функцию C, которая округляет число до следующей мощности 2

В интервью у меня появился следующий вопрос: "Напишите функцию C, которая округляет число до следующей мощности 2".

Я написал следующий ответ:

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

Вопрос: почему программа выходит из цикла do-while при достижении значений 11 и 10?

Ответ 1

Приоритет мой друг, приоритет.

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

Будет исправлено. (обратите внимание на скобки вокруг выражения tmp & num)

!= имеет более высокий приоритет, чем &, поэтому num != 0 оценивается до tmp & num.

Если вы пропустите скобку, оцениваемое выражение: tmp & (num != 0)

Первый раунд tmp = 9 (1001) и num != 0 равен 1 (0001), поэтому & получает значение 1 (true), и цикл продолжается.
Теперь в конце второй итерации имеем tmp = 10 (1010). num != 0 снова 0001, поэтому 1010 & 0001 оценивается как 0, поэтому цикл прерывается.

Здесь приведена таблица для справки.

Порядок приоритетов довольно необычен, как указано здесь. Бывает все время:).

Конечно, вам не нужно запоминать какой-либо порядок приоритетов, который должен помочь компилятору решить, что делается первым, если программист не дает понять. Вы можете просто правильно скопировать выражение и избежать таких ситуаций.

Ответ 2

Цикл завершается, потому что вы не помещали круглые скобки вокруг вашего условия. Это должно научить вас не ставить ненужные != 0 в ваши условия C/С++.

Вы можете немного упростить свой код.

Во-первых, обратите внимание, что temp равно предыдущему значению num, поэтому вы можете изменить свой цикл на

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

Во-вторых, интервьюер, вероятно, хотел посмотреть, знакомы ли вы с этим небольшим трюком:

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

В отличие от вашего кода, который может занять до 1 000 000 000 операций, вышеуказанное всегда завершается после двенадцати операций (декремент, приращение, пять смен и пять OR s).

Ответ 3

Такие вопросы всегда заслуживают встречных вопросов для разъяснения требований, хотя бы для демонстрации ваших навыков мышления и аналитики и даже творчества - вот о чем должно быть интервью.

Например, при отсутствии какой-либо спецификации, что "число", о котором идет речь, обязательно является целым числом, вы можете предложить следующее:

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

Но если бы вы это сделали, вы могли бы также выразить обеспокоенность применимостью такого решения для встроенной системы, возможно, с плавающей точкой.

Ответ 4

Я бы ответил, сказав, что никто не должен писать это в чистом C. Особенно во встроенной среде. Если чипсет не предоставляет функции для подсчета количества ведущих нулей в слове, то он, вероятно, довольно старый, и, конечно же, не то, что вы хотите использовать. Если это так, вы хотите использовать эту функцию.

В качестве примера нестандартного способа округления целого числа без знака до степени два (вам действительно нужно уточнить тип аргумента, поскольку "число" неоднозначно) с помощью gcc вы можете сделать:

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

Ответ 5

В отличие от других, бит-трюк фактически может использоваться на любом количестве бит в переносимости. Просто измените это немного:

unsigned int shift = 1;

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

return ++v;

Я считаю, что любой компилятор будет оптимизировать цикл, поэтому он должен быть таким же, как и с точки зрения производительности (плюс, я думаю, он выглядит лучше).

Ответ 6

Еще один вариант.

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

    }
    return tmp;

}

Ответ 7

Другой вариант, использующий оператор while и bit-wise

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