inspiriert von Countdown aus der Unendlichkeit

Bei einer nicht negativen ganzen Zahl N die Anzahl der Wiederholungen der folgenden Schritte aus, die erforderlich sind, um 0 zu erreichen:

1. Konvertieren N Binärdatei ( 4812390 -> 10010010110111001100110)
2. Flip jedes Bit (10010010110111001100110 -> 01101101001000110011001 )
3. Trimmen Sie führende Nullen (01101101001000110011001 -> 1101101001000110011001 )
4. Zurück in Dezimalzahl konvertieren (1101101001000110011001 -> 3576217 )

Regeln

• Die Ein- und Ausgabe kann in jedem eindeutigen, konsistenten Format erfolgen
• Die Eingabe liegt innerhalb des systemeigenen darstellbaren Ganzzahlbereichs für Ihre Sprache (wenn Ihre Sprache beliebig große Ganzzahlen unterstützt, gibt es keine Begrenzung).

Testfälle

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

Diese Sequenz ist A005811 im OEIS.

Gelee , 6 4 Bytes

^HBS

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Hintergrund

Sei n eine nicht negative ganze Zahl.

Schritte 2 und 3 des Verfahrens in der beschriebenen spec können alternativ als das Entfernen aller führenden festgestellt werden , 1 ‚s und Hin- und Herschalten der verbleibenden Bits.

Dies bedeutet, dass wir in jeder Iteration genau eine Gruppe benachbarter und gleicher Binärziffern entfernen, sodass die binäre Countdown-Länge von n nur die Anzahl dieser Gruppen in der Binärdarstellung von n ist . Stellen Sie sich für diese Herausforderung vor, dass 0 keine Ziffern enthält.

Für n = 8675309 sieht der Prozess in binärer Form wie folgt aus.

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

Anstatt diese Gruppen zu zählen (was bei Randfall 0 fehlschlagen würde ), gehen wir wie folgt vor.

n und n: 2 haben die folgenden binären Darstellungen.

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

Beachten Sie, dass die Binärdarstellung von n: 2 einfach n ist und um ein Bit nach links verschoben ist.

Wenn wir n und n: 2 XOREN, erhalten wir eine 1 (MSB) und eine zusätzliche 1 für jedes Paar verschiedener benachbarter Ziffern. Die Anzahl der Gruppen ist also gleich der Anzahl der gesetzten Bits in n ≤ n: 2 .

Wie es funktioniert

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

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

Testen Sie es auf Ideone .

Hintergrund

Sei n eine nicht negative ganze Zahl.

Schritte 2 und 3 des Verfahrens in der beschriebenen spec können alternativ als das Entfernen aller führenden festgestellt werden , 1 ‚s und Hin- und Herschalten der verbleibenden Bits.

Dies bedeutet, dass wir in jeder Iteration genau eine Gruppe benachbarter und gleicher Binärziffern entfernen, sodass die binäre Countdown-Länge von n nur die Anzahl dieser Gruppen in der Binärdarstellung von n ist . Stellen Sie sich für diese Herausforderung vor, dass 0 keine Ziffern enthält.

Für n = 8675309 sieht der Prozess in binärer Form wie folgt aus.

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

Anstatt diese Gruppen zu zählen (was bei Randfall 0 fehlschlagen würde ), gehen wir wie folgt vor.

n und n: 2 haben die folgenden binären Darstellungen.

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

Beachten Sie, dass die Binärdarstellung von n: 2 einfach n ist und um ein Bit nach links verschoben ist.

Wenn wir n und n: 2 XOREN, erhalten wir eine 1 (MSB) und eine zusätzliche 1 für jedes Paar verschiedener benachbarter Ziffern. Die Anzahl der Gruppen ist also gleich der Anzahl der gesetzten Bits in n ≤ n: 2 .

Python 2, 29 Bytes

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

Zählt die Anzahl der Wechsel zwischen 0 und 1 in der binären Erweiterung und zählt die führende 1 als Wechsel. Dies geschieht, indem geprüft wird, ob die letzten beiden Binärziffern unterschiedlich sind, und dann die Zahl mit der letzten entfernten Ziffer wiederholt wird. Die letzten beiden Ziffern unterscheiden sich genau, wenn n%41 oder 2 ist, was überprüft werden kann als -n%4/2.

JavaScript (ES6), 26 Byte

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

Funktioniert durch Zählen der Übergänge zwischen 0 und 1. Funktioniert nur bis zu 31 Bit. 29 Bytes zur Unterstützung von 53 Bits:

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

Haskell, 34 Bytes

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

05AB1E , 7 5 Bytes

2 Bytes gespart dank Dennis .

b0ÛÔg

Ohne den Flankenfall 0 könnten dies 3 Bytes seinbÔg .

Probieren Sie es online! oder als Testsuite

Erläuterung

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

CJam , 14 Bytes

ri0{2b:!2bj)}j

Probieren Sie es 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

Grundsätzlich ein Abbruch meiner Antwort auf die andere Frage.

Java 7,112 108 100 90 73 Bytes

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

Grundidee

 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 Bytes

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

Zählt die Anzahl der Läufe in den Binärziffern von n, wobei der Sonderfall 0 für n = 0 zurückgibt.

Verwendung

   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

Erläuterung

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

Vielen Dank an @Dennis für das Speichern eines Bytes!

ri_2be`,e&

Probieren Sie es online!

Erläuterung

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

Schläger 349 Bytes

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

Ungolfed:

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

Testen:

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

Ausgabe:

0
1
6
3
8
1
10
11
14
28
32

MATL , 7 Bytes

BY'nwa*

Probieren Sie es online!

Erläuterung

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

-3 Bytes dank 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

Hier ist die xxd-Ausgabe mit intakten nicht druckbaren Zeichen:

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

Probieren Sie es online!

Erläuterung

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 Bytes

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

Inspiriert von der Python-Antwort von xnor.

PHP, 64 Bytes

basierend auf meiner Countdown-Lösung

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

Gibt 1Zeichenzeiten aus k, wobei kdie Anzahl der Iterationen angegeben wird.

+4 Bytes für Ganzzahlausgabe: (leere Ausgabe für 0)

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

JavaScript (ES6), 44

Rekursive Funktion

Beschränkt auf eine positive Ganzzahl mit Javascript, 31 Bit:

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

Verwaltung von Zahlen mit doppelter Genauigkeit bis zu 53 signifikanten Bits - 59 Bytes:

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

Auf eine andere Weise: Verwenden Sie den erstaunlichen Algorithmus von @Dennis, eine nicht rekursive Funktion, die 53 Bits und 43 Bytes verwaltet:

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

PHP, 51 Bytes

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

Verwendet einen regulären Ausdruck, um die Anzahl der Durchläufe von 1 oder 0 zu zählen. Leider erfordert dies einen Sonderfall für die Eingabe 0, der 3 zusätzliche Bytes erfordert (und einen Hinweis gibt).

Java 7, 71 Bytes

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

Ich weiß, dass dies von Geobits ' splitLösung (die irgendwann veröffentlicht wird) übertroffen wird, aber das Schreiben hat trotzdem Spaß gemacht

Oktave, 47 Bytes

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

Laut dem OEIS-Beitrag ist der Wert, den wir als Lösung für diese Herausforderung suchen, auch der Anzahl von1 s im Gray-Code für die angegebene Ganzzahl.

Wikipedia sagt mir, dass der Gray-Code als x ^ (x >> 1) berechnet werden kann. In der obigen Funktion berechne ich den Gray-Code als solchen, konvertiere ihn in eine Binärzeichenfolge und zähle, wie viele Stellen diese Zeichenfolge enthält 1.

Java 7, 64 Bytes

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

Ich weiß, dass dies von einer der besseren Antworten übertroffen werden könnte, aber ich habe es mir im Chat ausgedacht, und ich kann es nicht posten, nachdem Poke etwas darüber gesagt hat :)

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

Funktioniert für alle Testfälle (so weit ich das Wort unsigned oder last test case nicht einschließen möchte) ...

Bash, 57 Bytes

Pakete: Core Utililities, grep, sed, vim (für xxd)

Angenommen, die Zahl ist im Binärformat angegeben. Jede Länge ist akzeptabel :)

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

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

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

Probieren Sie es online!

Verwendung der @ Dennis-Methode.

Tcl , 119 Bytes

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}

Probieren Sie es online!

Für meinen Geschmack immer noch sehr ungolfed