11

我在一次采访中得到了以下问题：“编写一个将数字四舍五入为 2 的下一个幂的 C 函数。”

我写了以下答案：

#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 时会跳出循环？

4

7 回答 7

28

优先我的朋友，优先。

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

会修复它。（注意表达式周围的括号tmp & num）

!=的优先级高于&，因此num != 0在 之前进行评估tmp & num。

如果跳过括号，则计算的表达式为：tmp & (num != 0)

  1. 第一次循环，tmp = 9 (1001)并且num != 0is 1 (0001)so&评估为 1（真），然后循环继续。

  2. 现在在第二次迭代结束时，我们有tmp = 10 (1010). num != 0再次为 0001，因此1010 & 0001计算结果为0，因此循环中断。

这是供参考的表格。

如此处所述，优先顺序非常不寻常。一直在发生:)。

当然你不必记住任何优先顺序，这只是为了帮助编译器在程序员没有明确说明的情况下决定首先做什么。您可以正确地将表达式括起来并避免这种情况。

于 2013-02-11T13:35:31.730 回答
20

循环退出是因为您没有在条件周围加上括号。这应该教会你不要把不必要的东西!= 0放在你的 C/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 次操作才能完成的代码不同，上述代码始终在十二次操作（减量、增量、五班和 5OR秒）后完成。

于 2013-02-11T13:39:25.393 回答
2

这样的问题总是值得反问来澄清要求，如果只是为了展示你的思维和分析能力，甚至是创造力——这就是面试应该关注的内容。

例如，在没有任何说明所讨论的“数字”必须是整数的情况下，您可能会提出以下建议：

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

但是，如果您这样做了，您可能还会担心这种解决方案对可能没有浮点单元的嵌入式系统的适用性。

于 2013-02-12T09:41:35.997 回答
1

我会回答说没有人应该用纯 C 来写。尤其是在嵌入式环境中。如果芯片组没有提供计算单词中前导零数量的功能，那么它可能已经很老了，而且肯定不是您想要使用的东西。如果是这样，您会想要使用该功能。

作为使用 gcc 将无符号整数四舍五入为 2 的幂的非标准方法的示例（您确实需要澄清参数的类型，因为“数字”是不明确的），您可以这样做：

unsigned
round_up( unsigned x )
{
    if( x < 2 ) {
        return 1U;
    } else {
        return 1U << ( CHAR_BIT * sizeof x - __builtin_clz( x - 1 ));
    }
}
于 2013-02-11T14:15:14.057 回答
1

又一个变种。

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

    }
    return tmp;

}
于 2015-01-09T02:34:34.347 回答
1

与其他人所说的相反，比特旋转技巧实际上可以便携地用于任意数量的比特。稍微改一下：

unsigned int shift = 1;

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

return ++v;

我相信任何编译器都会优化循环，所以它应该在性能方面是相同的（而且我认为它看起来更好）。

于 2013-03-03T18:08:08.870 回答
0

另一个使用 while 循环和按位运算符的变体

int next_pwr_of_2(unsigned &num)
{
    unsigned int number = 1;
    while (number < num)
    {
    number<<=1;
    }
    return number;
};
于 2014-06-14T01:27:43.287 回答