Un entier positif N est K -sparse s'il y a au moins K 0 entre deux quelconques 1 consécutifs dans sa représentation binaire.

Ainsi, le nombre 1010101 est 1-clairsemé alors que 101101 ne l'est pas.

Votre tâche consiste à trouver le prochain numéro 1-sparse pour le numéro d'entrée donné. Par exemple, si l'entrée est 12 ( 0b1100), la sortie doit être 16 ( 0b10000) et si l'entrée est 18 ( 0b10010), la sortie doit être 20 ( 0b10100).

Le plus petit programme ou fonction (en octets) gagne! Failles standard interdites.

Pyth, 9 octets

• Emprunter l' x & (x*2) != 0algorithme de @alephalpha
• Plaque d' emprunt Pyth de @Jakube

Ma première tentative sur Pyth:

f!.&TyThQ

Essayez-le ici

               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 octets

3 octets économisés grâce à DigitalTrauma.

l~{)___+&}g

Testez-le ici.

Explication

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'.";

Cela laisse le dernier numéro sur la pile qui est imprimé automatiquement à la fin du programme.

Python 2, 44 octets

Il s'agit d'un programme python complet qui lit en n et imprime la réponse. Je pense que cela fonctionne très bien dans la sous-compétition de lisibilité.

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

Les résultats des tests:

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

Pyth, 12 11 octets

f!}`11.BThQ

Essayez-le en ligne: 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 octets

Sauvegardé 11 octets grâce à Martin Büttner.

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

Perl, 31

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

Ou depuis la ligne de commande:

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

APL, 18 octets

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

Cela équivaut à une fonction monadique. Essayez-le ici. Usage:

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

Explication

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

J, 20 caractères

Un verbe monadique. Correction d'obéir aux règles.

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

Explication

D'abord, c'est le verbe avec des espaces puis un peu moins golfé:

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

Lis:

    ]                             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

L'argument plus la réduction or de l' 1 1appartenance à l' intervalle dans la représentation de base 2 de l'argument, cela à la limite de puissance appliquée à l'argument incrémenté.

Je calcule essentiellement si 1 1se produit dans la représentation de base 2 de l'entrée. Si c'est le cas, j'incrémente l'entrée. Ceci est placé sous une limite de puissance, ce qui signifie qu'il est appliqué jusqu'à ce que le résultat ne change plus.

Javascript, 25 19

En utilisant le fait que, pour un nombre binaire 1-clairsemée, x&2*x == 0:

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

JavaScript (ES6), 39 43

Pas d'expression régulière, pas de chaînes, récursif:

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

Version itérative:

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

C'est très simple, il suffit d'utiliser le décalage vers la droite pour trouver une séquence de 11. Lorsque je la trouve, passez au numéro suivant. La version récursive est directement dérivée de la version itérative.

Non golfé et plus évident. Pour jouer au golf, la partie la plus délicate est de fusionner les boucles intérieure et extérieure (avoir à initier x à 3 au début)

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 octets

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

Utilisé la logique x & 2*x == 0pour un nombre à 1 fragment.
Merci à @Nick et @CarpetPython.

JavaScript, 75 66 62 octets

Merci à Martin Büttner pour avoir économisé 9 octets et Pietu1998 pour 4 octets!

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

Comment ça marche: il exécute une forboucle à partir du a + 1moment où le nombre actuel n'est pas 1-sparse, et si c'est le cas, la boucle est interrompue et il retourne le nombre actuel. Pour vérifier si un nombre est 1-sparse, il le convertit en binaire et vérifie s'il ne contient pas 11.

Code non golfé:

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

Julia, 40 octets

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

Cela crée une fonction anonyme qui accepte un seul entier en entrée et retourne le prochain entier à 1 segment le plus élevé. Pour l'appeler, donnez-lui un nom, par exemple f=n->..., et faites f(12).

Non golfé + explication:

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

Exemples:

julia> f(12)
16

julia> f(16)
20

Les suggestions et / ou questions sont les bienvenues comme toujours!

> <> (Poisson) , 31 + 3 = 34 octets

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

Usage:

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

3 octets ajoutés pour le -vdrapeau.

JavaScript (ECMAScript 6), 40

Par récursivité:

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

JavaScript, 56

Idem sans fonctions fléchées.

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

Scala, 65 octets

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

(si une fonction nommée est requise, la solution sera de 69 octets)

Python, 39 33 octets

Essayez-le ici: http://repl.it/gpu/2

Sous forme lambda (merci à xnor pour le golf):

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

La syntaxe de fonction standard s'est avérée être plus courte qu'une lambda pour une fois!

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

Java, 33 octets.

Utilise la méthode dans cette réponse

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

TIO

Rubis, 44

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

Assez basique. Un lambda avec une boucle infinie et une expression rationnelle pour tester la représentation binaire. Je souhaite que loopcédé et numéro d'index.

Matlab ( 77 74 octets)

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

Remarques:

• Il suffit de tester les nombres m+1à 2*m, où mest l'entrée.
• ~any(x)est truesi xcontient tous les zéros ou si xest vide

C (32 octets)

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

Implémentation récursive du même algorithme que tant d'autres réponses.

Perl, 16 octets

Combiner les x&2*xdifférentes réponses (je pense que la première de Nick ) avec les redo rendements de nutki :

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

Testé dans Strawberry 5.26.

Japt, 8 octets

_&ZÑ}fUÄ

Exécutez-le en ligne.

Gelée , 7 octets

‘&Ḥ¬Ɗ1#

Un programme complet acceptant un seul entier non négatif qui imprime un entier positif (en tant que lien monadique, il donne une liste contenant un seul entier positif).

Essayez-le en ligne!

Comment?

En commençant par v=n+1, et en incrémentant, doublez vpour déplacer chaque bit vers le haut à un endroit et bit par bit ET avec v, puis effectuez une opération logique NON pour tester s'il vest à 1 fragment jusqu'à ce qu'un de ces nombres soit trouvé.

‘&Ḥ¬Ɗ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 octets

╦>ù╤x

Exécuter et déboguer

Cela fonctionne en utilisant cette procédure. L'entrée commence au sommet de la pile.

• Incrémentez et copiez deux fois.
• Réduisez de moitié le haut de la pile.
• Au niveau du bit et des deux éléments supérieurs de la pile.
• Si le résultat est véridique (non nul), répétez tout le programme.