Dostajesz duży zakres [a, b], gdzie „a” i „b” mogą zwykle wynosić od 1 do 4 000 000 000 włącznie. Musisz znaleźć XOR wszystkich liczb w podanym zakresie.

Ten problem był używany w TopCoder SRM. Widziałem jedno z zgłoszonych rozwiązań w meczu i nie jestem w stanie dowiedzieć się, jak działa.

Czy ktoś mógłby pomóc wyjaśnić zwycięskie rozwiązanie:

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);
}

Tutaj getXor()jest rzeczywistą funkcją obliczającą xor wszystkich liczb w przekazanym zakresie [a, b] i "f ()" jest funkcją pomocniczą.

Jest to całkiem sprytne rozwiązanie - wykorzystuje fakt, że w działających XORach istnieje wzór wyników. f()Oblicza całkowitą XOR uruchamiane z [0, A]. Spójrz na tę tabelę dla liczb 4-bitowych:

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]

Gdzie pierwsza kolumna jest reprezentacją binarną, a następnie wynik dziesiętny i jego związek z indeksem (a) do listy XOR. Dzieje się tak, ponieważ wszystkie górne bity anulują się, a najniższe dwa bity cyklicznie co 4. Tak więc można dojść do tej małej tablicy przeglądowej.

Rozważmy teraz ogólny zakres [a, b]. Możemy użyć f()do znalezienia XOR dla [0, a-1] i [0, b]. Ponieważ każda wartość XOR ze sobą równa się zero, po f(a-1)prostu anuluje wszystkie wartości w XOR, które są mniejsze niż a, pozostawiając XOR zakresu [a, b].

Dodając do świetnej odpowiedzi FatalError, kwestię tę return f(b)^f(a-1);można wyjaśnić lepiej. Krótko mówiąc, to dlatego, że XOR ma te wspaniałe właściwości:

• Jest asocjacyjny - umieść nawiasy w dowolnym miejscu
• Jest przemienny - oznacza to, że możesz przemieszczać operatorów (mogą „dojeżdżać”)

Oto oba w akcji:

(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c

• To się odwraca

Lubię to:

a ^ b = c
c ^ a = b

Dodawanie i mnożenie to dwa przykłady innych operatorów asocjacyjnych / przemiennych, ale one same się nie odwracają. Ok, więc dlaczego te właściwości są ważne? Cóż, prostą drogą jest rozszerzenie tego na to, czym naprawdę jest, a następnie możesz zobaczyć te właściwości w działaniu.

Najpierw zdefiniujmy, czego chcemy i nazwijmy to:

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

Jeśli to pomoże, pomyśl o XOR (^) tak, jakby to był dodatek.

Zdefiniujmy też funkcję:

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

bjest większe niż a, więc po prostu bezpiecznie upuszczając kilka dodatkowych nawiasów (co możemy, ponieważ jest asocjacyjne), możemy również powiedzieć to:

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

Co upraszcza:

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

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

Następnie używamy tej właściwości odwrócenia i przemienności, aby uzyskać magiczną linię:

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

Jeśli myślałeś o XOR jak o dodaniu, zostawiłbyś tam odejmowanie. XOR jest dla XOR tym, czym dodawanie jest odejmowaniem!

Jak mam to wymyślić?

Zapamiętaj właściwości operatorów logicznych. Pracuj z nimi prawie jak dodawanie lub mnożenie, jeśli to pomaga. Wydaje się niezwykłe, że i (&), xor (^) i lub (|) są skojarzone, ale tak jest!

Najpierw uruchom naiwną implementację, poszukaj wzorców w danych wyjściowych, a następnie zacznij znajdować reguły, które potwierdzają, że wzorzec jest prawdziwy. Jeszcze bardziej uprość wdrażanie i powtórz. Prawdopodobnie jest to droga, którą obrał pierwotny twórca, podkreślona faktem, że nie jest ona całkowicie optymalna (tj. Użyj instrukcji switch zamiast tablicy).

Dowiedziałem się, że poniższy kod również działa jak rozwiązanie podane w pytaniu.

Być może jest to trochę zoptymalizowane, ale właśnie to otrzymałem obserwując powtórzenia podane w zaakceptowanej odpowiedzi,

Chciałbym poznać / zrozumieć dowód matematyczny za podanym kodem, jak wyjaśniono w odpowiedzi @Luke Briggs

Oto kod 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];
}

Rozwiązałem problem z rekurencją. Po prostu dzielę zbiór danych na prawie równą część dla każdej iteracji.

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;
}

Daj mi znać, co myślisz o rozwiązaniu. Chętnie otrzymuję informacje zwrotne dotyczące ulepszeń. Zaproponowane rozwiązanie oblicza XOR ze złożonością 0 (log N).

Dziękuję Ci

Aby obsługiwać XOR od 0 do N, podany kod musiał zostać zmodyfikowany jak poniżej,

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);
}