Dado um inteiro de 64 bits sem sinal y
, existe uma maneira eficiente de encontrar todos os inteiros de 64 bits sem sinal x
tais que
(x & (x + y)) == 0
?
Alguns exemplos para pequenos y
:
y=0
: única solução possívelx=0
y=1
: todas as soluções são da formax=(1<<n)-1
para algum n>=0y=2
: todas as soluções são da formax=(1<<n)-2
para algum n>=1y=3
: oux=(1<<n)-3
, n>=2, oux=(1<<n)-2
, n>=1
Em geral, o número de casos a serem considerados depende do número de execuções de uns e zeros na representação de bits de y
.
Uma solução para o problema poderia ser uma função iteradora, que encontra o próximo válido x
, como o seguinte:
uint64 next(uint64 x, uint64 y) {
x++;
while (x & (x+y)) x++;
return x;
}
Como o critério (x & (x + y)) == 0
é bastante simples, esse pode ser um problema conhecido para o qual existe uma solução mais eficiente do que a acima.
Para qualquer dado
y
, sex
é uma solução, então todo sufixo dex
, incluindo0
, também é uma solução.Se você organizar os inteiros de 64 bits em uma árvore de modo que o pai de cada nó seja um sufixo formado pela desativação do bit 1 mais alto, então as soluções corresponderão a uma subárvore com raiz em 0, e você poderá enumerá-las percorrendo essa árvore.
Trabalhando a partir da raiz, então, se tivermos uma solução
x
, então precisamos encontrar os novos bits mais altos que poderíamos definir que também produzem soluções válidas. Esses são convenientemente exatamente os1
bits emx+y
que são maiores quex
. Eles podem ser enumerados eficientemente, levando a uma solução recursiva eficiente.Aqui está uma implementação em python. Você pode transformá-la em um iterador se quiser: