Temukan XOR dari semua angka dalam rentang tertentu

99

Anda diberi kisaran besar [a, b] di mana 'a' dan 'b' biasanya antara 1 dan 4,000,000,000 inklusif. Anda harus mencari XOR dari semua angka dalam rentang yang diberikan.

Masalah ini digunakan di TopCoder SRM. Saya melihat salah satu solusi yang dikirimkan dalam pertandingan dan saya tidak dapat mengetahui cara kerjanya.

Bisakah seseorang membantu menjelaskan solusi pemenang:

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

Di sini, getXor()adalah fungsi sebenarnya untuk menghitung xor dari semua bilangan dalam rentang yang dilewati [a, b] dan "f ()" adalah fungsi pembantu.

rajneesh2k10
sumber
Saya mengedit pertanyaan Anda sedikit. Kami tidak keberatan menjelaskan mengapa beberapa kode, tetapi kami tidak memerlukan daftar baru tentang cara lain untuk menyelesaikannya. Serahkan itu ke TopCoder.
Kev
@Kev Tidak ada masalah! Saya menulis itu karena beberapa orang lebih suka memberikan caranya sendiri daripada menjelaskan hal yang sudah tertulis. Dan ide baru apa pun tidak pernah sia-sia ...;)
rajneesh2k10
Ini memiliki perilaku tidak terdefinisi untuk a<=0, atau untuk b<0. long longadalah tipe bertanda, begitu x%4juga negatif (atau 0) untuk input negatif . Mungkin Anda ingin unsigned long long, dan / atau a & 3mengindeks array?
Peter Cordes

Jawaban:

152

Ini adalah solusi yang cukup pintar - ini mengeksploitasi fakta bahwa ada pola hasil dalam XOR yang sedang berjalan. The f()Fungsi menghitung XOR total run dari [0, a]. Lihat tabel ini untuk angka 4-bit:

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]

Dimana kolom pertama adalah representasi biner dan kemudian hasil desimal dan hubungannya dengan indeksnya (a) ke dalam daftar XOR. Ini terjadi karena semua bit atas dibatalkan dan dua bit terendah berputar setiap 4. Jadi, begitulah cara sampai ke tabel pencarian kecil itu.

Sekarang, pertimbangkan rentang umum [a, b]. Kita bisa menggunakan f()XOR untuk [0, a-1] dan [0, b]. Karena setiap nilai XOR dengan dirinya sendiri adalah nol, f(a-1)just membatalkan semua nilai dalam XOR berjalan kurang dari a, meninggalkan Anda dengan XOR dari rentang [a, b].

Kesalahan fatal
sumber
ambang batas minimum adalah 1, bukan 0
Pencho Ilchev
2
@PenchoIlchev Apakah itu termasuk 0 atau tidak adalah jenis diperdebatkan - (n ^ 0) == n
FatalError
2
@ Rajneesh2k10 Nah, dalam proses 4 (mulai dari kelipatan 4), semua bit kecuali yang terendah adalah sama, jadi mereka bergantian antara membatalkan satu sama lain atau memiliki nilai aslinya. Memang benar bahwa bit terendah berputar setiap 2, tetapi 0 ^ 1 == 1 (yaitu mereka tidak membatalkan). Alasan mengapa dua nilai terendah menjadi spesial adalah karena (00 ^ 01 ^ 10 ^ 11) == 00. Dengan kata lain, setiap 4 nilai yang Anda putar membuat Anda kembali ke 0, sehingga Anda dapat membatalkan semua siklus tersebut, yaitu mengapa% 4 signifikan.
FatalError
3
@Pandrei itu aada 2, bukan 0.
harold
1
Kolom itu adalah xor yang berjalan dan 1 xor 2 adalah 3, jadi nilai saat ini di baris itu terlihat benar bagi saya.
FatalError
58

Menambahkan jawaban bagus FatalError, kalimat return f(b)^f(a-1);itu bisa dijelaskan dengan lebih baik. Singkatnya, itu karena XOR memiliki properti luar biasa ini:

  • Ini asosiatif - Tempatkan tanda kurung di mana pun Anda inginkan
  • Ini bersifat komutatif - artinya Anda dapat memindahkan operator (mereka dapat "ngelaju")

Inilah keduanya beraksi:

(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c
  • Itu membalikkan dirinya sendiri

Seperti ini:

a ^ b = c
c ^ a = b

Tambah dan perkalian adalah dua contoh operator asosiatif / komutatif lainnya, tetapi mereka tidak membalikkan dirinya sendiri. Oke, jadi, mengapa properti ini penting? Cara yang sederhana adalah mengembangkannya menjadi apa adanya, dan kemudian Anda dapat melihat properti ini bekerja.

Pertama, mari kita tentukan apa yang kita inginkan dan beri nama n:

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

Jika membantu, pikirkan XOR (^) seolah-olah itu adalah tambahan.

Mari kita juga mendefinisikan fungsinya:

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

blebih besar dari a, jadi hanya dengan memasukkan beberapa tanda kurung ekstra dengan aman (yang dapat kami lakukan karena ini asosiatif), kami juga dapat mengatakan ini:

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

Yang disederhanakan menjadi:

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

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

Selanjutnya, kami menggunakan properti pembalikan dan komutivitas untuk memberi kami garis ajaib:

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

Jika Anda menganggap XOR seperti penjumlahan, Anda akan mengurangi pengurangan di sana. XOR adalah untuk XOR apa menambahkan untuk mengurangi!

Bagaimana saya mendapatkan ini sendiri?

Ingat properti operator logika. Bekerja dengan mereka hampir seperti menambah atau mengalikan jika itu membantu. Rasanya tidak biasa bahwa dan (&), xor (^) dan atau (|) adalah asosiatif, padahal memang demikian!

Jalankan implementasi naif melalui pertama, cari pola dalam output, lalu mulai temukan aturan yang mengonfirmasi bahwa pola tersebut benar. Sederhanakan penerapan Anda lebih jauh dan ulangi. Ini mungkin rute yang diambil oleh pembuat aslinya, disorot oleh fakta bahwa itu tidak sepenuhnya optimal (yaitu gunakan pernyataan switch daripada array).

Luke Briggs
sumber
3
Ini mengingatkan saya pada kursus Matematika Diskrit yang saya ambil tahun lalu di universitas. Hari-hari yang menyenangkan. Yang langsung terlintas di benak saya setelah membaca ini adalah komik XKCD ini .
Sean Francis N. Ballais
3

Saya menemukan bahwa kode di bawah ini juga berfungsi seperti solusi yang diberikan dalam pertanyaan.

Mungkin ini sedikit dioptimalkan tetapi itu hanya apa yang saya dapatkan dari mengamati pengulangan seperti yang diberikan dalam jawaban yang diterima,

Saya ingin mengetahui / memahami bukti matematika di balik kode yang diberikan, seperti yang dijelaskan dalam jawaban oleh @ Luke Briggs

Ini kode JAVA itu

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];
}
Parth Vishvajit
sumber
2

Saya telah memecahkan masalah dengan rekursi. Saya hanya membagi dataset menjadi bagian yang hampir sama untuk setiap iterasi.

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

Beri tahu saya pendapat Anda tentang solusinya. Senang mendapatkan masukan perbaikan. Solusi yang diusulkan menghitung XOR dalam kompleksitas 0 (log N).

Terima kasih

Abhijeet Sonawane
sumber
Yang ini memiliki kompleksitas Komputasi yang sama dengan perhitungan m ^ (m + 1) ^ ... ^ (n-1) ^ n normal. Ini adalah 0 (n).
Thế Anh Nguyễn
0

Untuk mendukung XOR dari 0 ke N kode yang diberikan perlu dimodifikasi seperti di bawah ini,

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);
}
Mohammad Nazmul Hossain
sumber