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

14

Suponha que nós estamos dando dois números e e que queremos encontrar para l \ le i, \, j \ le r .lr l i ,max(ij)li,jr

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?

Jacopo Notarstefano
fonte
Você deve deixar jpassar i+1..re ipassar l...r-1para ser preciso.
Ahmet Alp Balkan

Respostas:

20

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

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 0plr0

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 | - 1r>l1r0lp10n|p|1p01n|p|1

Portanto, o máximo que estamos procurando é .0|p|1n|p|

FrankW
fonte
1
Bem, isso foi fácil! Acho que deveria ter pensado mais neste problema.
Jacopo Notarstefano 30/08/14
O acionador de linha pediu "melhor que quadrático nos números". Como é linear no tamanho dos números, é logarítmico nos próprios números.
gnasher729
18

É possível fazê-lo no tempo .O(registror)

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 2[eu,r]eureu,r2p-1p é maior que l r . 2peur

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;
}
ysb.4
fonte
Você pode explicar a lógica por trás desse algoritmo?
Sk1pro99
Este vídeo pode ajudá-lo: youtube.com/watch?v=3j-ok4gMjXU
Jack Kinsella
0

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
noman pouigt
fonte
0

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 n -1, portanto, a resposta neste caso será 2 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 = lr

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 n −1

Complexidade temporal = O (n)

UjjwalAyyangar
fonte
-1

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.

Ben Rayfield
fonte
1
Não sei ao certo o que você quer dizer com "dígito inferior", "log-desaparece pequeno" ou "isso ... significa o pior caso de log ao quadrado". Você poderia esclarecer?
David Richerby
-1

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

Ahmet Alp Balkan
fonte
2
Como sua resposta (após a correção) difere da do ysb.4 (além de ele explicar o que está acontecendo)? O que 'return b' faz com o 'b' não declarado? Desculpe, mas não consigo acessar o link que você forneceu.
Mal