terinspirasi oleh Count down from infinity

Diberikan bilangan bulat non-negatif N, hasilkan jumlah pengulangan dari langkah-langkah berikut yang diperlukan untuk mencapai 0:

1. Konversi Nke biner ( 4812390 -> 10010010110111001100110)
2. Balik setiap bit ( 10010010110111001100110 -> 01101101001000110011001)
3. Potong nol di depan ( 01101101001000110011001 -> 1101101001000110011001)
4. Konversi kembali ke desimal ( 1101101001000110011001 -> 3576217)

Aturan

• Input dan output mungkin dalam format yang jelas dan konsisten
• Input akan berada dalam rentang bilangan bulat representatif asli untuk bahasa Anda (jika bahasa Anda mendukung bilangan bulat besar sewenang-wenang, tidak ada batasan)

Uji Kasus

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

Urutan ini adalah A005811 dalam OEIS.

Jelly , 6 4 byte

^HBS

Cobalah online!atau verifikasi semua kasus uji .

Latar Belakang

Membiarkan n menjadi bilangan bulat non-negatif.

Langkah 2 dan 3 dari proses yang dijelaskan dalam spesifikasi dapat dinyatakan sebagai menghilangkan semua pelopor 1 's dan mengganti bit yang tersisa.

Ini berarti bahwa kami akan menghapus satu kelompok digit biner yang berdekatan dan sama di setiap iterasi, sehingga Panjang Countdown Biner dari n hanyalah jumlah grup ini dalam representasi biner dari n . Untuk keperluan tantangan ini, pikirkan 0 tidak memiliki digit.

Untuk n = 8675309 , prosesnya terlihat sebagai berikut dalam biner.

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

Alih-alih menghitung kelompok ini (yang akan gagal untuk kasus tepi 0 ), kami melakukan yang berikut.

n dan n: 2 memiliki representasi biner berikut.

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

Perhatikan bahwa representasi biner n: 2 sederhana n , bergeser sedikit ke kiri.

Jika kita XOR n dan n: 2 , kita akan mendapatkan 1 (MSB), dan 1 tambahan untuk setiap pasangan digit yang berdekatan berbeda. Dengan demikian jumlah grup sama dengan jumlah bit yang diset dalam n ⊻ n: 2 .

Bagaimana itu bekerja

^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 byte

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

Uji di Ideone .

Latar Belakang

Biarkan n menjadi bilangan bulat non-negatif.

Langkah 2 dan 3 dari proses yang diuraikan dalam spesifikasi dapat dinyatakan sebagai menghapus semua leading 1 's dan mengganti bit yang tersisa.

Ini berarti bahwa kami akan menghapus satu kelompok digit biner yang berdekatan dan sama di setiap iterasi, sehingga Panjang Countdown Biner dari n hanyalah jumlah grup ini dalam representasi biner dari n . Untuk keperluan tantangan ini, anggap 0 tidak memiliki digit.

Untuk n = 8675309 , prosesnya terlihat sebagai berikut dalam biner.

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

Alih-alih menghitung grup ini (yang akan gagal untuk kasus tepi 0 ), kami melakukan yang berikut.

n dan n: 2 memiliki representasi biner berikut.

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

Perhatikan bahwa representasi biner n: 2 hanyalah n , bergeser sedikit ke kiri.

Jika kita XOR n dan n: 2 , kita akan mendapatkan 1 (MSB), dan 1 tambahan untuk setiap pasangan digit yang berdekatan berbeda. Dengan demikian jumlah grup sama dengan jumlah bit yang diset dalam n ⊻ n: 2 .

Python 2, 29 byte

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

Menghitung jumlah pergantian antara 0 dan 1 dalam ekspansi biner, menghitung per 1 sebagai pergantian. Lakukan dengan memeriksa apakah dua digit biner terakhir berbeda, lalu berulang ke nomor dengan digit terakhir dihapus. Dua digit terakhir berbeda persis jika n%41 atau 2, yang dapat diperiksa sebagai -n%4/2.

JavaScript (ES6), 26 byte

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

Bekerja dengan menghitung transisi antara 0 dan 1. Hanya bekerja hingga 31 bit. 29 byte untuk mendukung 53 bit:

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

Haskell, 34 byte

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

05AB1E , 7 5 byte

Disimpan 2 byte berkat Dennis .

b0ÛÔg

Tanpa kasus tepi 0 ini bisa 3 byte bÔg.

Cobalah online! atau sebagai Test suite

Penjelasan

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

CJam , 14 byte

ri0{2b:!2bj)}j

Cobalah 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

Pada dasarnya jawaban saya untuk pertanyaan lainnya.

Java 7,112 108 100 90 73 byte

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);}

Ide dasar

 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 byte

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

Menghitung jumlah run dalam digit biner dari n dengan case khusus menghasilkan 0 untuk n = 0.

Pemakaian

   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

Penjelasan

**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 byte

Terima kasih kepada @Dennis karena telah menghemat satu byte!

ri_2be`,e&

Cobalah online!

Penjelasan

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

Racket 349 byte

(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))))

Tidak Disatukan:

(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)))))

Pengujian:

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

Keluaran:

0
1
6
3
8
1
10
11
14
28
32

MATL , 7 byte

BY'nwa*

Cobalah online!

Penjelasan

          % 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 byte

-3 byte terima kasih kepada 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

Ini adalah output xxd dengan karakter yang tidak dapat dicetak utuh:

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

Cobalah online!

Penjelasan

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

Ruby, 26 byte

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

Terinspirasi oleh jawaban Python xnor.

PHP, 64 byte

berdasarkan solusi hitung mundur saya

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

mencetak waktu 1karakter k, di mana kjumlah iterasi.

+4 byte untuk output integer: (output kosong untuk 0)

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

JavaScript (ES6), 44

Fungsi rekursif

Terbatas untuk javascript positive integer, 31 bit:

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

Mengelola angka presisi ganda hingga 53 bit signifikan - 59 byte:

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

Dengan cara lain: menggunakan algoritma luar biasa oleh @ Dennis, fungsi non rekursif mengelola hingga 53 bit, 43 byte:

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

PHP, 51 byte

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

Menggunakan regex untuk menghitung jumlah proses 1 atau 0. Sayangnya ini membutuhkan kasus khusus untuk input 0yang memerlukan 3 byte tambahan (dan memberikan pemberitahuan).

Java 7, 71 byte

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

Saya tahu ini dikalahkan oleh solusi Geobitssplit (yang nantinya akan diposting) tapi ini masih menyenangkan untuk ditulis

Oktaf, 47 byte

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

Menurut entri OEIS, nilai yang kami cari sebagai solusi untuk tantangan ini juga sama dengan jumlah 1s dalam kode Gray untuk bilangan bulat yang diberikan.

Wikipedia memberi tahu saya kode Gray dapat dihitung sebagai x ^ (x >> 1), jadi pada fungsi di atas saya menghitung kode Gray seperti itu, mengubahnya menjadi string biner, dan menghitung berapa digit dari string itu 1.

Java 7, 64 byte

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

Saya tahu ini bisa dikalahkan oleh port dari salah satu jawaban yang lebih baik, tetapi saya datang dengan itu dalam obrolan, dan saya tidak bisa mempostingnya setelah Poke mengatakan sesuatu tentang hal itu :)

C, 76 Bytes

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;}

Berfungsi untuk semua kasus uji (sebanyak yang saya tidak ingin memasukkan kata uji kasus unsigned atau terakhir) ...

Bash, 57 byte

Paket: Core Utililities, grep, sed, vim (untuk xxd )

Asumsikan angka diberikan dalam format biner. Panjangnya bisa diterima :)

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

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

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

Cobalah online!

Menggunakan metode @ Dennis.

Tcl , 119 byte

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}

Cobalah online!

Masih sangat ungolfed untuk seleraku