108

広い範囲[a、b]が与えられます。ここで、「a」と「b」は通常1〜4,000,000,000を含みます。指定された範囲内のすべての数値のXORを見つける必要があります。

この問題はTopCoderSRMで使用されました。試合で提出された解決策の1つを見ましたが、それがどのように機能するかを理解できません。

誰かが勝利の解決策を説明するのを手伝ってもらえますか？

long long f(long long a) {
     long long res[] = {a,1,a+1,0};
     return res[a%4];
}

long long getXor(long long a, long long b) {
     return f(b)^f(a-1);
}

ここで、getXor()は渡された範囲[a、b]のすべての数値のxorを計算する実際の関数であり、「f（）」はヘルパー関数です。

4

6 に答える 6

161

これは非常に巧妙なソリューションです。実行中のXORに結果のパターンがあるという事実を利用しています。このf()関数は、[0、a]からXOR合計実行を計算します。この表で4ビットの数値を確認してください。

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

ここで、最初の列は2進表現であり、次に10進結果とXORリストへのインデックス（a）との関係です。これは、すべての上位ビットがキャンセルされ、下位2ビットが4ごとに循環するために発生します。したがって、この小さなルックアップテーブルに到達する方法です。

ここで、[a、b]の一般的な範囲について考えてみましょう。f()[0、a-1]と[0、b]のXORを見つけるために使用できます。それ自体とXORされた値はすべてゼロであるためf(a-1)、XORのすべての値がキャンセルされa、範囲[a、b]のXORが残ります。

于 2012-05-20T03:13:10.583 に答える
62

FatalErrorのすばらしい答えに加えて、この行return f(b)^f(a-1);はより適切に説明できます。つまり、XORには次のようなすばらしい特性があるからです。

  • 連想的です-ブラケットを好きな場所に配置します
  • 可換です。つまり、オペレーターを移動できます（「通勤」できます）。

両方の動作は次のとおりです。

(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c
  • それは自分自身を逆転させます

このような：

a ^ b = c
c ^ a = b

加算と乗算は、他の結合/可換演算子の2つの例ですが、それ自体は逆になりません。では、なぜこれらのプロパティが重要なのですか？簡単な方法は、それを実際の状態に拡張することです。そうすれば、これらのプロパティが機能していることを確認できます。

まず、必要なものを定義して、それをnと呼びましょう。

n      = (a ^ a+1 ^ a+2 .. ^ b)

それが役立つ場合は、XOR（^）を追加であるかのように考えてください。

関数も定義しましょう：

f(b)   = 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ b

bはより大きいaので、いくつかの余分な角かっこを安全にドロップするだけで（結合法則であるため可能です）、次のように言うこともできます。

f(b)   = ( 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ (a-1) ) ^ (a ^ a+1 ^ a+2 .. ^ b)

これは次のように単純化されます。

f(b)   = f(a-1) ^ (a ^ a+1 ^ a+2 .. ^ b)

f(b)   = f(a-1) ^ n

次に、その反転プロパティと可換性を使用して、魔法の線を与えます。

n      = f(b) ^ f(a-1)

XORを加算のように考えていたとしたら、そこに減算を入れたでしょう。XORはXORに対して、加算は減算することです。

どうすればこれを自分で思いつくことができますか？

論理演算子のプロパティを覚えておいてください。それが役立つ場合は、ほとんど加算または乗算のようにそれらを操作します。and（＆）、xor（^）、or（|）が連想的であるのは珍しいと感じますが、連想的です！

最初に単純な実装を実行し、出力でパターンを探してから、パターンが真であることを確認するルールの検索を開始します。実装をさらに簡素化し、繰り返します。これはおそらく、元の作成者がたどったルートであり、完全に最適ではないという事実によって強調されています（つまり、配列ではなくswitchステートメントを使用します）。

于 2017-01-12T21:04:51.480 に答える
3

以下のコードも質問で与えられた解決策のように機能していることがわかりました。

これは少し最適化されているかもしれませんが、受け入れられた答えで与えられたような繰り返しを観察することから私が得たものです、

@Luke Briggsの回答で説明されているように、与えられたコードの背後にある数学的証明を知りたい/理解したい

これがそのJAVAコードです

public int findXORofRange(int m, int n) {
    int[] patternTracker;

    if(m % 2 == 0)
        patternTracker = new int[] {n, 1, n^1, 0};
    else
        patternTracker = new int[] {m, m^n, m-1, (m-1)^n};

    return patternTracker[(n-m) % 4];
}
于 2017-02-06T14:08:46.710 に答える
2

再帰の問題を解決しました。反復ごとにデータセットをほぼ等しい部分に分割するだけです。

public int recursion(int M, int N) {
    if (N - M == 1) {
        return M ^ N;
    } else {
        int pivot = this.calculatePivot(M, N);
        if (pivot + 1 == N) {
            return this.recursion(M, pivot) ^ N;
        } else {
            return this.recursion(M, pivot) ^ this.recursion(pivot + 1, N);
        }
    }
}
public int calculatePivot(int M, int N) {
    return (M + N) / 2;
}

解決策についてのあなたの考えを教えてください。改善のフィードバックをいただければ幸いです。提案されたソリューションは、0（log N）の複雑さでXORを計算します。

ありがとうございました

于 2018-01-28T16:42:24.543 に答える
0

0からNまでのXORをサポートするには、指定されたコードを次のように変更する必要があります。

int f(int a) {
    int []res = {a, 1, a+1, 0};
    return res[a % 4];
}

int getXor(int a, int b) {
    return f(b) ^ f(a);
}
于 2018-12-26T20:13:00.017 に答える
0

FatalErrorの答えにさらに加えて、で観察されたパターンがf()4つの数値ごとに循環することを（帰納法によって）証明することが可能です。

私たちはすべての整数についてそれを証明しようとしていますk >= 0、

f(4k + 1) = 1
f(4k + 2) = 4k + 3
f(4k + 3) = 0
f(4k + 4) = 4k + 4

はどこf(n)ですか1 ^ 2 ^ ... ^ n。

私たちのベースケースとして、私たちは手でそれを解決することができます

f(1) = 1
f(2) = 1 ^ 2 = 3
f(3) = 3 ^ 3 = 0
f(4) = 0 ^ 4 = 4

帰納的ステップ4xでは、これらの方程式が特定の整数（つまり）まで真であると仮定しますf(4x) = 4x。、、、およびについて4x + 1、方程式が真であることを示したいと思います。4x + 24x + 34x + 4

証明の記述と視覚化を支援するために、たとえば、 b(x)のバイナリ（基数2）文字列表現を示すことができます。x
b(7) = '111'b(9) = '1001'

と

b(4x)     = 'b(x)00'
b(4x + 1) = 'b(x)01'
b(4x + 2) = 'b(x)10'
b(4x + 3) = 'b(x)11'

これが帰納的ステップです：

Assume: f(4x) = 4x = 'b(x)00'
Then:

f(4x + 1) = f(4x)    ^ (4x + 1)  // by definition
          = f(4x)    ^ 'b(x)01'  // by definition
          = 'b(x)00' ^ 'b(x)01'  // from assumption
          = '01'                 // as b(x) ^ b(x) = 0

f(4x + 2) = f(4x + 1) ^ (4x + 2)
          = f(4x + 1) ^ 'b(x)10'       
          = '01'      ^ 'b(x)10'
          = 'b(x)11'             // this is 4x + 3

f(4x + 3) = f(4x + 2) ^ (4x + 3)
          = f(4x + 2) ^ 'b(x)11' 
          = 'b(x)11'  ^ 'b(x)11'
          = '00'

For the last case, we don't use binary strings, 
since we don't know what b(4x + 4) is.

f(4x + 4) = f(4x + 3) ^ (4x + 4)
          = 0         ^ (4x + 4)
          = 4x + 4

したがって、パターンは、の次の4つの数値に当てはまり4x、証明が完了します。

于 2022-03-01T23:40:38.800 に答える