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. 1 回目なので、1 (真) と評価され、ループが続行されますtmp = 9 (1001)。num != 01 (0001)&

  2. 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 回の操作が必要なコードとは異なり、上記は常に 12 回の操作 (デクリメント、インクリメント、5 つのシフト、および 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 に答える