0

invert(x,p,n)位置 p から始まる n ビットを反転して (つまり、1 を 0 に、またはその逆に) x を返し、他のビットは変更しないで実装するように依頼されました。

私の解決策は次のとおりです。

unsigned invert(unsigned x, int p, int n)
{
       return (x ^ (((1 << (n + 1)) - 1) << (p - n + 1)));
}

問題に対するこの解決策をネットで見つけました：

unsigned invert(unsigned x, int p, int n)
{
    return x ^ ((~(~0<<n))<< p+1-n);
}

私にとっては間違っているように見えます-問題に対する正しく効果的なアプローチは何ですか

4

1 に答える 1

4

あなたの実装は明らかに間違っています。考慮してp = 1, n = 2ください：

x ^ (((1 << (n + 1)) - 1) << (p - n + 1))
x ^ (((1 << 3) - 1) << 0)
x ^ ((8 - 1) << 0)
x ^ 7

これは、x の下位 2 ビットではなく、下位 3 ビットを反転します。代わりに次を使用して修正できます。

return x ^ (1 << n) - 1 << p - n + 1;

（大量の偽のかっこも取り除きました）。これにはまだまれなバグがあります。呼び出し元が 1 つを除くすべてのビットを反転したい場合 (つまりn == sizeof x * CHAR_BIT - 1)。int が 32 ビットであると仮定して、例を見てみましょう:

x ^ (1 << n) - 1 << p - n + 1;
x ^ (1 << 31) - 1 << p - 31 + 1;
    ^^^^^^^^^
    ruh-roh!

残念ながら、これは未定義の動作を引き起こします (C11、§6.5.7 段落 4)。

E1 が符号付きの型で負でない値を持ち、E1 × 2 E2が結果の型で表現できる場合、それが結果の値です。それ以外の場合、動作は未定義です。

定数を符号なしにすることでこれを修正できます...1

return x ^ (1U << n) - 1 << p - n + 1;

...しかし、(つまり、呼び出し元がすべてのビットを反転したい場合) (C11、§6.5.7 段落 3) の場合、未定義の動作が発生します。n == sizeof x * CHAR_BIT

右オペランド ... の値が昇格された左オペランドの幅以上の場合、動作は未定義です。

あなたがネット上で見つけた解決策は、同じように未定義の動作に苦しんでいます。すべてのエッジ ケースを徹底的に正確に取得したい場合は、次の行に沿って何かを行う必要があります。

unsigned invert(unsigned x, int p, int n) {
    if (p < 0 || p >= sizeof x * CHAR_BIT) {
        /* flip out and kill people */
    }
    if (n < 0 || n > p + 1) {
        /*  (╯°□°）╯︵ ┻━┻) */
    }
    if (n == sizeof x * CHAR_BIT) return ~x;
    /* Having dealt with all the undefined cases,
       we can safely use your nice expression.
       But without all the parentheses.  Superfluous
       parentheses make hulk angry. */
    return x ^ (1U << n) - 1 << p - n + 1;
}

これは衒学的なやり過ぎですか？はい。面接の最初のパスとして誰かがこれを書くことを期待できますか? いいえ、ここに含まれる危険性について知的に議論できるようにしてほしいですか? はい。

于 2013-11-07T20:09:47.907 に答える