Problem:

Znajdź liczbę zer wiodących w 64-bitowej liczbie całkowitej ze znakiem

Zasady:

• Dane wejściowe nie mogą być traktowane jako ciąg; może to być wszystko, gdzie algorytm steruje operacjami matematycznymi i bitowymi
• Dane wyjściowe powinny zostać sprawdzone pod kątem 64-bitowej liczby całkowitej ze znakiem, niezależnie od języka
• Obowiązują domyślne zasady gry w golfa
• Najkrótszy kod w bajtach wygrywa

Przypadki testowe:

Testy te zakładają liczby całkowite ze znakiem uzupełnienia do dwóch. Jeśli w Twoim języku / rozwiązaniu brakuje innej reprezentacji liczb całkowitych z podpisem, zadzwoń i podaj dodatkowe przypadki testowe, które mogą być istotne. Dołączyłem kilka przypadków testowych, które dotyczą podwójnej precyzji, ale możesz zaproponować inne, które powinny zostać wymienione.

input                output   64-bit binary representation of input (2's complement)
-1                   0        1111111111111111111111111111111111111111111111111111111111111111
-9223372036854775808 0        1000000000000000000000000000000000000000000000000000000000000000
9223372036854775807  1        0111111111111111111111111111111111111111111111111111111111111111
4611686018427387903  2        0011111111111111111111111111111111111111111111111111111111111111
1224979098644774911  3        0001000011111111111111111111111111111111111111111111111111111111
9007199254740992     10       0000000000100000000000000000000000000000000000000000000000000000
4503599627370496     11       0000000000010000000000000000000000000000000000000000000000000000
4503599627370495     12       0000000000001111111111111111111111111111111111111111111111111111
2147483648           32       0000000000000000000000000000000010000000000000000000000000000000
2147483647           33       0000000000000000000000000000000001111111111111111111111111111111
2                    62       0000000000000000000000000000000000000000000000000000000000000010
1                    63       0000000000000000000000000000000000000000000000000000000000000001
0                    64       0000000000000000000000000000000000000000000000000000000000000000

język maszynowy x86_64 w systemie Linux, 6 bajtów

0:       f3 48 0f bd c7          lzcnt  %rdi,%rax
5:       c3                      ret

Wymaga procesora Haswell lub K10 lub nowszego z lzcntinstrukcją.

Wypróbuj online!

Sześciokąt , 78 70 bajtów

2"1"\.}/{}A=<\?>(<$\*}[_(A\".{}."&.'\&=/.."!=\2'%<..(@.>._.\=\{}:"<><$

Wypróbuj online!

Czy to wyzwanie nie jest zbyt trywialne dla praktycznego języka? ;)

_{długość boku 6. Nie mogę go dopasować do sześciokąta o długości boku 5.}

Wyjaśnienie

Python , 31 bajtów

lambda n:67-len(bin(-n))&~n>>64

Wypróbuj online!

Expresson składa się &z dwóch części:

67-len(bin(-n)) & ~n>>64

67-len(bin(-n))Daje poprawną odpowiedź na wejściach nieujemnych. Bierze długość bitu i odejmuje od 67, czyli 3 więcej niż 64, aby skompensować -0bprefiks. Negacja jest sztuczką, która pozwala dostosować się do n==0tego, że negowanie nie powoduje pojawienia się -znaku z przodu.

To & ~n>>64sprawia, że ​​odpowiedź jest 0negatywna n. Kiedy n<0, ~n>>64jest równa 0 (na 64-bitowe liczby całkowite), a więc z-ing to daje 0. Kiedy n>=0The ~n>>64ocenia się -1, i robi &-1nie ma znaczenia.

Python 2 , 36 bajtów

f=lambda n:n>0and~-f(n/2)or(n==0)*64

Wypróbuj online!

Alternatywa arytmetyczna.

Java 8, 32 26 bajtów.

Long::numberOfLeadingZeros

Wbudowane FTW.

-6 bajtów dzięki Kevin Cruijssen

Wypróbuj online!

C (gcc) , 14 bajtów

__builtin_clzl

Działa dobrze na tio

C (gcc) , 35 29 bajtów

f(long n){n=n<0?0:f(n-~n)+1;}

Wypróbuj online!

Niż Dennis za 6 bajtów

Flagi kompilatora C (gcc) , 29 bajtów autorstwa Davida Foerstera

-Df(n)=n?__builtin_clzl(n):64

Wypróbuj online!

Perl 6 , 35 28 26 bajtów

-2 bajty dzięki nwellnhof

{to .fmt("%064b")~~/^0*/:}

Wypróbuj online!

Anonimowy blok kodu, który pobiera liczbę i zwraca liczbę. Konwertuje to liczbę na ciąg binarny i zlicza zera wiodące. Działa dla liczb ujemnych, ponieważ pierwszym znakiem jest -np. -00000101, Więc nie ma zer wiodących.

Wyjaśnienie:

{                        }  # Anonymous code block
    .fmt("%064b")           # Format as a binary string with 64 digits
                 ~~         # Smartmatch against
                   /^0*/    # A regex counting leading zeroes
 to                     :   # Return the index of the end of the match

JavaScript (Node.js) , 25 bajtów

Pobiera dane wejściowe jako literał BigInt.

f=x=>x<0?0:x?f(x/2n)-1:64

Wypróbuj online!

$0$

Python 3 , 34 bajty

f=lambda n:-1<n<2**63and-~f(2*n|1)

Wypróbuj online!

J , 18 bajtów

0{[:I.1,~(64$2)#:]

Wypróbuj online!

J , 19 bajtów

1#.[:*/\0=(64$2)#:]

Wypróbuj online!

Wyjaśnienie:

                #:  - convert 
                  ] - the input to
          (64$2)    - 64 binary digits
         =          - check if each digit equals 
        0           - zero
   [:*/\            - find the running product
1#.                 - sum

Perl 6 , 18 bajtów

-2 bajty dzięki Jo King

64-(*%2**64*2).msb

Wypróbuj online!

Ruby , 22 bajty

->n{/[^0]/=~"%064b"%n}

Wypróbuj online!

05AB1E , 10 9 bajtów

·bg65αsd*

I / O są liczbami całkowitymi

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

·         # Double the (implicit) input
          #  i.e. -1 → -2
          #  i.e. 4503599627370496 → 9007199254740992
 b        # Convert it to binary
          #  i.e. -2 → "ÿ0"
          #  i.e. 9007199254740992 → 100000000000000000000000000000000000000000000000000000
  g       # Take its length
          #  i.e. "ÿ0" → 2
          #  i.e. 100000000000000000000000000000000000000000000000000000 → 54
   65α    # Take the absolute different with 65
          #  i.e. 65 and 2 → 63
          #  i.e. 65 and 54 → 11
      s   # Swap to take the (implicit) input again
       d  # Check if it's non-negative (>= 0): 0 if negative; 1 if 0 or positive
          #  i.e. -1 → 0
          #  i.e. 4503599627370496 → 1
        * # Multiply them (and output implicitly)
          #  i.e. 63 and 0 → 0
          #  i.e. 11 and 1 → 11

Haskell , 56 bajtów

^{Dzięki xnor za wykrycie błędu!}

f n|n<0=0|1>0=sum.fst.span(>0)$mapM(pure[1,0])[1..64]!!n

Może przydzielić sporo pamięci, spróbuj online!

Może chcesz przetestować to z mniejszą stałą: Wypróbuj 8-bit!

Wyjaśnienie

mapM(pure[0,1])[1..64]mapM(pure[1,0])[1..64]$\lbrace0,1\rbrace^{64}$$1$sum.fst.span(>0)

PowerShell, 51 bajtów

param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1

Skrypt testowy:

$f = {

param([long]$n)for(;$n-shl$i++-gt0){}($i,65)[!$n]-1

}

@(
    ,(-1                   ,0 )
    ,(-9223372036854775808 ,0 )
    ,(9223372036854775807  ,1 )
    ,(4611686018427387903  ,2 )
    ,(1224979098644774911  ,3 )
    ,(9007199254740992     ,10)
    ,(4503599627370496     ,11)
    ,(4503599627370495     ,12)
    ,(2147483648           ,32)
    ,(2147483647           ,33)
    ,(2                    ,62)
    ,(1                    ,63)
    ,(0                    ,64)
) | % {
    $n,$expected = $_
    $result = &$f $n
    "$($result-eq$expected): $result"
}

Wynik:

True: 0
True: 0
True: 1
True: 2
True: 3
True: 10
True: 11
True: 12
True: 32
True: 33
True: 62
True: 63
True: 64

Java 8, 38 bajtów

int f(long n){return n<0?0:f(n-~n)+1;}

Wejście jako long(64-bitowa liczba całkowita), wyjście jako int(32-bitowa liczba całkowita).

Port odpowiedzi C (gcc) @ l4m2 .

Wypróbuj online.

Wyjaśnienie:

 int f(long n){       // Recursive method with long parameter and integer return-type
   return n<0?        //  If the input is negative:
           0          //   Return 0
          :           //  Else:
           f(n-~n)    //   Do a recursive call with n+n+1
                  +1  //   And add 1

EDYCJA: Może być 26 bajtów przy użyciu wbudowanego Long::numberOfLeadingZeroswyświetlanego w odpowiedzi Java 8 @lukeg .

APL + WIN, 34 bajty

+/×\0=(0>n),(63⍴2)⊤((2*63)××n)+n←⎕

Wyjaśnienie:

n←⎕ Prompts for input of number as integer

((2*63)××n) If n is negative add 2 to power 63

(63⍴2)⊤ Convert to 63 bit binary

(0>n), Concatinate 1 to front of binary vector if n negative, 0 if positive

+/×\0= Identify zeros, isolate first contiguous group and sum if first element is zero

C # (interaktywny kompilator Visual C #) , 42 bajty

x=>x!=0?64-Convert.ToString(x,2).Length:64

Wypróbuj online!

C # (interaktywny kompilator Visual C #) , 31 bajtów

int c(long x)=>x<0?0:c(x-~x)+1;

Jeszcze krótszy, oparty na odpowiedzi C (gcc) @ l4m2. Nigdy nie wiedziałem, że możesz zadeklarować takie funkcje, dzięki @Dana!

Wypróbuj online!

Galaretka ,  10  9 bajtów

-1 dzięki zgrabnej sztuczce Erika the Outgolfer (nie-negatywne jest teraz po prostu AƑ)

ḤBL65_×AƑ

Łącze monadyczne akceptujące liczbę całkowitą (w zakresie), która daje liczbę całkowitą.

Wypróbuj online! Lub zobacz zestaw testowy .

10 było ḤBL65_ɓ>-×

Oto kolejne 10-bajtowe rozwiązanie, które lubię, ponieważ mówi, że to „BOSS” ...

BoṠS»-~%65

Zestaw testowy tutaj

... BoṠS63r0¤i, BoṠS63ŻṚ¤ilub BoṠS64ḶṚ¤iteż będzie działać.

Kolejne 10 bajtów (od Dennisa) to æ»64ḶṚ¤Äċ0(znowu æ»63r0¤Äċ0i æ»63ŻṚ¤Äċ0będzie działać)

Perl 5 , 37 bajtów

sub{sprintf("%064b",@_)=~/^0*/;$+[0]}

Wypróbuj online!

Lub te 46 bajtów, jeśli „strityfikacja” jest niedozwolona: sub z

sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}

Szybki (na platformie 64-bitowej), 41 bajtów

Deklaruje zamknięcie o nazwie, fktóre przyjmuje i zwraca an Int. To rozwiązanie działa poprawnie tylko platformy 64-bitowe, gdzie Intjest typealiased do Int64. (Na platformie 32-bitowej Int64można jawnie użyć dla typu parametru zamknięcia, dodając 2 bajty).

let f:(Int)->Int={$0.leadingZeroBitCount}

W Swift nawet podstawowy typ liczb całkowitych jest zwykłym obiektem zadeklarowanym w standardowej bibliotece. Oznacza to, że Intmogą mieć metody i właściwości, takie jak leadingZeroBitCount(które są wymagane na wszystkich typach zgodnych z FixedWidthIntegerprotokołem standardowej biblioteki ).

Haskell , 24 bajty

f n|n<0=0
f n=1+f(2*n+1)

Wypróbuj online!

Jest to w zasadzie to samo co rozwiązanie Java Kevina Cruijssena, ale znalazłem je niezależnie.

Argument powinien mieć typ Intdla kompilacji 64-bitowej lub Int64cokolwiek innego.

Wyjaśnienie

Jeśli argument jest ujemny, wynik wynosi natychmiast 0. W przeciwnym razie przesuwamy się w lewo, wypełniając je , aż osiągniemy liczbę ujemną. To wypełnienie pozwala nam uniknąć specjalnego przypadku na 0.

Dla porównania, oto oczywisty / skuteczny sposób:

34 bajty

import Data.Bits
countLeadingZeros

Czysty , 103 bajty

Używa tego samego „wbudowanego” co odpowiedź sufitu.

f::!Int->Int
f _=code {
instruction 243
instruction 72
instruction 15
instruction 189
instruction 192
}

Wypróbuj online!

Czysty , 58 bajtów

import StdEnv
$0=64
$i=until(\e=(2^63>>e)bitand i<>0)inc 0

Wypróbuj online!

Stax , 10 bajtów

în»╧3(∞┼⌠g

Uruchom i debuguj

To port rozwiązania 05AB1E Kevina.

Perl 5 -p , 42 bajtów

1while$_>0&&2**++$a-1<$_;$_=0|$_>=0&&64-$a

Wypróbuj online!

Dłuższe niż rozwiązanie oparte na łańcuchach bitowych, ale przyzwoite rozwiązanie matematyczne.

APL (NARS), 15 znaków, 30 bajtów

{¯1+1⍳⍨⍵⊤⍨64⍴2}

przetestuj kilka liczb, aby zobaczyć, jak używać:

  f←{¯1+1⍳⍨⍵⊤⍨64⍴2}
  f ¯9223372036854775808
0
  f 9223372036854775807
1

Rdza, 18 bajtów

i64::leading_zeros

Wypróbuj online!

K (ngn / k) , 6 bajtów

64-#2\

Wypróbuj online!

2\ zakoduj argument w formacie binarnym

# długość

64- odejmij od 64

PHP, 50 46 bajtów

for(;0<$n=&$argn;$n>>=1)$i++;echo$n<0?0:64-$i;

Uruchom jako potok z -Rlub wypróbuj go online ,

<?=$argn<0?0:0|64-log($argn+1,2);ma problemy z zaokrąglaniem; więc przeszedłem długą drogę.

Wolfram Language (Mathematica) , 41 bajtów

Wzór na liczby dodatnie jest sprawiedliwy 63-Floor@Log2@#&. Reguły wymiany są stosowane w specjalnych przypadkach zerowego i ujemnego wkładu.

Dane wejściowe nie muszą być 64-bitową liczbą całkowitą ze znakiem. To skutecznie zabierze głos na wejściu, aby przekształcić go w liczbę całkowitą. Jeśli wprowadzisz liczbę poza normalnymi granicami dla 64-bitowej liczby całkowitej, wyświetli ona liczbę ujemną wskazującą, ile więcej bitów będzie potrzebnych do zapisania tej liczby całkowitej.

63-Floor@Log2[#/.{_?(#<0&):>2^63,0:>.5}]&

Wypróbuj online!

@ Rozwiązanie LegionMammal978 jest nieco krótsze i ma 28 bajtów. Dane wejściowe muszą być liczbą całkowitą. Według dokumentacji: „ BitLength[n]jest efektywną wersją Floor[Log[2,n]]+1”. Automatycznie obsługuje przypadek zerowego raportowania 0zamiast -∞.

Wolfram Language (Mathematica) , 28 bajtów

Boole[#>=0](64-BitLength@#)&

Wypróbuj online!

bitNumber - math.ceil (math.log (number) / math.log (2))

np. 64-bitowy NUMER: 9223372036854775807 math.ceil (math.log (9223372036854775807) / math.log (2)) ANS: 63