Starożytni Grecy nazywali te rzeczy pojedynczo i podwójnie parzystymi liczbami. Przykładem pojedynczo parzystej liczby jest 14. Można ją podzielić przez 2 raz, i w tym momencie stała się liczbą nieparzystą (7), po czym nie jest już podzielna przez 2. Podwójnie parzysta liczba to 20. Można ją dwukrotnie podzielić przez 2, a następnie otrzymać 5.

Twoim zadaniem jest napisanie funkcji lub programu, który pobiera liczbę całkowitą jako dane wejściowe i wyprowadza liczbę podzielności przez 2 jako liczbę całkowitą, w jak najmniejszej liczbie bajtów. Dane wejściowe będą niezerową liczbą całkowitą (dowolną wartością dodatnią lub ujemną, w granicach twojego języka).

Przypadki testowe:

14 -> 1

20 -> 2

94208 -> 12

7 -> 0

-4 -> 2

Odpowiedź z najmniej bajtami wygrywa.

Wskazówka: Spróbuj przekonwertować liczbę na bazę 2. Zobacz, co ci to mówi.

Galaretka , 4 bajty

Æfċ2

W najnowszej wersji Jelly ÆEḢdziała (3 bajty).

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

Wypróbuj tutaj .

kod maszynowy x86_64, 4 bajty

Dokładnie to robi instrukcja BSF (przeskok bitów do przodu) !

0x0f    0xbc    0xc7    0xc3

W zespole w stylu gcc jest to:

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

Dane wejściowe są podawane w rejestrze EDI i zwracane w rejestrze EAX zgodnie ze standardowymi 64-bitowymi konwencjami wywoływania c .

Ze względu na kodowanie binarne z dopełnieniem dwóch działa to zarówno dla liczb -ve, jak i + ve.

Ponadto, pomimo dokumentacji mówiącej: „Jeśli treść operandu źródłowego wynosi 0, treść operandu docelowego jest niezdefiniowana”. , Znajduję na mojej maszynie Wirtualnej Ubuntu, że wynikiem f(0)jest 0.

Instrukcje:

• Zapisz powyższe evenness.si zmontujgcc -c evenness.s -o evenness.o
• Zapisz następujący sterownik testowy jako evenness-main.ci skompiluj z 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;
}

Następnie:

• Połączyć: gcc evenness-main.o evenness.o -o evenness
• Biegać: ./evenness

@FarazMasroor poprosił o więcej informacji na temat sposobu uzyskania tej odpowiedzi.

Jestem bardziej zaznajomiony z c niż zawiłościami zestawu x86, więc zazwyczaj używam kompilatora do generowania kodu zestawu dla mnie. Wiem z doświadczenia, że rozszerzenia takie jak gcc __builtin_ffs(), __builtin_ctz()i__builtin_popcount() zazwyczaj skompilować i zmontować do 1 lub 2 instrukcje x86. Zacząłem więc od funkcji c, takiej jak:

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

Zamiast używać zwykłej kompilacji gcc aż do kodu obiektowego, możesz użyć -Sopcji kompilacji tylko do złożenia - gcc -S -c evenness.c. To daje plik asemblera evenness.staki jak ten:

    .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

Wiele z tego można zagrać w golfa. W szczególności wiemy, że konwencja wywoływania c dla funkcji z podpisem jest ładna i prosta - parametr wejściowy jest przekazywany do rejestru, a zwracana wartość jest zwracana do rejestru. Możemy więc wyciągnąć większość instrukcji - wiele z nich dotyczy zapisywania rejestrów i konfigurowania nowej ramki stosu. Nie używamy tutaj stosu i używamy tylko rejestru, więc nie musisz się martwić o inne rejestry. Pozostawia to kod zestawu „golfowy”:int f(int n);EDIEAXEAX

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

Uwaga: jak wskazuje @zwol, można również użyć zoptymalizowanej kompilacji, aby osiągnąć podobny wynik. W szczególności -Ostworzy dokładnie powyższe instrukcje (z kilkoma dodatkowymi dyrektywami asemblera, które nie generują żadnego dodatkowego kodu obiektowego).

Jest to teraz zmontowane z gcc -c evenness.s -o evenness.o, które można następnie połączyć z programem sterownika testowego, jak opisano powyżej.

Istnieje kilka sposobów ustalenia kodu maszynowego odpowiadającego temu zespołowi. Moim ulubionym jest użycie disasspolecenia dezasemblacji gdb :

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

Widzimy więc, że kod maszynowy bsfinstrukcji jest 0f bc c7i retjest c3.

Python, 25 bajtów

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

n & -n zeruje cokolwiek oprócz najmniej znaczącego bitu, np. to:

100010101010100000101010000
            v
000000000000000000000010000

Interesuje nas liczba końcowych zer, więc konwertujemy ją na ciąg binarny za pomocą bin, który dla powyższej liczby będzie "0b10000". Ponieważ nie dbamy o 0bani, ani 1odejmujemy 3 od tej długości łańcuchów.

Pyth, 6 bajtów

/P.aQ2

Wypróbuj tutaj .

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

JavaScript (ES6), 18 bajtów

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

4 bajty krótsze niż 31-Math.clz32. Hah

JavaScript ES6, 22 19 bajtów

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

Wygląda na to, że rekursja jest najkrótszą trasą.

Pyth, 8 bajtów

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

Na przykład binarna reprezentacja 94208to:

10111000000000000

Po podzieleniu na 1si i zabraniu ostatniego elementu wynikowej tablicy staje się:

000000000000

To 12 zer, więc to „12-ly nawet”.

Działa x / 2to, ponieważ jest zasadniczo x >> 1- czyli przesunięciem bitów w prawo 1. Dlatego liczba jest podzielna przez 2 tylko wtedy, gdy LSB jest 0(tak jak liczba dziesiętna jest podzielna przez 10, gdy jej ostatnia cyfra jest 0).

05AB1E , 4 5 bajtów

Teraz obsługuje liczby ujemne. Kod:

Äb1¡g

Wypróbuj online!

Wyjaśnienie:

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

Wykorzystuje kodowanie CP-1252.

Pyth, 6 bajtów

x_.BQ1

Zasadniczo po prostu

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

MATL , 5 bajtów

Yf2=s

Działa to dla wszystkich liczb całkowitych.

Wypróbuj 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) bajtów

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

(Podano brak testowania na argument zerowy jako argument niezerowy).

Aktualizacja (w odpowiedzi na komentarz) : Jeśli zezwolimy na deklaracje funkcji stylu K&R, możemy mieć wersję 28-bajtową:

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

W tym przypadku możemy liczyć na to, że zarówno kompilator domyślnie ni rodzaju powrót fdo int. Ten formularz generuje ostrzeżenie z C99 i nie kompiluje się jako poprawny kod C ++.

Java 7, 39 lub może 44 bajty

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

Tak, rekurencja! Musiałem użyć !=zamiast krótszego porównania, aby nie przepełnić negatywnych danych wejściowych, ale poza tym jest to dość proste. Jeśli to dziwne, wyślij zero. Jeśli nawet, dodaj jeden i zrób to jeszcze raz.

Istnieją dwie wersje, ponieważ obecnie dane wyjściowe dla zera są nieznane. Pierwszy będzie powtarzał się, aż stos się przepełni, i nic nie wyprowadza, ponieważ 0 jest nieskończenie równe. Drugi wyrzuca ładne, bezpieczne, ale prawdopodobnie nie matematyczne rygorystyczne 0 dla wyjścia.

JavaScript (ES6), 20 bajtów 19 bajtów.

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

To jest port rozwiązania Haskell od @nimi do JavaScript. Wykorzystuje właściwości „zwarcia”, &&które zwraca jego lewą stronę, jeśli jest falsey (co w tym przypadku jest -0), lub zwraca prawą stronę. Aby wdrożyć odd x = 0, wykonujemy zatem lewą stronę, 1 - (x % 2)która 0przepuszcza bąbelki &&, w przeciwnym razie uciekamy się 1 + f(x / 2).

Golenie 1 - (x % 2)as (~x) % 2wynika z poniższej @Neil i ma dziwną właściwość, która powoduje, że powyższa funkcja emituje -0małe liczby nieparzyste. Ta wartość jest osobliwością decyzji JS, że liczby całkowite są podwójnymi liczbami IEEE754; ten system ma osobne +0i -0są w JavaScripcie specjalnie zaprojektowane, aby być ===ze sobą. ~Operatora oblicza 32-bitowe, zalogowanych całkowitą bitową inwersję na liczbę, która dla małych liczb nieparzystych będzie ujemny liczba parzysta. (Na Math.pow(2, 31) + 1przykład liczba dodatnia daje 0raczej niż -0.) Dziwne ograniczenie liczb całkowitych ze znakiem 32-bitowym nie ma żadnych innych efektów; w szczególności nie wpływa to na poprawność.

Perl 6, 23 18 bajtów

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

stosowanie

> 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 bajty

Moje pierwsze zgłoszenie do gry w golfa (tak!)

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

Jak się tu dostałem :

Najpierw chciałem uzyskać kod, który faktycznie spełniał specyfikację, aby rozwiązać problem, więc zbudowałem metodę bez względu na liczbę bajtów:

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

z tą wiedzą przekreśliłem funkcję w pętlę while i dodałem $*(ARGV) jako dane wejściowe i jako liczbę, ile razy liczba została zmniejszona o połowę, zanim stała się nieparzysta.

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

Byłem z tego dość dumny i prawie przedłożyłem to, zanim dotarło do mnie, że to wszystko podzielone przez dwa brzmiało dla mnie trochę dwójkowo, będąc inżynierem oprogramowania, ale nie tyle informatykiem, co nie przychodzi mi na myśl.

Zebrałem więc wyniki dotyczące tego, jak wyglądały wartości wejściowe w formacie binarnym:

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

Zauważyłem, że wynikiem była liczba pozycji w lewo, którą musimy przejść, zanim liczba stanie się nieparzysta.

Wykonując proste operacje na łańcuchach, podzieliłem łańcuch przy ostatnim wystąpieniu 1 i policzyłem długość pozostałych zer:

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

używając ("%b" % x)formatowania, aby zamienić liczbę na binarną, i String # slice, aby pokroić mój ciąg.

Nauczyłem się kilku rzeczy o ruby ​​w tym zadaniu i już wkrótce czekam na więcej golfów!

J, 6 bajtów

1&q:@|

Wyjaśnienie:

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

C, 37 bajtów

f(int x){return x?x&1?0:1+f(x/2):0;} Rekurencyjnie sprawdź ostatni bit, aż nie będzie to 0.

Haskell, 28 bajtów

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

Przykład użycia: f 94208-> 12.

Jeśli liczba jest nieparzysta, wynik jest 0inny, 1plus połączenie rekurencyjne z połową numeru.

Befunge, 20

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

Wykonanie kodu przesuwa się w prawo i zawija do drugiego znaku pierwszego wiersza (dzięki końcowemu #) aż do 2%wyjścia 1, co powoduje _zmianę kierunku w lewo, a następnie |w górę, co powoduje zawijanie do <drugiego wiersza, które wyjścia i wyjścia. Za każdym razem przez pętlę zwiększamy drugi element stosu za każdym razem, a następnie dzielimy górę przez 2.

Siatkówka ,29 17

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

Wypróbuj online!

2 bajty zapisane dzięki Martinowi!

Zajmuje jednoargumentowy wkład. Powoduje to wielokrotne dopasowanie największej możliwej liczby 1s, tak że ta liczba 1s pasuje dokładnie do reszty 1s podanej liczby. Za każdym razem, gdy to robi, ;dodaje ciąg do ciągu. Na koniec zliczamy liczbę ;s w ciągu.

Aby wprowadzić dane dziesiętne, dodaj:

\d+
$0$*1

do początku programu.

Jolf, 6 bajtów

Wypróbuj tutaj!

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

Raczej proste ... Uznanie dla ETHProdukty za wyparcie Jolfa z wersją, która naprawdę powinna działać!

PARI / GP, 17 bajtów

n->valuation(n,2)

6502 język maszynowy, 7 bajtów

Aby znaleźć wartość miejsca najmniej znaczącego 1 bitu niezerowej wartości w akumulatorze, pozostawiając wynik w rejestrze X:

A2 FF E8 4A 90 FC 60

Aby uruchomić to na symulatorze 6502 na e-tradition.net , należy poprzedzić go znakiem , a A9następnie 8-bitową liczbą całkowitą.

To rozkłada się na następujące:

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

Jest to równoważne z następującym C, z tym wyjątkiem, że C musi intmieć co najmniej 16 bitów:

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

To samo działa na 65816, przy założeniu, że MX = 01 (akumulator 16-bitowy, indeks 8-bitowy) i jest równoważne powyższemu fragmentowi C.

Brachylog , 27 15 bajtów

$pA:2xlL,Al-L=.

Wyjaśnienie

$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 bajtów

rizmf2e=

Czytaj liczbę całkowitą, wartość bezwzględną, rozkład na czynniki pierwsze, policz dwa.

JavaScript ES6, 36 38 bajtów

Grał w golfa dwa bajty dzięki produktom @ETH

Odpowiedź dość nudna, ale działa. Może być zbyt podobny do innej odpowiedzi, jeśli doda sugerowane zmiany, usunę moją.

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

Aby uruchomić, przypisz ją do zmiennej ( a=>{for...), ponieważ jest to funkcja anonimowa, a następnie wywołaj ją za pomocą a(100).

ES6, 22 bajty

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

Zwraca -1, jeśli zdasz 0.

DUP , 20 bajtów

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

Try it here!

Przekształcony w rekurencję, wyjście jest teraz najwyższym numerem na stosie. Stosowanie:

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

Wyjaśnienie

[                ]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 bajtów

¢w b1

Przetestuj online!

Poprzednia wersja powinna mieć pięć bajtów, ale ta faktycznie działa.

Jak to działa

       // 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 bajtów

2 bajty wyłączone dzięki @JohnWHSmith . 2 bajty wyłączone dzięki @luserdroog .

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

Testuj na żywo na ideone .