6

コードを貼り付けて、ビット演算子を使用して2つの数値の合計を求めています。最適化できるかどうか提案してください。ありがとう...

public static int getSum(int p, int q)
{
int carry=0, result =0;
for(int i=0; i<32; i++)
{
    int n1 = (p & (1<<(i)))>>(i); //find the nth bit of p
    int n2 = (q & (1<<(i)))>>(i); //find the nth bit of q

    int s = n1 ^ n2 ^ carry; //sum of bits
    carry = (carry==0) ? (n1&n2): (n1 | n2); //calculate the carry for next step
    result = result | (s<<(i)); //calculate resultant bit
}

return result;
}
4

3 に答える 3

27

少しずつ考えてみましょう:

public static int getSum(int p, int q)
{
    int result = p ^ q; // + without carry 0+0=0, 0+1=1+0=1, 1+1=0
    int carry = (p & q) << 1; // 1+1=2
    if (carry != 0) {
        return getSum(result, carry);
    }
    return result;
}

この再帰は、キャリーの右側のビット 0 が連続して増えるため (最大 32 回の繰り返し) 終了します。

でループとして簡単に書くことができますp = result; q = carry;。

アルゴリズム探索のもう 1 つの特徴は、ケースを区別する際に行き過ぎないことです。上記の条件を使用することもできます: if ((result & carry) != 0).

于 2013-03-16T14:15:02.217 に答える
2

最適化は、パフォーマンス（おそらくコンパイラーによって処理される）ではなく、読みやすさの分野にあるべきだと思います。

whileの代わりにforループを使用する

事前に反復回数がわかっている場合、このイディオムfor (int i=0; i<32; i++)はwhileループよりも読みやすくなります。

数値を2で割ります

数値を2で割って、係数を取得します。

n1 = p % 2;
p  /= 2;

おそらく次よりも読みやすいです：

(p & (1<<(i-1)))>>(i-1);
于 2013-03-10T20:29:10.410 に答える