1

これは私が遭遇したインタビューの問題です。数値の XOR を繰り返して力ずくで解決する方法は知っていますが、これをより効率的に行う方法はわかりません。

キャリアカップでこのソリューションを見ました：

typedef unsigned long long UINT64;

UINT64 getXOROne2N(UINT64 n) {
    switch (n % 4) {
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        case 3: return 0;
    }
    return 0;
}

しかし、男の説明があっても、ここのロジックを正確に理解していません。誰かがこれを行う方法を説明してもらえますか?

4

2 に答える 2

3

の昇順の値の答えを見ると、数学的パターンが生じますn。4段で回転しているような感じです。これは、奇数と偶数を xor して、前の偶数と奇数の結果のさまざまな組み合わせにする間を行ったり来たりしているためです。連続する xor ごとに、ローテーションの 4 分の 1 が表示されます。実演して説明します。

最初から始めて、ケースバイケースでこれを調べてみましょうn=1:

00000001

case 1これは、返される結果が 1 である解の範囲内にあることに注意してください。また、この の値nは奇数であるため、必ず で終わることに注意してください1。

ここで、 の解を計算するとn=2、それは の新しい値で xor された前の答えの解になりますn。

00000001
       ^
00000010
--------
00000011

case 2これは、返される結果が であるソリューションの範囲内にあることに注意してくださいn + 1。また、この場合nは偶数であり、必然的に末尾が 1 になることに注意してください。つまり0、前の結果の 1 (奇数) に xored すると、追加のビットをオンにするだけなので、同様の場合の結果は常に同様にn+1

次の値の場合、当然、 の結果getXOROne2N(3)は前の結果であり、 によって xor され3ます。興味深いことに、これは私たちをゼロに一掃します。

00000011
       ^
00000011
--------
00000000

これは、考えてみれば当然のことです。の結果はgetXOROne2N(2)だっn+1 = 2+1 = 3たので、( ) に沿った次の値に xor すると、当然のことながら、すべての符号付きビットがキャンセルされて 0 に戻ります。また、これは提示されたソリューションにn+1該当することに注意してください。case 3

さて、0 を取得した後の次の値を計算するときはいつでも、次のgetXOROne2N値になります。つまり、n4getXOROne2N(4)です。

00000000
       ^
00000100
--------
00000100

case 0これは、提示したソリューションにうまく収まることに注意してください。

ここで、40 の前の結果への xor は偶数であるため、結果には必然的に後続の 0 があります。したがって、フォールドへの xor の行の次の値 5 は、この前のビット構成を持つ必要がありますが、最後のビットは 1 に設定されます。を計算する前の結果に xor するとgetXOROne2N(5)、最後のビット以外はすべてキャンセルされ、1 に戻ります。

00000100
       ^
00000101
--------
00000001

したがって、私たちはローテーションを形成します。この次は偶数を xor してn+1(奇数) を生成し、その次は (奇数を xor0してこの偶数の結果を生成する) にキャンセルし、次の値を取得しますn(これは偶数である必要があります)、したがって、次の奇数の次の値を xor すると、最後に残っているビット以外のすべてのビットがキャンセルされ、再び 1 が生成されます。

悪循環です！しかし、かなりきれいだと思います。

于 2015-11-14T07:13:05.313 に答える
2

最初に注意すべきことは、4 で割り切れる数から始まる連続した 4 つの数は、XOR をとった場合に 0 になるということです。

    ...00 - starting with any binary digits
    ...01
    ...10
    ...11
XOR -----
        0 : 4 times (...), twice 1 for both lower digits

これは事実上、4 で割り切れる max の後の最後の数値のみnが実際の結果を形成することを意味します (それぞれが 0 になるクワッドで前のすべての数値をグループ化できます)。

だから、それは来る

%4    n               calc           result
0   ...00  ->  ...00 =               n
1   ...01  ->  ...00 XOR ...01 =     1
2   ...10  ->  ...10 XOR 1 = ...11 = n + 1
3   ...11  ->  ...11 XOR ...11 =     0
于 2015-11-14T07:14:25.653 に答える