Encontrando o XOR máximo de dois números em um intervalo: podemos fazer melhor que quadrático?

Suponha que nós estamos dando dois números e e que queremos encontrar para l \ le i, \, j \ le r .$l$$r$ l ≤ i $\max{(i\oplus j)}$$l\le i,\,j\le r$

O algoritmo ingênuo simplesmente verifica todos os pares possíveis; por exemplo, em ruby, teríamos:

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

Eu sinto que nós podemos fazer melhor do que quadrática. Existe um algoritmo melhor para esse problema?

Podemos obter um tempo de execução linear no comprimento da representação binária de e :l $n$$l$$r$

O prefixo na representação binária de e , que é o mesmo para os dois valores, também é o mesmo para todos os valores entre eles. Portanto, esses bits sempre serão .l r $p$$l$$r$$0$

Desde , o bit seguindo este prefixo será no e em . Além disso, os números e estão no intervalo.1 r 0 l p 10 n - | p | - 1 p 01 n - | p | - $r>l$$1$$r$$0$$l$$p10^{n-|p|-1}$$p01^{n-|p|-1}$

Portanto, o máximo que estamos procurando é .$0^{|p|}1^{n-|p|}$

É possível fazê-lo no tempo .$\mathcal{O}(\log r)$

O XOR máximo possível de quaisquer dois inteiros de um intervalo pode ser determinado a partir de l ⊕ r , assumindo que l , r sejam inteiros. Este valor é igual a 2 p - 1 , onde p é o menor valor, de modo que $[l, r]$$l \oplus r$$l, r$$2^p-1$$p$ é maior que l ⊕ r . $2^p$$l \oplus r$

Aqui está uma implementação em C ++

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

Precisamos maximizar o xor entre 'pequeno' e 'alto'. Então, vamos dar um exemplo para entender isso.

5 xor 2 = 101 xor 010 primeiro caso: o bit MSB não está definido para os dois valores no intervalo. Se você deseja maximizar isso, o que precisamos fazer é manter o MSB de 5 (100) como está e pensar sobre maximizando os bits inferiores restantes. Como sabemos, todos os bits inferiores serão um para o caso em que tudo é 11, que nada mais é do que 3, isto é, 2 ^ 2-1. Como o problema está falando sobre o intervalo entre 2 e 5, temos definitivamente 3 no intervalo. Então, tudo o que precisamos fazer é descobrir o maior MSB definido no maior dos 2 valores e adicionar os 1s restantes para os bits mais baixos.

segundo caso: como no caso em que MSB está definido para ambos os valores no intervalo xor, esses bits serão definidos como 0 e precisamos voltar aos bits mais baixos. Novamente, para bits mais baixos, precisamos repetir a mesma lógica do primeiro caso. exemplo: (10, 12) (1010, 1100) Como você pode ver que o MSB está definido como 1, temos que voltar aos bits inferiores, que são 010 e 100. Agora, esse problema é o mesmo do primeiro caso.

Existem várias maneiras de codificar isso. O que fiz foi fazer apenas o xor entre 'pequeno' e 'alto' e isso removerá o bit MSB se 'pequeno' e 'alto' tiverem o bit MSB definido. Caso esse não seja o caso, ele preservará o bit MSB. Depois disso, estou tentando fazer todos os bits 1 menores, descobrindo a potência máxima de 2 na saída xored e subtraindo de 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

Bem, você pode usar o XOR de l e r para encontrar a resposta.

Suponha, l = 4 er = 6.

l = 100, r = 110 (equivalentes binários desses números)

l⊕r = 0 10

O que isso significa é que o valor máximo que você está procurando definitivamente terá seu primeiro bit (MSB) como zero. (Pense bem, é possível que seu valor máximo seja 1 no primeiro bit? Se fosse 01010 e 00101, o xor teria sido = 01 111 ou seja, o valor máximo entre 01010 e 00101 definitivamente terá um 1 no segundo bit da esquerda, não é possível obter um 1 antes do segundo bit da esquerda, ou seja, no primeiro bit da esquerda)

Então, você fica com os 2 bits restantes para encontrar o máximo. Sabemos que o valor máximo possível quando temos n bits conosco é = 2 ⁿ -1, portanto, a resposta neste caso será 2 ² -1 = 4-1 = 3.

A partir do exemplo acima, podemos criar um algoritmo geral para isso.

Etapa 1. num = número de bits necessários para representar max ( l , r )

Etapa 2. res = l ⊕ r

Etapa 3. pos = posição do primeiro bit definido da esquerda em res (indexação baseada em 0)

Etapa 4. n = num - pos

Etapa 5. ans = 2 ⁿ −1

Complexidade temporal = O (n)

Para cada dígito binário, existem 4 possibilidades: 1_e_1, 1_e_0, 0_e_1 ou 0_e_0. Os possíveis dígitos mais baixos não fazem diferença ou são muito pequenos para a saída xor da escolha do próximo dígito. O melhor algoritmo possível é ignorar todos os dígitos mais baixos e considerar apenas os 2 seguintes disponíveis, dadas as opções anteriores sobre dígitos mais altos. Se for 1_e_1 ou 0_e_0, a escolha é clara, mas se esse dígito for 1_e_0 vs 0_e_1 (que têm xor igual, mas com valor desigual), então recursivamente deve ser igual ao algoritmo https://en.wikipedia.org/wiki/Edit_distance , significando o pior caso de log ao quadrado.

Por intervalos de 32 bits, encontrei esta O(1)solução nos editoriais do Hacker Rank. Não tenho ideia de como funciona, mas funciona. (Talvez alguém possa explicar por que funciona.)

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

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