Um número inteiro positivo N é K- separado se houver pelo menos K 0s entre quaisquer dois 1s consecutivos em sua representação binária.

Portanto, o número 1010101 é 1-esparso, enquanto 101101 não é.

Sua tarefa é encontrar o próximo número 1 esparso para o número de entrada especificado. Por exemplo, se a entrada for 12 ( 0b1100), a saída deve ser 16 ( 0b10000) e se a entrada é 18 ( 0b10010), a saída deve ser 20 ( 0b10100).

O menor programa ou função (em bytes) vence! Lacunas padrão não permitidas.

Pitão, 9 bytes

• Tomando emprestado o x & (x*2) != 0algoritmo de @alephalpha
• Empréstimo Pythplate de @Jakube

Minha primeira tentativa em Pyth:

f!.&TyThQ

Experimente aqui

               implicit: Q = input()            
f      hQ      find the first integer T >= Q + 1, 
               that satisfies the condition:
 !.&TyT        T & (T * 2) is 0

CJam, 14 11 bytes

3 bytes salvos graças ao DigitalTrauma.

l~{)___+&}g

Teste aqui.

Explicação

l~          "Read and eval input.";
  {      }g "Do while...";
   )_       "Increment and duplicate (call this x).";
     __+    "Get two more copies and add them to get x and 2x on the stack.";
        &   "Take their bitwise AND. This is non-zero is as long as x's base-2
             representation contains '11'.";

Isso deixa o último número na pilha que é impresso automaticamente no final do programa.

Python 2, 44 bytes

Este é um programa python completo que lê n e imprime a resposta. Eu acho que se sai muito bem na subcompetição de legibilidade.

n=input()+1
while'11'in bin(n):n+=1
print n

Os resultados do teste:

$ echo 12 | python soln.py 
16
$ echo 18 | python soln.py 
20

Pitão, 12 11 bytes

f!}`11.BThQ

Experimente online: Pyth Compiler / Executor .

               implicit: Q = input()            
f        hQ    find the first integer T >= Q + 1, 
               that satisfies the condition:
 !}`11.BT         "11" is not in the binary representation of T

Mathematica, 41 30 bytes

Economizou 11 bytes graças a Martin Büttner.

#+1//.i_/;BitAnd[i,2i]>0:>i+1&

Perl, 31

#!perl -p
sprintf("%b",++$_)=~/11/&&redo

Ou na linha de comando:

 perl -pe'sprintf("%b",++$_)=~/11/&&redo' <<<"18"

APL, 18 bytes

1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2}

Isso avalia uma função monádica. Experimente aqui. Uso:

   1∘+⍣{~∨/2∧/⍺⊤⍨⍺⍴2} 12
16

Explicação

1∘+                    ⍝ Increment the input ⍺
   ⍣{            }     ⍝ until
     ~∨/               ⍝ none of
        2∧/            ⍝ the adjacent coordinates contain 1 1 in
           ⍺⊤⍨⍺⍴2      ⍝ the length-⍺ binary representation of ⍺.

J, 20 caracteres

Um verbo monádico. Corrigido para obedecer às regras.

(+1 1+./@E.#:)^:_@>:

Explicação

Primeiro, este é o verbo com espaços e depois um pouco menos jogado:

(+ 1 1 +./@E. #:)^:_@>:
[: (] + [: +./ 1 1 E. #:)^:_ >:

Ler:

    ]                             The argument
      +                           plus
        [: +./                    the or-reduction of
               1 1 E.             the 1 1 interval membership in
                      #:          the base-2 representation of the argument,
[: (                    )^:_      that to the power limit of
                             >:   the incremented argument

O argumento mais a redução ou redução da 1 1participação no intervalo na representação de base 2 do argumento, que é o limite de potência aplicado ao argumento incrementado.

Basicamente, calculo se 1 1ocorre na representação base-2 da entrada. Se isso acontecer, eu incremento a entrada. Isso é colocado sob um limite de potência, o que significa que é aplicado até que o resultado não mude mais.

Javascript, 25 19

Usando o fato de que, para um número binário 1-esparsa, x&2*x == 0:

f=x=>x++&2*x?f(x):x

JavaScript (ES6), 39 43

Sem regexp, sem strings, recursivo:

R=(n,x=3)=>x%4>2?R(++n,n):x?R(n,x>>1):n

Versão iterativa:

F=n=>{for(x=3;x%4>2?x=++n:x>>=1;);return n}

É muito simples, basta usar o shift direito para encontrar uma sequência de 11. Quando o encontrar, pule para o próximo número. A versão recursiva é diretamente derivada da iterativa.

Ungolfed e mais óbvio. Para o golfe, a parte mais complicada é mesclar os loops internos e externos (tendo que iniciar x a 3 no início)

F = n=>{
  do {
    ++n; // next number
    for(x = n; x != 0; x >>= 1) {
      // loop to find 11 in any position
      if ((x & 3) == 3) { // least 2 bits == 11
        break;
      }
    }
  } while (x != 0) // if 11 was found,early exit from inner loop and x != 0
  return n
}

Python 2, 37 bytes

f=input()+1
while f&2*f:f+=1
print f

Utilizou a lógica x & 2*x == 0do número 1 esparso.
Graças a @Nick e @CarpetPython.

JavaScript, 75 66 62 bytes

Agradecemos a Martin Büttner por salvar 9 bytes e a Pietu1998 por 4 bytes!

function n(a){for(a++;/11/.test(a.toString(2));a++);return a;}

Como funciona: executa um forloop a + 1desde que o número atual não seja 1 esparso e, se for, o loop é interrompido e retorna o número atual. Para verificar se um número é 1 esparso, ele o converte em binário e verifica se ele não contém 11.

Código não golfe:

function nextOneSparseNumber(num) {
    for (num++; /11/.test(num.toString(2)); num++);
    return num;
}

Julia, 40 bytes

n->(while contains(bin(n+=1),"11")end;n)

Isso cria uma função anônima que aceita um único número inteiro como entrada e retorna o próximo número inteiro 1 esparso mais alto. Para chamá-lo, dê um nome, por exemplo f=n->..., e façaf(12) .

Ungolfed + explicação:

function f(n)

    # While the string representation of n+1 in binary contains "11",
    # increment n. Once it doesn't, we've got the answer!

    while contains(bin(n += 1), "11")
    end

    return(n)
end

Exemplos:

julia> f(12)
16

julia> f(16)
20

Sugestões e / ou perguntas são bem-vindas, como sempre!

> <> (Peixe) , 31 + 3 = 34 bytes

1+:>:  4%:3(?v~~
;n~^?-1:,2-%2<

Uso:

>python fish.py onesparse.fish -v 12
16

3 bytes adicionados para o -vsinalizador.

JavaScript (ECMAScript 6), 40

Por recursão:

g=x=>/11/.test((++x).toString(2))?g(x):x

JavaScript, 56

Mesmo sem funções de seta.

function f(x){return/11/.test((++x).toString(2))?f(x):x}

Scala, 65 bytes

(n:Int)=>{var m=n+1;while(m.toBinaryString.contains("11"))m+=1;m}

(se uma função nomeada for necessária, a solução será 69 bytes)

Python, 39 33 bytes

Experimente aqui: http://repl.it/gpu/2

Na forma lambda (graças ao xnor para jogar golfe):

f=lambda x:1+x&x/2and f(x+1)or-~x

A sintaxe da função padrão acabou sendo mais curta que uma lambda pela primeira vez!

def f(x):x+=1;return x*(x&x*2<1)or f(x)

Java, 33 bytes.

Usa o método nesta resposta

n->{for(;(n++&2*n)>0;);return n;}

TIO

Ruby, 44

->(i){loop{i+=1;break if i.to_s(2)!~/11/};i}

Bastante básico. Um lambda com um loop infinito e uma regexp para testar a representação binária. Eu gostaria que esse loopnúmero rendesse e índice.

Matlab ( 77 74 bytes)

m=input('');for N=m+1:2*m
if ~any(regexp(dec2bin(N),'11'))
break
end
end
N

Notas:

• Basta testar números m+1para 2*m, onde mestá a entrada.
• ~any(x)é truese xcontém todos os zeros ou se xestá vazio

C (32 bytes)

f(int x){return 2*++x&x?f(x):x;}

Implementação recursiva do mesmo algoritmo que muitas outras respostas.

Perl, 16 bytes

Combinando as x&2*xrespostas de várias (acho que o primeiro de Nick ) com os redo rendimentos de nutki :

perl -pe'++$_&2*$_&&redo'

Testado em morango 5.26.

Japonês, 8 bytes

_&ZÑ}fUÄ

Execute-o online.

Geléia , 7 bytes

‘&Ḥ¬Ɗ1#

Um programa completo que aceita um número inteiro único e não negativo que imprime um número inteiro positivo (como um link monádico, gera uma lista contendo um único número inteiro positivo).

Experimente online!

Quão?

Começando em v=n+1e incrementando, duplique vpara mudar cada bit para cima um lugar e bit a bit AND com ve, em seguida, execute NOT lógico para testar se vé 1 esparso até que um desses números seja encontrado.

‘&Ḥ¬Ɗ1# - Main Link: n   e.g. 12
‘       - increment           13
     1# - 1-find (start with that as v and increment until 1 match is found) using:
    Ɗ   -   last three links as a dyad:
  Ḥ     -   double v
 &      -   (v) bit-wise AND (with that)
   ¬    -   logical NOT (0->1 else 1)
        - implicit print (a single item list prints as just the item would)

Stax , 5 bytes

╦>ù╤x

Execute e depure

Funciona usando este procedimento. A entrada começa no topo da pilha.

• Incremente e copie duas vezes.
• Metade da parte superior da pilha.
• Bitwise e os dois principais elementos da pilha.
• Se o resultado for verdadeiro (diferente de zero), repita o programa inteiro.