zainspirowany Countdown from Infinity

Biorąc pod uwagę nieujemną liczbę całkowitą N, wypisz liczbę powtórzeń następujących kroków, aby osiągnąć 0:

1. Konwertuj Nna binarny ( 4812390 -> 10010010110111001100110)
2. Odwróć każdy bit ( 10010010110111001100110 -> 01101101001000110011001)
3. Przycinanie zer wiodących ( 01101101001000110011001 -> 1101101001000110011001)
4. Konwertuj z powrotem na dziesiętny ( 1101101001000110011001 -> 3576217)

Zasady

• Dane wejściowe i wyjściowe mogą być w dowolnym jednoznacznym, spójnym formacie
• Dane wejściowe będą znajdować się w natywnym reprezentatywnym zakresie liczb całkowitych dla Twojego języka (jeśli Twój język obsługuje dowolnie duże liczby całkowite, nie ma żadnych ograniczeń)

Przypadki testowe

0 -> 0
1 -> 1
42 -> 6
97 -> 3
170 -> 8
255 -> 1
682 -> 10
8675309 -> 11
4812390 -> 14
178956970 -> 28
2863311530 -> 32

Ta sekwencja to A005811 w OEIS.

Galaretka , 6 4 bajtów

^HBS

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Niech n będzie liczbą całkowitą nieujemną.

Kroki 2 i 3 procesu opisanego w specyfikacji można alternatywnie określić jako usunięcie wszystkich wiodących 1 i przełączenie pozostałych bitów.

Oznacza to, że usuniemy dokładnie jedną grupę sąsiednich i równych cyfr binarnych w każdej iteracji, więc Binary Countdown Length n to tylko liczba tych grup w binarnej reprezentacji n . Na potrzeby tego wyzwania pomyśl o 0 jako bez cyfr.

Dla n = 8675309 proces wygląda binarnie w następujący sposób.

100001000101111111101101
 11110111010000000010010
     1000101111111101101
      111010000000010010
         101111111101101
          10000000010010
           1111111101101
                   10010
                    1101
                      10
                       1
                       0

Zamiast zliczać te grupy (co mogłoby się nie powieść w przypadku 0 krawędzi ), wykonujemy następujące czynności.

n i n: 2 mają następujące reprezentacje binarne.

n   = 8675309 = 100001000101111111101101_2
n:2 = 4337654 =  10000100010111111110110_2

Zauważ, że binarna reprezentacja n: 2 to po prostu n , przesunięta o jeden bit w lewo.

Jeśli XOR n i n: 2 , otrzymamy 1 (MSB) i dodatkowy 1 dla każdej pary różnych sąsiadujących cyfr. Liczba grup jest więc równa liczbie ustawionych bitów w n ⊻ n: 2 .

Jak to działa

^HBS  Main link. Argument: n

 H    Halve; yield n:2.
^     XOR n with n:2.
  B   Convert the result to binary.
   S  Compute the sum of the resulting binary digits.

Python 2, 30 bajtów

lambda n:bin(n^n/2).count('1')

Przetestuj na Ideone .

tło

Niech n będzie liczbą całkowitą nieujemną.

Kroki 2 i 3 procesu opisanego w specyfikacji można alternatywnie określić jako usunięcie wszystkich wiodących 1 i przełączenie pozostałych bitów.

Oznacza to, że usuniemy dokładnie jedną grupę sąsiednich i równych cyfr binarnych w każdej iteracji, więc Binary Countdown Length n to tylko liczba tych grup w binarnej reprezentacji n . Na potrzeby tego wyzwania pomyśl o 0 jako bez cyfr.

Dla n = 8675309 proces wygląda binarnie w następujący sposób.

100001000101111111101101
 11110111010000000010010
     1000101111111101101
      111010000000010010
         101111111101101
          10000000010010
           1111111101101
                   10010
                    1101
                      10
                       1
                       0

Zamiast zliczać te grupy (co mogłoby się nie powieść w przypadku 0 krawędzi ), wykonujemy następujące czynności.

n i n: 2 mają następujące reprezentacje binarne.

n   = 8675309 = 100001000101111111101101_2
n:2 = 4337654 =  10000100010111111110110_2

Zauważ, że binarna reprezentacja n: 2 to po prostu n , przesunięta o jeden bit w lewo.

Jeśli XOR n i n: 2 , otrzymamy 1 (MSB) i dodatkowy 1 dla każdej pary różnych sąsiadujących cyfr. Liczba grup jest więc równa liczbie ustawionych bitów w n ⊻ n: 2 .

Python 2, 29 bajtów

f=lambda n:n and-n%4/2+f(n/2)

Liczy liczbę zmian między 0 a 1 w rozwinięciu binarnym, licząc wiodącą 1 jako alternatywę. Czyni to, sprawdzając, czy dwie ostatnie cyfry binarne są różne, a następnie powraca do liczby z usuniętą ostatnią cyfrą. Dwie ostatnie cyfry są różne dokładnie, jeśli n%4wynosi 1 lub 2, co można sprawdzić jako -n%4/2.

JavaScript (ES6), 26 bajtów

f=n=>n&&(n^(n>>=1))%2+f(n)

Działa poprzez zliczanie przejść od 0 do 1. Działa tylko do 31 bitów. 29 bajtów do obsługi 53 bitów:

f=n=>1<=n&&(n%2^n/2%2)+f(n/2)

Haskell, 34 bajty

b 0=0
b n|x<-b$div n 2=x+mod(x+n)2

05AB1E , 7 5 bajtów

Zaoszczędzono 2 bajty dzięki Dennisowi .

b0ÛÔg

Bez przypadku krawędzi 0 może to być 3 bajty bÔg.

Wypróbuj online! lub jako pakiet testowy

Wyjaśnienie

b      # convert to binary
 0Û    # trim off leading zeroes
   Ô   # remove adjacent duplicates
    g  # length

CJam , 14 bajtów

ri0{2b:!2bj)}j

Wypróbuj online!

ri      e# read integer
0       e# value for terminal case
{       e# recursive function
  2b    e#   create binary representation with no leading zeros
  :!    e#   flip bits
  2b    e#   convert binary back to integer
  j     e#   recursive call
  )     e#   increment from 0 on the way up
}j      e# end

Zasadniczo podróbka mojej odpowiedzi na drugie pytanie.

Java 7,112 108 100 90 73 bajty

int c(int i){int l=1,j=i;for(;(j=j/2)>0;l*=2);return i<1?0:1+c(2*l-1-i);}

Podstawowy pomysł

 Lets take an no 10110(21)
 then you do set all bits in no 21 and you will get 11111
 and after that you would subtract the original number from 11111.
 You will get 01001 and loop it until you will get 0

J, 14 bajtów

**1+/@,2~:/\#:

Liczy liczbę przebiegów w cyfrach binarnych n ze specjalnym przypadkiem zwracającym 0 dla n = 0.

Stosowanie

   f =: **1+/@,2~:/\#:
   (,.f"0) 0 1 42 97 170 255 682 8675309 4812390 178956970 2863311530
         0  0
         1  1
        42  6
        97  3
       170  8
       255  1
       682 10
   8675309 11
   4812390 14
 178956970 28
2863311530 32

Wyjaśnienie

**1+/@,2~:/\#:  Input: integer n
            #:  Get the binary digits of n
       2   \    For each overlapping sublist of size 2
        ~:/       Reduce by not-equals
  1   ,         Prepend a 1
   +/@          Reduce by addition
*               Sign(n), returns 0 for n = 0 else 1
 *              Multiply with the previous sum and return

CJam , 11 10 bajtów

Dzięki @Dennis za uratowanie jednego bajtu!

ri_2be`,e&

Wypróbuj online!

Wyjaśnienie

ri            #e Read as integer
              #e STACK: 97
  _           #e Duplicate
              #e STACK: 97, 97
   2b         #e Convert to binary
              #e STACK: 97, [1 1 0 0 0 0 1]
     e`       #e Run-length encoding
              #e STACK: 97, [[2 1] [4 0] [1 1]]
       ,      #e Length
              #e STACK: 97, 3
        e&    #e Return first value if 0, or else the second value
              #e STACK: 3

Rakieta 349 bajtów

(define(h s)(apply string(map(λ(x)(if(eq? x #\0)#\1 #\0))(string->list s))))(define(g s)(let*
((l(string-length s))(k(for/list((i s)(n l)#:final(not(equal? i #\0)))n)))(substring s(last k))))
(define(f n)(if(= 0 n)0(begin(let loop((n n)(c 1))(define m(string->number(string-append "#b"
(g(h(number->string n 2))))))(if(> m 0)(loop m(add1 c))c))))

Nie golfowany:

(define (invertBinary s)
  (apply string
         (map
          (λ(x)(if(eq? x #\0)#\1 #\0))
          (string->list s))))

(define (trimLeading0s s)
  (let* ((l (string-length s))
         (k (for/list ((i s)
                       (n l)
                       #:final (not(equal? i #\0)))
              n)))
    (substring s (last k))))

(define (f n)
  (if (= 0 n) 0
      (begin
        (let loop ((n n)
                   (c 1))
          (define m 
            (string->number
             (string-append
              "#b"
              (trimLeading0s
               (invertBinary
                (number->string n 2))))))

          (if (> m 0)
              (loop m (add1 c))
              c)))))

Testowanie:

(f 0)
(f 1)
(f 42)
(f 97)
(f 170)
(f 255)
(f 682)
(f 8675309)
(f 4812390)
(f 178956970)
(f 2863311530)

Wynik:

0
1
6
3
8
1
10
11
14
28
32

MATL , 7 bajtów

BY'nwa*

Wypróbuj online!

Wyjaśnienie

          % Implicit input, for example 97
          % STACK: 97
B         % Convert to binary
          % STACK: [1 1 0 0 0 0 1]
 Y'       % Run-length encoding
          % STACK: [1 0 1], [2 4 1]
   n      % Number of elements
          % STACK: [1 0 1], 3
    w     % Swap
          % STACK: 3, [1 0 1]
     a    % Any: gives 1 if any element is nonzero
          % STACK: 3, 1
      *   % Multiply
          % STACK: 3
          % Implicit display

Vim, 62 59 bajtów

-3 bajty dzięki DJMcMayhem

C0
<C-r>=pri<Tab>'%b',<C-r>")
<Esc>0qqC<C-r>=tr(@",'01','10')
<Esc>:s/^0\+
k<C-a>j@qq@q

Oto wyjście xxd z nienaruszonymi znakami niedrukowalnymi:

0000000: 4330 0d12 3d70 7269 0927 2562 272c 1222  C0..=pri.'%b',."
0000010: 290d 1b30 7171 4312 3d74 7228 4022 2c27  )..0qqC.=tr(@",'
0000020: 3031 272c 2731 3027 290d 1b3a 732f 5e30  01','10')..:s/^0
0000030: 5c2b 0d6b 016a 4071 7140 71              \+.k.j@qq@q

Wypróbuj online!

Wyjaśnienie

C                                   " Delete the number (it goes in @")
0<CR>                               " Print 0 (our counter) and a carriage return
<C-r>=pri<Tab>'%b',<C-r>")<CR><Esc> " Use `printf()` to insert the number as base 2
0qq                                 " Return to column 0, start recording a macro
  C<C-r>=tr(@",'01','10')<CR><Esc>  "   Replace 0s with 1s and vice versa
  :s/^0\+<CR>                       "   Delete leading 0s
  k<C-a>                            "   Increment the number on the line above
  j                                 "   Return to the previous line
  @q                                "   Invoke macro recursively
q@q                                 " Stop recording and invoke macro

Rubinowy, 26 bajtów

f=->n{n<1?0:-n%4/2+f[n/2]}

Zainspirowany odpowiedzią Python na xnor.

PHP, 64 bajty

na podstawie mojego rozwiązania odliczania

for($n=$argv[1];$n;print 1)$n=bindec(strtr(decbin($n),"01",10));

wypisuje czasy 1znaków k, gdzie kjest liczba iteracji.

+4 bajty dla wyjścia liczb całkowitych: (puste wyjście dla 0)

for($n=$argv[1];$n;$i++)$n=bindec(strtr(decbin($n),"01",10));echo$i;

JavaScript (ES6), 44

Funkcja rekurencyjna

Ograniczona do dodatniej liczby całkowitej javascript, 31 bitów:

f=(a,s=0)=>a?f((-1>>>Math.clz32(a))-a,s+1):s

Zarządzanie podwójną precyzją do 53 znaczących bitów - 59 bajtów:

F=(a,s=0)=>a?F('0b'+a.toString(2).replace(/./g,1)-a,s+1):s

Innym sposobem: użycie niesamowitego algorytmu @Dennis, nierekurencyjna funkcja zarządzająca 53 bitami, 43 bajtami:

a=>a&&a.toString(2).match(/(.)\1*/g).length

PHP, 51 bajtów

<?=preg_match_all('/(1+|0+)/',decbin($argv[1])?:o);

Używa wyrażenia regularnego, aby policzyć liczbę przebiegów wynoszącą 1 lub 0. Niestety wymaga to specjalnego przypadku, dla którego wprowadzenie 0wymaga 3 dodatkowych bajtów (i powiadamia).

Java 7, 71 bajtów

int b(Long a){return a==0?0:1+b(~a&-1L>>>64-a.toString(a,2).length());}

Wiem, że pokonało to rozwiązanie Geobitssplit (które ostatecznie zostanie opublikowane), ale pisanie tego było fajne

Oktawa, 47 bajtów

@(x)(sum(dec2bin(bitxor(x,idivide(x,2)))=='1'))

Zgodnie z wpisem OEIS, wartość, której szukamy jako rozwiązania tego wyzwania, jest również równa liczbie 1s w kodzie Graya dla danej liczby całkowitej.

Wikipedia mówi mi, że kod Graya można obliczyć jako x ^ (x >> 1), więc w powyższej funkcji obliczyłem kod Graya jako taki, przekonwertowałem go na ciąg binarny i policzę ile cyfr tego ciągu 1.

Java 7, 64 bajty

long g(Long n){return n.toString(n,2).split("0+").length*2-n%2;}

Wiem, że może to zostać pobity przez port jednej z lepszych odpowiedzi, ale wymyśliłem to na czacie i nie mogę tego nie opublikować po tym, jak Poke powiedział coś na ten temat :)

C, 76 bajtów

unsigned n,m,i;f(x){for(i=0;x;x^=m-1,i++)for(n=x,m=2;n>>=1;m<<=1);return i;}

Działa dla wszystkich przypadków testowych (o ile nie chcę dołączać słowa unsigned lub last case test) ...

Bash, 57 bajtów

Pakiety: Core Utililities, grep, sed, vim (for xxd )

Załóżmy, że liczba jest podana w formacie binarnym. Każda długość jest dopuszczalna :)

xxd -b -c1|cut -d" " -f2|sed s/^0*//|grep -o .|uniq|wc -l

Perl 5 , 31 + 1 ( p) = 32 bajty

$_=(sprintf'%b',$_^$_/2)=~y/1//

Wypróbuj online!

Korzystanie z metody @ Dennisa.

Tcl , 119 bajtów

proc D n i\ 0 {
while \$n {set n [regsub ^0+(?=.) [string map {0 1 1 0} [format %b $n]] ""]
incr i
scan $n %b n}
set i}

Wypróbuj online!

Wciąż bardzo niepodobna do mojego gustu