Die alten Griechen hatten diese Dinge einfach und doppelt gerade Zahlen genannt. Ein Beispiel für eine einfach gerade Zahl ist 14. Sie kann einmal durch 2 geteilt werden und ist dann zu einer ungeraden Zahl (7) geworden, nach der sie nicht mehr durch 2 teilbar ist. Eine doppelt gerade Zahl ist 20. Sie kann zweimal durch 2 geteilt werden und wird dann zu 5.

Ihre Aufgabe ist es, eine Funktion oder ein Programm zu schreiben, die / das eine Ganzzahl als Eingabe und die Anzahl der durch 2 teilbaren Ganzzahlen in möglichst wenigen Bytes ausgibt. Die Eingabe ist eine Ganzzahl ungleich Null (jeder positive oder negative Wert innerhalb der Grenzen Ihrer Sprache).

Testfälle:

14 -> 1

20 -> 2

94208 -> 12

7 -> 0

-4 -> 2

Die Antwort mit den wenigsten Bytes gewinnt.

Tipp: Versuchen Sie, die Zahl in Basis 2 umzuwandeln. Sehen Sie, was Ihnen das sagt.

Gelee , 4 Bytes

Æfċ2

In der neuesten Version von Jelly ÆEḢfunktionieren (3 Byte).

Æf      Calculate the prime factorization. On negative input, -1 appended to the end.
  ċ2    Count the 2s.

Probieren Sie es hier aus .

x86_64-Maschinencode, 4 Byte

Der BSF-Befehl (Bit Scan Forward) macht genau das !

0x0f    0xbc    0xc7    0xc3

In der gcc-artigen Montage ist dies:

    .globl  f
f:
    bsfl    %edi, %eax
    ret

Die Eingabe wird im EDI-Register angegeben und gemäß den üblichen 64-Bit- C- Aufrufkonventionen im EAX-Register zurückgegeben .

Aufgrund der Zweierkomplement-Binärcodierung funktioniert dies sowohl für -ve- als auch für + ve-Zahlen.

Auch trotz der Dokumentation "Wenn der Inhalt des Quelloperanden 0 ist, ist der Inhalt des Zieloperanden undefiniert." Finde ich auf meiner Ubuntu VM, dass die Ausgabe von f(0)0 ist.

Anleitung:

• Speichern Sie das obige als evenness.sund montieren Sie mitgcc -c evenness.s -o evenness.o
• Speichern Sie den folgenden Testtreiber als evenness-main.cund kompilieren Sie mit gcc -c evenness-main.c -o evenness-main.o:

#include <stdio.h>

extern int f(int n);

int main (int argc, char **argv) {
    int i;

    int testcases[] = { 14, 20, 94208, 7, 0, -4 };

    for (i = 0; i < sizeof(testcases) / sizeof(testcases[0]); i++) {
        printf("%d, %d\n", testcases[i], f(testcases[i]));
    }

    return 0;
}

Dann:

• Verknüpfung: gcc evenness-main.o evenness.o -o evenness
• Lauf: ./evenness

@FarazMasroor bat um weitere Informationen darüber, wie diese Antwort abgeleitet wurde.

Da ich mit C besser vertraut bin als mit den Feinheiten von x86-Assemblys, benutze ich normalerweise einen Compiler, um Assembly-Code für mich zu generieren. Ich weiß aus Erfahrung , dass gcc Erweiterungen wie __builtin_ffs(), __builtin_ctz()und__builtin_popcount() typischerweise zusammenzustellen und um 1 oder 2 Anweisungen auf x86 montieren. Also begann ich mit einer c- Funktion wie:

int f(int n) {
    return __builtin_ctz(n);
}

Anstatt die reguläre GCC-Kompilierung bis hin zum Objektcode zu verwenden, können Sie die -SOption verwenden, um nur Assembly zu kompilieren gcc -S -c evenness.c. Dies ergibt eine Assembly-Datei evenness.swie folgt:

    .file   "evenness.c"
    .text
    .globl  f
    .type   f, @function
f:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -4(%rbp)
    movl    -4(%rbp), %eax
    rep bsfl    %eax, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   f, .-f
    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

Vieles davon kann ausgenutzt werden. Insbesondere wissen wir, dass die c- Aufrufkonvention für Funktionen mit int f(int n);Signatur nett und einfach ist - der Eingabeparameter wird im EDIRegister übergeben und der Rückgabewert wird im EAXRegister zurückgegeben. So können wir die meisten Anweisungen herausnehmen - viele befassen sich mit dem Speichern von Registern und dem Einrichten eines neuen Stapelrahmens. Wir benutzen den Stack hier nicht und benutzen nur das EAXRegister, also brauchen wir uns nicht um andere Register zu kümmern. Dies hinterlässt den Assembler-Code "Golf":

    .globl  f
f:
    bsfl    %edi, %eax
    ret

Beachten Sie, wie @zwol hervorhebt, dass Sie auch eine optimierte Kompilierung verwenden können, um ein ähnliches Ergebnis zu erzielen. -OsProduziert insbesondere genau die obigen Anweisungen (mit ein paar zusätzlichen Assembler-Direktiven, die keinen zusätzlichen Objektcode produzieren.)

Diese wird nun mit zusammengesetzt gcc -c evenness.s -o evenness.o, die dann wie oben beschrieben in ein Testtreiberprogramm eingebunden werden können.

Es gibt verschiedene Möglichkeiten, den dieser Baugruppe entsprechenden Maschinencode zu ermitteln. Mein Favorit ist die Verwendung des disassBefehls gdb disassembly:

$ gdb ./evenness
GNU gdb (Ubuntu 7.7.1-0ubuntu5~14.04.2) 7.7.1
...
Reading symbols from ./evenness...(no debugging symbols found)...done.
(gdb) disass /r f
Dump of assembler code for function f:
   0x00000000004005ae <+0>: 0f bc c7    bsf    %edi,%eax
   0x00000000004005b1 <+3>: c3  retq   
   0x00000000004005b2 <+4>: 66 2e 0f 1f 84 00 00 00 00 00   nopw   %cs:0x0(%rax,%rax,1)
   0x00000000004005bc <+14>:    0f 1f 40 00 nopl   0x0(%rax)
End of assembler dump.
(gdb) 

So können wir sehen, dass der Maschinencode für die bsfAnweisung 0f bc c7und für retist c3.

Python, 25 Bytes

lambda n:len(bin(n&-n))-3

n & -n setzt alles außer dem niedrigstwertigen Bit auf Null, zB dies:

100010101010100000101010000
            v
000000000000000000000010000

Wir sind an der Anzahl der nachgestellten Nullen interessiert, also konvertieren wir sie mit in eine Binärzeichenfolge bin, die für die obige Zahl gilt "0b10000". Da uns weder das 0bnoch das 1wichtig ist, subtrahieren wir 3 von dieser Saitenlänge.

Pyth, 6 Bytes

/P.aQ2

Probieren Sie es hier aus .

 P.aQ         In the prime factorization of the absolute value of the input
/    2        count the number of 2s.

JavaScript (ES6), 18 Byte

n=>Math.log2(n&-n)

4 Bytes kürzer als 31-Math.clz32. Hah

JavaScript ES6, 22 19 Bytes

f=x=>x%2?0:f(x/2)+1

Rekursion scheint der kürzeste Weg zu sein.

Pyth, 8 Bytes

lec.BQ\1

     Q    autoinitialized to eval(input())
   .B     convert to binary string
  c   \1  split on "1", returning an array of runs of 0s
 e        get the last run of 0s, or empty string if number ends with 1
l         take the length

Zum Beispiel ist die binäre Darstellung von 94208:

10111000000000000

Nach dem Teilen von 1s und dem Aufnehmen des letzten Elements des resultierenden Arrays wird dies zu:

000000000000

Das sind 12 Nullen, also ist es "gerade 12".

Dies funktioniert, weil x / 2es sich im Wesentlichen x >> 1um ein Bitverschiebungsrecht von handelt 1. Daher ist eine Zahl nur dann durch 2 teilbar, wenn das LSB ist 0(genau wie eine Dezimalzahl durch 10 teilbar ist, wenn ihre letzte Ziffer ist 0).

05AB1E , 4 5 Bytes

Unterstützt jetzt negative Zahlen. Code:

Äb1¡g

Probieren Sie es online!

Erläuterung:

Ä      # Abs(input)
 b     # Convert the number to binary
  1¡   # Split on 1's
    g  # Take the length of the last element

Verwendet die CP-1252-Codierung.

Pyth, 6 Bytes

x_.BQ1

Grundsätzlich nur

convert2BinString(evaluatedInput())[::-1].index("1")

MATL , 5 Bytes

Yf2=s

Dies funktioniert für alle ganzen Zahlen.

Probieren Sie es online!

Yf      % implicit input. Compute (repeated) prime factors. For negative input
        % it computes the prime factors of the absolute value, except that for
        % -1 it produces an empty array instead of a single 1
2=s     % count occurrences of "2" in the array of prime factors

C, 36 (28) Bytes

int f(int n){return n&1?0:f(n/2)+1;}

(Es wurde angegeben, dass kein Argument ungleich Null auf Null geprüft werden soll.)

Update (als Antwort auf einen Kommentar) : Wenn wir Funktionsdeklarationen im K & R-Stil zulassen, können wir eine 28-Byte-Version haben:

f(n){return n&1?0:f(n/2)+1;}

In diesem Fall verlassen wir uns auf die Tatsache, dass der Compiler standardmäßig sowohl nals auch den Rückgabetyp von fto verwendet int. Dieses Formular generiert jedoch eine Warnung mit C99 und wird nicht als gültiger C ++ - Code kompiliert.

Java 7, 39 oder vielleicht 44 Bytes

int s(int a){return a%2!=0?0:s(a/2)+1;}

int s(int a){return a%2!=0|a==0?0:s(a/2)+1;}

Ja Rekursion! Ich musste einen !=anstelle eines kürzeren Vergleichs verwenden, damit es bei negativen Eingaben nicht überläuft, aber ansonsten ist es ziemlich einfach. Wenn es ungerade ist, senden Sie eine Null. Wenn ja, fügen Sie einen hinzu und wiederholen Sie den Vorgang.

Es gibt zwei Versionen, da die Ausgabe für Null derzeit unbekannt ist. Der erste Befehl wird solange wiederholt, bis der Stapel überläuft, und gibt nichts aus, da 0 unendlich gerade ist. Die zweite spuckt eine schöne, sichere, aber wahrscheinlich nicht mathematisch strenge 0 für die Ausgabe aus.

JavaScript (ES6), 20 Bytes, 19 Bytes.

f=x=>~x%2&&1+f(x/2)

Dies ist ein Port der Haskell-Lösung von @nimi zu JavaScript. Es verwendet die "Kurzschluss" -Eigenschaften &&, deren linke Seite zurückgegeben wird, wenn es falsch ist (was in diesem Fall der Fall ist -0) oder die rechte Seite zurückgibt. Zur Umsetzung machen odd x = 0wir daher die linke Seite, 1 - (x % 2)die 0durch die sprudelt &&, ansonsten greifen wir zu 1 + f(x / 2).

Das Rasieren von 1 - (x % 2)as (~x) % 2ist auf @Neil zurückzuführen und hat die seltsame Eigenschaft, dass die obige Funktion -0kleine ungerade Zahlen ausgibt . Dieser Wert ist eine Besonderheit der Entscheidung von JS, dass ganze Zahlen IEEE754-Doppelte sind. Dieses System hat ein separates +0und -0in JavaScript spezielles Gehäuse, um ===untereinander zu sein. Der ~Operator berechnet die bitweise 32-Bit-Ganzzahl-Inversion für die Zahl, die für kleine ungerade Zahlen eine negative gerade Zahl ist. (Die positive Zahl Math.pow(2, 31) + 1zum Beispiel erzeugt 0eher als -0.) Die seltsame Beschränkung auf die 32-Bit-Ganzzahlen hat keine anderen Auswirkungen; es beeinträchtigt insbesondere nicht die Richtigkeit.

Perl 6, 23 18 Bytes

{+($_,*/2...^*%2)}

Verwendungszweck

> my &f = {+($_,*/2...^*%2)}
-> ;; $_? is raw { #`(Block|117104200) ... }
> f(14)
1
> f(20)
2
> f(94208)
12
> f(7)
0
> f(-4)
2

Ruby 24 Bytes

Meine erste Code Golf Einreichung (yey!)

("%b"%$*[0])[/0*$/].size

Wie ich hierher gekommen bin :

Zuerst wollte ich Code bekommen, der die Spezifikation tatsächlich erfüllte, um das Problem in den Griff zu bekommen, also baute ich die Methode ohne Rücksicht auf die Anzahl der Bytes auf:

def how_even(x, times=1)
  half = x / 2
  if half.even?
    how_even(half, times+1)
  else
    times
  end
end

Mit diesem Wissen habe ich die Funktion in eine while-Schleife $*dekursiert und (ARGV) als Eingabe und i als Anzahl der Halbierungen der Zahl hinzugefügt, bevor sie ungerade wird.

x=$*[0];i=1;while(x=x/2)%2<1;i+=1;end;i

Ich war ziemlich stolz darauf und hätte es beinahe eingereicht, bevor mir auffiel, dass all das Teilen durch zwei für mich ein bisschen binär klang, weil ich ein Software-Ingenieur, aber nicht so sehr ein Informatiker war.

Daher habe ich einige Ergebnisse darüber gesammelt, wie die Eingabewerte im Binärformat aussahen:

input      in binary      result
---------------------------------
   14               1110   1
   20              10100   2
94208  10111000000000000  12

Mir ist aufgefallen, dass das Ergebnis die Anzahl der Positionen links ist, die wir überqueren müssen, bevor die Anzahl ungerade wird.

Durch einige einfache Zeichenkettenmanipulationen habe ich die Zeichenkette beim letzten Auftreten von 1 geteilt und die Länge der verbleibenden Nullen gezählt:

("%b"%$*[0])[/0*$/].size

Verwenden Sie die ("%b" % x)Formatierung, um eine Zahl in eine Binärzahl umzuwandeln, und die Zeichenfolge # , um die Zeichenfolge aufzuteilen.

Ich habe auf dieser Suche ein paar Dinge über Rubin gelernt und freue mich bald auf weitere Golfplätze!

J, 6 Bytes

1&q:@|

Erläuterung:

     |    absolute value
1&q:      exponent of 2 in the prime factorization

C 37 Bytes

f(int x){return x?x&1?0:1+f(x/2):0;} Überprüfen Sie das letzte Bit rekursiv, bis es keine 0 mehr ist.

Haskell, 28 Bytes

f x|odd x=0|1<2=1+f(div x 2)

Anwendungsbeispiel: f 94208-> 12.

Wenn die Zahl ungerade ist, ist das Ergebnis 0, sonst 1plus ein rekursiver Anruf mit der Hälfte der Zahl.

Befunge, 20

&:2%#|_\1+\2/#
   @.<

Die Codeausführung bewegt sich weiter nach rechts und umschließt das zweite Zeichen der ersten Zeile (dank des Trailings #) bis zur 2%Ausgabe 1, wodurch _die Richtung nach links und dann |nach oben gewechselt wird, die <in die zweite Zeile übergeht. welche Ausgänge und Ausgänge. Wir inkrementieren das zweitoberste Element des Stapels jedes Mal durch die Schleife und teilen dann das oberste Element durch 2.

Netzhaut ,29 17

+`\b(1+)\1$
;$1
;

Probieren Sie es online!

2 Bytes gespart dank Martin!

Nimmt unäre Eingaben auf. Dies stimmt wiederholt mit der größten Menge von 1s überein, die es geben kann, so dass diese Anzahl von 1s genau mit dem Rest von 1s in der Anzahl übereinstimmt . Jedes Mal, wenn dies geschieht ;, wird der Zeichenfolge ein vorangestellt . Am Ende zählen wir die Anzahl der ;s in der Zeichenfolge.

Wenn Sie eine Dezimaleingabe wünschen, fügen Sie Folgendes hinzu:

\d+
$0$*1

an den Anfang des Programms.

Jolf, 6 Bytes

Probieren Sie es hier aus!

Zlm)j2
Zl   2  count the number occurrences of 2 in
  m)j   the prime factorization of j (input)

Ganz einfach ... Ein dickes Lob an ETHProductions, dass sie Jolf mit der Version verdrängt haben, die wirklich funktionieren sollte!

PARI / GP, 17 Bytes

n->valuation(n,2)

6502 Maschinensprache, 7 Bytes

Um den Stellenwert des niedrigstwertigen 1-Bit des Nicht-Null-Werts im Akkumulator zu finden, belassen Sie das Ergebnis in Register X:

A2 FF E8 4A 90 FC 60

Um dies auf dem 6502-Simulator auf e-tradition.net auszuführen , muss ihm A9eine 8-Bit-Ganzzahl vorangestellt werden .

Dies lässt sich wie folgt zerlegen:

count_trailing_zeroes:
    ldx #$FF
loop:
    inx
    lsr a     ; set carry to 0 iff A divisible by 2, then divide by 2 rounding down
    bcc loop  ; keep looping if A was divisible by 2
    rts       ; return with result in X

Dies entspricht dem folgenden C, mit der Ausnahme, dass C intmindestens 16 Bit lang sein muss:

unsigned int count_trailing_zeroes(int signed_a) {
    unsigned int carry;
    unsigned int a = signed_a;  // cast to unsigned makes shift well-defined
    unsigned int x = UINT_MAX;
    do {
        x += 1;
        carry = a & 1;
        a >>= 1;
    } while (carry == 0);
    return x;
}

Dasselbe funktioniert auf einem 65816 unter der Annahme von MX = 01 (16-Bit-Akkumulator, 8-Bit-Index) und entspricht dem obigen C-Snippet.

Brachylog , 27 15 Bytes

$pA:2xlL,Al-L=.

Erläuterung

$pA             § Unify A with the list of prime factors of the input
   :2x          § Remove all occurences of 2 in A
      lL,       § L is the length of A minus all the 2s
         Al-L=. § Unify the output with the length of A minus L

CJam, 8 Bytes

rizmf2e=

Ganzzahl, Absolutwert, Primfaktor lesen, zwei zählen.

JavaScript ES6, 36 38 Bytes

Zwei Bytes dank @ETHproductions

Ziemlich langweilige Antwort, aber es macht den Job. Kann einer anderen Antwort tatsächlich zu ähnlich sein, wenn er die vorgeschlagenen Änderungen hinzufügt, werde ich meine entfernen.

b=>{for(c=0;b%2-1;c++)b/=2;alert(c)}

Um es auszuführen, weisen Sie es einer Variablen ( a=>{for...) zu, da es eine anonyme Funktion ist, und rufen Sie es dann mit auf a(100).

ES6, 22 Bytes

n=>31-Math.clz32(n&-n)

Gibt -1 zurück, wenn Sie 0 übergeben.

DUP , 20 Bytes

[$2/%0=[2/f;!1+.][0]?]f:

Try it here!

In Rekursion konvertiert, ist die Ausgabe jetzt die höchste Zahl im Stapel. Verwendungszweck:

94208[2/\0=[f;!1+][0]?]f:f;!

Erläuterung

[                ]f: {save lambda to f}
 2/\0=               {top of stack /2, check if remainder is 0}
      [     ][ ]?    {conditional}
       f;!1+         {if so, then do f(top of stack)+1}
              0      {otherwise, push 0}

Japt, 9 5 Bytes

¢w b1

Online testen!

Die vorherige Version sollte aus fünf Bytes bestehen, aber diese Version funktioniert tatsächlich.

Wie es funktioniert

       // Implicit: U = input integer
¢      // Take the binary representation of U.
w      // Reverse.
b1     // Find the first index of a "1" in this string.
       // Implicit output

C 44 40 38 36 Bytes

2 Bytes weg danke @JohnWHSmith . 2 Bytes weg danke @luserdroog .

a;f(n){for(;~n&1;n/=2)a++;return a;}

Teste live auf ideone .