Menemukan XOR maks dari dua angka dalam satu interval: dapatkah kita melakukan lebih baik daripada kuadratik?

Misalkan kita diberi dua angka dan dan kita ingin menemukan untuk l \ le i, \, j \ le r .$l$$r$$\max{(i\oplus j)}$$l\le i,\,j\le r$

Algoritma naif hanya memeriksa semua pasangan yang mungkin; misalnya dalam ruby, kita akan memiliki:

def max_xor(l, r)
  max = 0

  (l..r).each do |i|
    (i..r).each do |j|
      if (i ^ j > max)
        max = i ^ j
      end
    end
  end

  max
end

Saya rasa kita bisa melakukan lebih baik daripada kuadratik. Apakah ada algoritma yang lebih baik untuk masalah ini?

Kita dapat mencapai runtime linear dalam panjang dari representasi biner dari dan :$n$$l$$r$

Awalan dalam representasi biner dari dan , yaitu sama untuk kedua nilai, juga sama untuk semua nilai di antara mereka. Jadi bit ini akan selalu menjadi .$p$$l$$r$$0$

Sejak , bit yang mengikuti awalan ini akan menjadi in dan in . Selanjutnya, angka dan keduanya berada dalam interval.$r>l$$1$$r$$0$$l$$p10^{n-|p|-1}$$p01^{n-|p|-1}$

Jadi maks yang kita cari adalah .$0^{|p|}1^{n-|p|}$

Dimungkinkan untuk melakukannya dalam waktu .$\mathcal{O}(\log r)$

XOR maksimum yang mungkin dari dua bilangan bulat mana pun dari interval dapat ditentukan dari , dengan asumsi sebagai bilangan bulat. Nilai ini sama dengan , di mana adalah nilai terkecil sehingga lebih besar dari . l ⊕ r l , r 2 p - 1 p 2 p l ⊕ $[l, r]$$l \oplus r$$l, r$$2^p-1$$p$$2^p$$l \oplus r$

Berikut ini adalah implementasi di C ++

int maximumXOR(int l, int r) {
    int q = l ^ r, a = 1;
    while(q){
        q /= 2;
        a <<= 1;
    }
    return --a;
}

Kita perlu memaksimalkan xor antara 'kecil' dan 'tinggi'. Jadi mari kita ambil contoh untuk memahami hal ini.

5 xor 2 = 101 xor 010 kasus pertama: MSB bit tidak diatur untuk kedua nilai dalam range. Jika ingin memaksimalkan ini maka yang perlu kita lakukan adalah menjaga MSB dari 5 (100) apa adanya dan pikirkan tentang memaksimalkan sisa bit yang lebih rendah. Seperti kita ketahui bahwa bit yang lebih rendah semuanya akan menjadi satu untuk kasus ketika semuanya 11 yang tidak lain adalah 3 yaitu 2 ^ 2-1. Karena masalahnya berbicara tentang kisaran antara 2 hingga 5, kami memiliki 3 dalam kisaran tersebut. Jadi yang perlu kita lakukan adalah mencari tahu set MSB tertinggi dalam nilai 2 yang lebih besar dan menambahkan 1 sisanya untuk bit yang lebih rendah.

kasus kedua: Adapun kasus ketika MSB diatur untuk kedua nilai dalam rentang xor akan defintely memiliki bit-bit tersebut ditetapkan sebagai 0 dan kita harus kembali ke bit yang lebih rendah. Sekali lagi untuk bit yang lebih rendah kita perlu mengulangi logika yang sama seperti kasus pertama. contoh: (10, 12) (1010, 1100) Seperti yang Anda lihat keduanya memiliki MSB ditetapkan sebagai 1 maka kita harus kembali ke bit yang lebih rendah yaitu 010 dan 100. Sekarang masalah ini sama dengan kasus pertama.

Ada beberapa cara untuk membuat kode ini. Apa yang saya lakukan adalah melakukan hanya xor antara 'kecil' dan 'tinggi' dan itu akan menghapus bit MSB jika keduanya 'kecil' dan 'tinggi' memiliki bit set MSB. Jika itu tidak terjadi maka akan mempertahankan bit MSB. Setelah itu saya mencoba untuk membuat semua bit 1 yang lebih rendah dengan mencari tahu kekuatan maksimum 2 pada output xored dan mengurangi dari 1.

def range_xor_max(small, high):
  if small == high:
    return 0
  xor = small ^ high
  #how many power of 2 is present
  how_many_power_of_2 = math.log(xor, 2)
  #we need to make all one's below the highest set bit
  return 2**int(math.floor(how_many_power_of_2)+1) - 1

Nah, Anda bisa menggunakan XOR dari l dan r untuk menemukan jawabannya.

Misalkan, l = 4 dan r = 6.

l = 100, r = 110 (setara biner dari angka-angka ini)

lr = 0 10

Artinya, nilai maksimum yang Anda cari pasti akan memiliki bit pertama (MSB) sebagai nol. (Pikirkan tentang itu, mungkinkah nilai maksimum Anda memiliki 1 pada bit pertama? Jika itu 01010 dan 00101, xor akan menjadi = 01 111 yaitu nilai maksimum antara 01010 dan 00101 pasti akan memiliki a 1 di bit kedua mereka dari kiri, itu tidak mungkin untuk mendapatkan 1 sebelum bit kedua dari kiri yaitu di bit pertama dari kiri)

Jadi, Anda memiliki 2 bit yang tersisa untuk menemukan maksimum. Kita tahu, bahwa nilai maksimum yang mungkin ketika kita memiliki n bit bersama kita adalah = 2 ⁿ −1, oleh karena itu jawaban dalam kasus ini adalah 2 ² -1 = 4-1 = 3.

Dari contoh di atas, kita dapat membuat algoritma umum untuk ini.

Langkah 1. num = jumlah bit yang diperlukan untuk merepresentasikan max ( l , r )

Langkah 2. res = l ⊕ r

Langkah 3. pos = Posisi bit pertama yang ditetapkan dari kiri di res (pengindeksan berbasis 0)

Langkah 4. n = num - pos

Langkah 5. ans = 2 ⁿ −1

Kompleksitas waktu = O (n)

Untuk setiap digit biner, ada 4 kemungkinan: 1_and_1, 1_and_0, 0_and_1, atau 0_and_0. Digit yang lebih rendah mungkin tidak membuat atau log-menghilang-sangat kecil perbedaan untuk output xor pilihan digit berikutnya. Algoritma terbaik yang mungkin adalah mengabaikan semua digit yang lebih rendah dan hanya mempertimbangkan 2 yang tersedia berikutnya, diberikan pilihan sebelumnya tentang digit yang lebih tinggi. Jika ini 1_and_1 atau 0_and_0, pilihannya jelas, tetapi jika digit ini adalah 1_and_0 vs 0_and_1 (yang memiliki nilai xor tapi tidak sama) maka secara rekursif harus sama dengan https://en.wikipedia.org/wiki/Edit_distance algoritma, berarti kasus terburuk dari log kuadrat.

Untuk interval 32-bit, saya baru saja menemukan O(1)solusi ini pada editorial Peringkat Hacker. Saya tidak tahu bagaimana cara kerjanya, tetapi itu bekerja. (Mungkin seseorang dapat menjelaskan mengapa itu berhasil.)

def max_xor(L,R):
  v = L^R
  v |= v >> 1
  v |= v >> 2
  v |= v >> 4
  v |= v >> 8
  v |= v >> 16
  return b

Sumber: https://www.hackerrank.com/challenges/maximizing-xor/editorial