55

私は配列内の孤独な整数を見つけるためのアルゴリズムを研究していましたが、実装は次のとおりです。

int arr[] = {10, 20, 30, 5, 20, 10, 30};
int LonelyInteger = 0;
for(int i=0; i< 7; i++)
{
    LonelyInteger = LonelyInteger ^ arr[i];
}

結果は5です。

私の質問は-おそらく、この操作のために整数(XOR操作によって生成される)が大きすぎるということです:

LonelyInteger ^ arr[i]

intこれは、この場合のデータ型では表現できない潜在的に大きな整数につながります。私の質問は次のとおりです。

  1. XOR型に格納できないような大きな整数値を生成する可能性さえありintますか?
  2. これが起こる可能性がない場合、これの証拠はありますか?
4

10 に答える 10

28

(この投稿は C++ ではなく C に適用されます)

ビット単位の演算子は、無効なパディング ビットを設定するため、トラップ表現を引き起こすことができません。C11 6.2.6.2/1 脚注を参照してください。

...有効な値に対する算術演算は、トラップ表現を生成できません...

(「算術演算」の意味は不明ですが、インデックスは XOR の定義である 6.5.11 にリンクしています)。

ただし、C では、負のゼロが生成される可能性があります。2 の補数には負のゼロはありません。しかし、1 の補数を持つシステムを使用している場合、負のゼロを介して生成することができ^、これによりトラップ表現が発生する可能性があります。6.2.6.2/3 は、これが可能であると明示的に述べています。

実装が負のゼロをサポートする場合、それらは以下によってのみ生成されます:

— そのような値を生成するオペランドを持つ &、|、^、~、<<、および >> 演算子。

最後に 6.2.6.2/2 は、(とにかくかなり確信しています) を超える整数を表す値ビットの組み合わせを持つことは不可能であることを意味しますINT_MAX

要約すると、^on twointの考えられる結果は次のとおりです。

  • 別の有効なint値 (おそらく、同じ値の他のバージョンとは異なるがトラップされないパディング ビットを使用)
  • トラップが発生する場合と発生しない場合がある負のゼロ
于 2015-02-04T11:55:57.383 に答える
21

厳密に言えば、2 つの整数を XOR することはできません。整数サイズのビットの 2 つのバッグを XOR することができ、それらのビットのバッグを整数として扱うこともできます。それ以外の場合は整数として扱うこともできます。

しかし、XOR 演算を実行する時点では、それらを整数や数値とはまったく異なるものとして扱っています。それらは、対応するビットが比較される 2 つのビット シーケンスにすぎません。オーバーフローの概念は当てはまらないため、結果を整数として扱うことにした場合、オーバーフローすることもありません。

于 2015-02-05T01:38:43.897 に答える
11

XOR が int 型に格納できないような大きな整数値を生成する可能性さえありますか?

オペランドが の場合、intいいえ。

これが起こる可能性がない場合、これの証拠はありますか?

まあ、それは定義から自明です。これは数学的に厳密な証明とは言えませんが、XOR の出力のビットは、オペランドの 1 つがその位置に 1 を持っている場合にのみ 1 になると考えることができます。範囲外のビットはオペランドで 1 になることはできないため、範囲外の値が 1 の出力ビットはありません。

于 2015-02-04T11:47:18.233 に答える
11

XOR、AND、OR、NOT およびその他のビット単位の演算子はビット単位の結果を生成し、結果のビットは入力内のまったく同じ位置にあるビットから結合されます。したがって、n ビットの入力は上位ビットなしで n ビットを生成します。

于 2015-02-04T12:57:03.487 に答える
7

一般的なケースでは、説明されているアルゴリズムは、配列内の孤立した整数を実際に見つけることはできません。実際に検出されるXORのは、そこに奇数回出現するすべての要素です。

したがって、要素が 1 つだけ存在'a'し、他のすべての要素が配列内で偶数回出現する場合、「必要に応じて」動作します -> この孤独な要素を見つけます'a'。

なんで？

アルゴリズムはXOR、配列内のすべての要素を実行します(a ^ b ^ c ^ d ^ ...)

XOR操作には次のプロパティがあります。

1) a ^ a = 0 (non-equivalence)

2) a ^ 0 = a (neutrality of 0)

3) a ^ b = b ^ a (commutative property)

4)(a ^ b) ^ c = a ^ (b ^ c) (associative property)

たとえば、要素を持つ配列を考えてみましょう:{a, b, c, a, c, b, a, c}

(要素'a'- 3 回、要素'b'- 2 回、要素'c'- 3 回)

次に、上記のXORプロパティに従って、アルゴリズムの結果

R = (((((((a ^ b) ^ c) ^ a) ^ c) ^ b) ^ a) ^ c)

次のように再配置できます。

R = (a ^ b) ^ (c ^ a) ^ (c ^ b) ^ (a ^ c) =

= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ (a ^ c) =

= 0 ^ 0 ^ 0 ^ (a ^ c) = (a ^ c)

つまり、

a) ...偶数回出現するすべての要素はゼロになる

b) ...奇数回発生するすべての要素は XOR 演算され、最終結果が作成されます

XORはビット単位の操作なので、もちろんオーバーフローすることはありません。

于 2015-02-04T17:57:58.090 に答える