Dado um inteiro de 64 bits sem sinal y, existe uma maneira eficiente de encontrar todos os inteiros de 64 bits sem sinal xtais que
(x & (x + y)) == 0?
Alguns exemplos para pequenos y:
y=0: única solução possívelx=0y=1: todas as soluções são da formax=(1<<n)-1para algum n>=0y=2: todas as soluções são da formax=(1<<n)-2para 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.