Wprowadzenie

To wyzwanie wymaga ustawienia zer końcowych reprezentacji binarnej liczb całkowitych na 010101…, najlepiej to wyjaśnić na przykładzie:

Biorąc pod uwagę liczbę całkowitą 400, pierwszym krokiem jest konwersja do postaci binarnej:

110010000

Jak widzimy, piąty bit jest najmniej znaczący 1, więc zaczynając od tego, zamieniamy dolne zera na 0101:

110010101

Na koniec konwertujemy to z powrotem na dziesiętne: 405

Wyzwanie

Biorąc pod uwagę dodatni zwrot / wyjście liczb całkowitych, odpowiednią wynikową wartość wyżej zdefiniowanego procesu.

Zasady

• Ta sekwencja jest zdefiniowana tylko dla liczb całkowitych z co najmniej jednym 1bitem, więc wejście zawsze będzie ≥ 1
• Zamiast tego możesz traktować dane wejściowe jako ciąg znaków, listę cyfr (dziesiętną)
• Nie musisz obsługiwać nieprawidłowych danych wejściowych

Przypadki testowe

Oto kilka przypadków testowych z krokami pośrednimi (nie musisz ich drukować / zwracać):

In -> … -> … -> Out
1 -> 1 -> 1 -> 1
2 -> 10 -> 10 -> 2
3 -> 11 -> 11 -> 3
4 -> 100 -> 101 -> 5
24 -> 11000 -> 11010 -> 26
29 -> 11101 -> 11101 -> 29
32 -> 100000 -> 101010 -> 42
192 -> 11000000 -> 11010101 -> 213
400 -> 110010000 -> 110010101 -> 405
298 -> 100101010 -> 100101010 -> 298

Python 3 , 20 bajtów

lambda n:(n&-n)//3+n

Wypróbuj online!

Wyjaśnienie

Weź 192jako przykład. Jego forma binarna jest 11000000i musimy ją przekonwertować 11010101.

Zauważamy, że musimy dodać 10101do numeru. Jest to seria geometryczna ( 4^0 + 4^1 + 4^2), która ma postać zamkniętą jako (4^3-1)/(4-1). Jest to to samo, co 4^3//3gdzie //oznacza podział na liczby całkowite.

Gdyby tak było 101010, nadal byłby to szereg geometryczny ( 2×4^0 + 2×4^1 + 2×4^2), co wynika 2×4^3//3z powyższych powodów.

W każdym razie, 4^3i 2×4^3po prostu być najmniej znaczącego bitu, który uzyskujemy poprzez n&-n:

Zauważamy, że uzupełnieniem njest 00111111. Jeśli dodamy jeden, staje się 01000000i nakłada się tylko n=11000000na co najmniej znaczącą cyfrę. Zauważ, że „uzupełnij i dodaj jeden” to tylko negacja.

Galaretka , 5 bajtów

&N:3+

Wypróbuj online!

Tym razem port podejścia Leaky Nun (przynajmniej pomogłem mu trochę w golfa: P)

Galaretka , 7 bajtów

^N+4:6ạ

Wypróbuj online!

Wykorzystuje fantastyczne podejście JungHwan Min , z pośrednią pomocą Martina Endera .

Wolfram Language (Mathematica) , 36 28 26 24 bajtów

^{-8 bajtów dzięki @MartinEnder i -2 bajtów dzięki @ Mr.Xcoder}

#+⌊(#~BitAnd~-#)/3⌋&

Wypróbuj online!

Musimy tylko znaleźć liczbę zer końcowych na wejściu i znaleźć liczbę z naprzemiennymi 0si i 1s o długości mniejszej niż ta, i dodać ją do wejścia.

Więc, 400 -> 11001000 -> 110010000 + 0000 -> 110010101 + 101 -> 405

Wyraźny wzór na nliczbę th z naprzemiennymi 1si i 0s podano w A000975 na OEIS. Możemy użyć ntej liczby, ponieważ żadne dwie różne liczby nie mogą mieć tej samej długości w systemie binarnym i mieć na przemian cyfry.

J , ₁₉ 18 bajtów

+(2|-.i.@#.-.)&.#:

Wypróbuj online!

Szybkie wyjaśnienie

To stara odpowiedź, ale z natury jest bardzo podobna do obecnej, po prostu inaczej zlicza końcowe zera. Zobacz komentarze do linku wyjaśniającego, jak to działa.

+(2|i.@i.&1@|.)&.#:
                 #:  Convert to binary list
       i.&1@|.       Index of last 1 from right
            |.         Reverse
       i.&1            Index of first 1
    i.               Range [0, index of last 1 from right)
  2|                 That range mod 2
               &.    Convert back to decimal number
+                    Add to the input

Inne odpowiedzi:

Poprzednia odpowiedź (19 bajtów).

+(2|i.@i.&1@|.)&.#:

Dłuższy niż powinien być, ponieważ \biegnie od prawej do lewej.

+(2|#*-.#.-.)\&.(|.@#:)

Julia 0.6 , 12 bajtów

!n=n|n&-n÷3

Wypróbuj online!

JavaScript (ES6), 40 39 bajtów

Pobiera dane wejściowe jako 32-bitową liczbę całkowitą.

n=>n|((n&=-n)&(m=0xAAAAAAAA)?m:m/2)&--n

Przypadki testowe

let f =

n=>n|((n&=-n)&(m=0xAAAAAAAA)?m:m/2)&--n

console.log(f(1))   // 1 -> 1 -> 1
console.log(f(2))   // 10 -> 10 -> 2
console.log(f(3))   // 11 -> 11 -> 3
console.log(f(4))   // 100 -> 101 -> 5
console.log(f(24))  // 11000 -> 11010 -> 26
console.log(f(29))  // 11101 -> 11101 -> 29
console.log(f(32))  // 100000 -> 101010 -> 42
console.log(f(192)) // 11000000 -> 11010101 -> 213
console.log(f(400)) // 110010000 -> 110010101 -> 405
console.log(f(298)) // 100101010 -> 100101010 -> 298

05AB1E , 13 8 5 bajtów

Zaoszczędź 5 bajtów dzięki panu Xcoderem i zgrabnej formule JungHwan Min Oszczędź
kolejne 3 dzięki panu Xcoderem

(&3÷+

Wypróbuj online!

Wyjaśnienie

(      # negate input
 &     # AND with input
  3÷   # integer divide by 3
    +  # add to input

R , 71 58 bajtów

dzięki NofP za -6 bajtów

function(n){n=n%/%(x=2^(0:31))%%2
n[!cumsum(n)]=1:0
n%*%x}

Wypróbuj online!

Zakłada, że ​​wejście jest 32-bitową liczbą całkowitą. R i tak ma tylko 32-bitowe liczby całkowite (rzutowanie do, doublegdy liczba całkowita się przepełnia) i tak nie ma 64-bitowych lub niepodpisanych liczb całkowitych.

pieprzenie mózgu , 120 bajtów

>+<[[>-]++>[[>]>]<[>+>]<[<]>-]>[-<+>[-<[<]<]>]>[>]<[>+<[->+<]<[->+<]<]>>[<]+>[-[-<[->+<<+>]>[-<+>]]<[->++<]<[->+<]>>>]<<

Wypróbuj online!

Zaczyna się od wartości w bieżącej komórce, a kończy na komórce wartością wyjściową. Oczywiście nie zadziała na liczbach powyżej 255, ponieważ jest to limit komórek dla typowego pieprzenia mózgu, ale zadziała, jeśli założymy nieskończony rozmiar komórki.

PowerShell , 168 bajtów

param($n)$a=($c=[convert])::ToString($n,2);if(($x=[regex]::Match($a,'0+$').index)-gt0){$c::ToInt32(-join($a[0..($x-1)]+($a[$x..$a.length]|%{(0,1)[$i++%2]})),2)}else{$n}

Wypróbuj online!

Auć. Konwersja do / z krojenia binarnego i tablicowego nie jest tak naprawdę mocną stroną PowerShell.

Pobiera dane wejściowe $njako liczbę. Natychmiast przekazujemy convertto do bazy binarnej 2i przechowujemy w $a. Następnie mamy konstrukcję if / else. Klauzula if sprawdza, czy wartość regex Matchprzeciw 1 lub więcej 0s na końcu łańcucha ( '0+$') ma swoją indexlokalizację większą niż 0(tj. Początek łańcucha binarnego). Jeśli tak, to mamy z czym pracować, elsepo prostu wypisujemy liczbę.

Wewnątrz wycinamy pierwsze cyfry i ifłączymy xtablice +z pozostałymi cyframi. Jednak w przypadku pozostałych cyfr przeglądamy je i wybieramy albo a, 0albo 1zamiast niego, używając $i++%2do wyboru. To daje nam 010101...wzór zamiast 0s na końcu. Następnie łączymy to z powrotem w -joinciąg i $cprzekształcamy z powrotem w Int32bazę 2.

W obu przypadkach liczba pozostawia się w potoku, a dane wyjściowe są niejawne.

APL + WIN, 43 bajty

p←+/^\⌽~n←((⌊1+2⍟n)⍴2)⊤n←⎕⋄2⊥((-p)↓n),p⍴0 1

Monity o wprowadzenie ekranu

PowerShell , 41 36 bajtów

param($n)$n+(($x=$n-band-$n)-$x%3)/3

Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe

Port Dziurawy zakonnicy Python odpowiedź .

Zaoszczędź 5 bajtów dzięki Leaky Nun

PHP , 47 bajtów

<?php function b($a){echo(int)(($a&-$a)/3)+$a;}

Wypróbuj online!

Naprawdę tylko kolejny port rozwiązania @Leaky Nun

Perl 5 , 54 bajtów

$_=sprintf'%b',<>;1while s/00(0*)$/01$1/;say oct"0b$_"

Wypróbuj online!

Python 3 , 56 bajtów

lambda n:eval((bin(n).rstrip("0")+"01"*n)[:len(bin(n))])

Wypróbuj online!

Jeszcze nie bardzo z tego zadowolony, ale tak naprawdę nie chciałem używać formuły ... -2 dzięki Rod . -1 dzięki Jonathan Frech .

Rubin , 15 bajtów

Kolejny port podejścia Dziurawej Zakonnicy.

->k{(k&-k)/3+k}

Wypróbuj online!

Rdza , 18 bajtów

Port podejścia Dziurawej Zakonnicy

|n:i32|(n&-n)/3+n;

Wypróbuj online!

AWK , 24 bajty

Port odpowiedzi Mathmatica autorstwa JungHwan Min

$0=int(and($0,-$0)/3+$0)

Wypróbuj online!

JavaScript ES6, 13 bajtów

n=>(n&-n)/3|n

f = 
n=>(n&-n)/3|n
;
console.log (f(8));
console.log (f(243));
console.log (f(1048576));
console.log (f(33554432));

C, 56 bajtów

i,k;f(n){for(k=i=1;n>>i<<i==n;k+=++i&1)k*=2;return n|k;}

Wypróbuj online!

C (gcc), 50 bajtów

i,k;f(n){for(k=i=1;n>>i<<i==n;k+=++i&1)k*=2;k|=n;}

Wypróbuj online!

 51  48 bajtów przy użyciu rozwiązania Arnauld :

Dzięki @ l4m2 za oszczędność trzech bajtów!

m;f(n){return n|((n&-n)&(m=-1u/3*2)?m:m/2)&n-1;}

Wypróbuj online!

43 z gcc:

m;f(n){m=n|((n&-n)&(m=-1u/3*2)?m:m/2)&n-1;}

Wypróbuj online!

Pari / GP , 19 bajtów

Port podejścia Dziurawej Zakonnicy.

n->n+bitand(n,-n)\3

Wypróbuj online!

Galaretka , 13 bajtów

BŒgṪµ2Ḷṁ×CḄ+³

Wypróbuj online!

Wyjaśnienie

Weź 24 jako przykładowe dane wejściowe.

BŒgṪµ2Ḷṁ×CḄ+³
B                Binary representation of the input → 11000
 Œg              Group runs of equal length → [[1,1],[0,0,0]]
   Ṫ             Tail → [0,0,0]
    µ            New monadic link
     2Ḷ          [0,1] constant
       ṁ         Mold [0,1] to the shape of [0,0,0] → [0,1,0]
        ×        Multiply [0,1,0] by...
         C       1-[0,0,0]. If last bit(s) of the original input are 1 this will add nothing to the original input
          Ḅ      Convert to decimal from binary → 2
           +³    Add this with the original input → 26