编写一个C函数，将数字向下舍入到下一个2的幂

我在接受采访时得到了以下问题：“编写一个C函数，将一个数字向下舍入到下一个2的幂”。

我写了以下答案：

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

问题是：为什么程序在获得值11和10时会超出其do-while循环？

Answer 1

优先考虑我的朋友，优先。

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

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

!=具有比&更高的优先级，因此在tmp & num之前计算num != 0 。

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

1. 第一轮， tmp = 9 (1001)并且num != 0是1 (0001)因此&评估为1（真），并且循环继续。

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

这是表格供参考。

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

当然，您不必记住任何优先顺序，这只是为了帮助编译器在程序员不清楚的情况下决定首先执行的操作。 您可以正确地将表达式括起来并避免出现这种情况。

Answer 2

循环退出是因为您没有在您的条件周围放置括号。 这应该教你不要在你的C / C ++条件中放置不必要的!= 0 。

不过，您可以相当简化代码。

首先，观察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个操作完成不同，上述操作总是在12次操作（减量，增量，5次移位和5次OR ）后完成。

Answer 3

这些问题总是值得反驳，以澄清要求，如果只是为了展示你的思考和分析能力，甚至是创造力 – 那就是面试应该是什么。

例如，在没有任何规范的情况下，所讨论的“数字”必然是整数，您可以提出以下建议：

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

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

Answer 4

我会回答说没有人应该用纯C来写。特别是在嵌入式环境中。 如果芯片组没有提供计算单词中前导零数的function，那么它可能很旧，当然也不是你想要使用的东西。 如果是，您可能希望使用该function。

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

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

Answer 5

与其他人所说的相反，实际上可以在任意数量的比特上使用比特琐事。 只需改变一下 ：

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

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

Answer 6

另一种变体。

 int rndup (int num) { int tmp=1; while (tmp 

Answer 7

使用while循环和逐位运算符的另一种变体

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