Dodatnia liczba całkowita N to rzadka K, jeśli w jej reprezentacji binarnej występują co najmniej K 0 między dowolnymi dwoma kolejnymi 1.

Tak więc liczba 1010101 jest 1-rzadka, podczas gdy 101101 nie.

Twoim zadaniem jest znalezienie następnego 1-rzadkiego numeru dla podanego numeru wejściowego. Na przykład, jeśli wejście to 12 ( 0b1100), wyjście powinno wynosić 16 ( 0b10000), a jeśli wejście to 18 ( 0b10010), wyjście powinno wynosić 20 ( 0b10100).

Najmniejszy program lub funkcja (w bajtach) wygrywa! Standardowe luki zabronione.

Pyth, 9 bajtów

• Pożyczanie x & (x*2) != 0algorytmu od @alephalpha
• Wypożyczenie płyty kotła Pyth od @Jakube

Moja pierwsza próba w Pyth:

f!.&TyThQ

Wypróbuj tutaj

               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 bajtów

3 bajty zapisane dzięki DigitalTrauma.

l~{)___+&}g

Sprawdź to tutaj.

Wyjaśnienie

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

Pozostawia to ostatnią liczbę na stosie, która jest drukowana automatycznie na końcu programu.

Python 2, 44 bajty

Jest to kompletny program pythonowy, który czyta in, i drukuje odpowiedź. Myślę, że radzi sobie całkiem nieźle w konkursie na czytelność.

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

Wyniki testu:

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

Pyth, 12 11 bajtów

f!}`11.BThQ

Wypróbuj 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 bajtów

Zaoszczędzono 11 bajtów dzięki Martinowi Büttnerowi.

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

Perl, 31

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

Lub z wiersza poleceń:

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

APL, 18 bajtów

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

To ocenia na funkcję monadyczną. Wypróbuj tutaj. Stosowanie:

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

Wyjaśnienie

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

J, 20 znaków

Czasownik monadyczny. Naprawiono, aby przestrzegać zasad.

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

Wyjaśnienie

Po pierwsze, jest to czasownik ze spacjami, a następnie trochę mniej golfowy:

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

Czytać:

    ]                             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

Argument plus redukcja 1 1członkostwa przedziałowego w reprezentacji argumentu base-2 argumentu, że do limitu mocy stosowanego do przyrostowego argumentu.

Zasadniczo obliczam, jeśli 1 1występuje w reprezentacji wejścia base-2. Jeśli tak, zwiększam dane wejściowe. Jest to objęte limitem mocy, co oznacza, że ​​jest stosowane, dopóki wynik się nie zmieni.

JavaScript, 25 19

Korzystając z faktu, że dla 1-rzadkiej liczby binarnej x&2*x == 0:

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

JavaScript (ES6), 39 43

Bez wyrażeń regularnych, bez ciągów, rekurencyjne:

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

Wersja iteracyjna:

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

To bardzo proste, wystarczy użyć prawego klawisza Shift, aby znaleźć sekwencję 11. Kiedy ją znajdę, przejdź do następnej liczby. Wersja rekurencyjna pochodzi bezpośrednio z wersji iteracyjnej.

Bez golfa i bardziej oczywiste. Aby zagrać w golfa, najtrudniejszą częścią jest połączenie wewnętrznej i zewnętrznej pętli (początkowe uruchomienie x do 3)

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 bajtów

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

Zastosowano logikę x & 2*x == 0dla liczby 1-rzadkiej.
Dzięki @Nick i @CarpetPython.

JavaScript, 75 66 62 bajtów

Dzięki Martin Büttner za oszczędność 9 bajtów i Pietu1998 za 4 bajty!

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

Jak to działa: uruchamia forpętlę, zaczynając od a + 1tak długo, jak długo bieżący numer nie jest 1-rzadki, a jeśli tak, pętla jest przerywana i zwraca bieżącą liczbę. Aby sprawdzić, czy liczba jest 1-rzadka, konwertuje ją na binarną i sprawdza, czy nie zawiera 11.

Kod bez golfa:

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

Julia, 40 bajtów

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

Tworzy to anonimową funkcję, która przyjmuje jedną liczbę całkowitą jako dane wejściowe i zwraca następną najwyższą liczbę całkowitą 1-rzadką. Aby to nazwać, nadaj mu nazwę, np. f=n->...I zrób f(12).

Niegolfowane + wyjaśnienie:

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

Przykłady:

julia> f(12)
16

julia> f(16)
20

Sugestie i / lub pytania są jak zawsze mile widziane!

> <> (Ryba) , 31 + 3 = 34 bajty

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

Stosowanie:

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

Dodano 3 bajty dla -vflagi.

JavaScript (ECMAScript 6), 40

Według rekurencji:

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

JavaScript, 56

To samo bez funkcji strzałek.

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

Scala, 65 bajtów

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

(jeśli wymagana jest funkcja o nazwie, rozwiązanie będzie 69 bajtów)

Python, 39 33 bajty

Wypróbuj tutaj: http://repl.it/gpu/2

W formie lambda (dzięki xnor do gry w golfa):

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

Standardowa składnia funkcji okazała się raz krótsza niż lambda!

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

Java, 33 bajty.

Używa metody z tej odpowiedzi

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

TIO

Ruby, 44

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

Całkiem proste. Lambda z nieskończoną pętlą i wyrażeniem regularnym do testowania reprezentacji binarnej. Życzę, aby loopuzyskany i numer indeksu.

Matlab ( 77 74 bajtów)

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

Uwagi:

• Wystarczy przetestować liczby m+1do 2*m, gdzie mjest wejście.
• ~any(x)jest, truejeśli xzawiera wszystkie zera lub jeśli xjest pusty

C (32 bajty)

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

Rekurencyjna implementacja tego samego algorytmu, jak wielu innych odpowiedzi.

Perl, 16 bajtów

Łącząc x&2*xróżne odpowiedzi (myślę, że Nick jest pierwszy) z wynikami nutki redo :

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

Testowany w Truskawce 5.26.

Japt, 8 bajtów

_&ZÑ}fUÄ

Uruchom to online.

Galaretka , 7 bajtów

‘&Ḥ¬Ɗ1#

Pełny program akceptujący jedną, nieujemną liczbę całkowitą, która wypisuje dodatnią liczbę całkowitą (jako łącze monadyczne daje listę zawierającą jedną dodatnią liczbę całkowitą).

Wypróbuj online!

W jaki sposób?

Zaczynając od v=n+1i zwiększając, dwukrotnie, vaby przesunąć każdy bit w górę o jedno miejsce i bitowo ORAZ za pomocą, va następnie wykonać logiczne NIE, aby sprawdzić, czy vjest 1-rzadki, dopóki nie zostanie znaleziona jedna taka liczba.

‘&Ḥ¬Ɗ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 bajtów

╦>ù╤x

Uruchom i debuguj

Działa przy użyciu tej procedury. Dane wejściowe zaczynają się na szczycie stosu.

• Zwiększ i skopiuj dwa razy.
• Zmniejsz połowę stosu.
• Bitowe i górne dwa elementy na stosie.
• Jeśli wynik jest prawdziwy (niezerowy), powtórz cały program.