Temukan jumlah nol terkemuka di integer 64-bit

18

Masalah:

Temukan jumlah nol terkemuka di integer bertanda 64-bit

Aturan:

  • Input tidak dapat diperlakukan sebagai string; itu bisa apa saja di mana operasi matematika dan bitwise mendorong algoritma
  • Output harus divalidasi terhadap representasi bilangan bulat bertanda 64-bit, terlepas dari bahasa
  • Aturan golf kode standar berlaku
  • Kode terpendek dalam byte menang

Kasus uji:

Tes ini mengasumsikan bilangan bulat bertanda tangan dua pelengkap yang ditandatangani. Jika bahasa / solusi Anda kurang atau menggunakan representasi bilangan bulat bertanda tangan yang berbeda, harap sebutkan dan berikan kasus uji tambahan yang mungkin relevan. Saya telah memasukkan beberapa test case yang menangani presisi ganda, tetapi jangan ragu untuk menyarankan yang lain yang harus didaftar.

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
code-golf math restricted-source binary bitwise Dave
sumber
13
Selamat datang di PPCG! Apa alasan di balik "input tidak dapat diperlakukan sebagai string" ? Ini mendiskualifikasi semua bahasa yang tidak dapat menangani bilangan bulat 64-bit dan tidak mungkin mengarah pada lebih banyak jawaban yang mengambil bilangan bulat, karena ini adalah cara langsung ketika tersedia.
Arnauld
1
Bisakah kita kembali Falsebukan 0?
Jo King
4
@Arnauld Sudah ada pertanyaan serupa di sini dan di situs lain yang secara khusus menyerukan solusi berbasis string, tetapi tidak ada yang membuka pertanyaan untuk operasi matematika dan logis. Harapan saya adalah melihat banyak pendekatan berbeda untuk masalah ini yang belum dijawab di tempat lain. Haruskah ini dibuka untuk solusi string juga untuk menjadi inklusif?
Dave
4
Beberapa CPU termasuk x86 dan ARM memiliki instruksi khusus untuk ini (x86 sebenarnya memiliki beberapa). Saya selalu bertanya-tanya mengapa bahasa pemrograman tidak mengekspos fitur ini karena di sebagian besar bahasa pemrograman hari ini Anda tidak dapat meminta instruksi perakitan.
slebetman
1
@ user202729 Saya pikir saya mengatakan ini dengan buruk: 'Output harus divalidasi terhadap representasi bilangan bulat bertanda 64-bit, terlepas dari bahasa' Apa yang saya maksud dengan itu adalah bahwa pertanyaan ini mendefinisikan jumlah nol sebagai jumlah nol dalam integer bertanda 64-bit. Saya kira saya membuat batasan untuk menghilangkan bilangan bulat bertanda vs tidak bertanda.
Dave

Jawaban:

41

bahasa mesin x86_64 di Linux, 6 byte

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

Membutuhkan Haswell atau K10 atau prosesor yang lebih tinggi dengan lzcntinstruksi.

Cobalah online!

plafon
sumber
20
Tembakan bawaan lagi / s
Logern
1
Saya sarankan menentukan konvensi pemanggilan yang digunakan (meskipun Anda mengatakannya di Linux)
qwr
@ qwr Sepertinya konvensi pemanggilan SysV karena parameter dilewatkan dalam% rdi dan dikembalikan dalam% rax.
Logern
24

Hexagony , 78 70 byte

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

Cobalah online!

Bukankah tantangan ini terlalu sepele untuk bahasa praktis? ;)

panjang sisi 6. Saya tidak bisa memasangnya di sisi panjang 5 segi enam.

Penjelasan

pengguna202729
sumber
3
Saya tertawa sangat keras pada "penjelasan". : D
Eric Duminil
1
Saya pikir Anda mungkin terlalu rumit menangani angka negatif / nol. Saya berhasil memasukkan program yang mirip ke sisi panjang 5 dengan tidak melakukan perhitungan 2 ^ 64 yang lumayan. Itu jelas belum golf dengan baik, meskipun!
FryAmTheEggman
@fry Ah benar, angka negatif selalu memiliki 0 nol terkemuka ... yang pasti mengarah ke program yang lebih pendek karena menghasilkan 2 ^ 64 panjang.
user202729
12

Python , 31 byte

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

Cobalah online!

Ekspresi adalah bitwise &dari dua bagian:

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

Ini 67-len(bin(-n))memberikan jawaban yang benar untuk input non-negatif. Dibutuhkan panjang bit, dan kurangi dari 67, yaitu 3 lebih dari 64 untuk mengimbangi -0bawalan. Negasi adalah trik untuk menyesuaikan untuk n==0menggunakan negasi itu tidak menghasilkan -tanda di depan.

Sebagai & ~n>>64gantinya, jawabannya adalah 0negatif n. Kapan n<0, ~n>>64sama dengan 0 (pada bilangan bulat 64-bit), maka and-ing dengan itu memberi 0. Kapan n>=0, ~n>>64mengevaluasi ke -1, dan melakukan &-1tidak berpengaruh.

Python 2 , 36 byte

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

Cobalah online!

Alternatif aritmetika.

Tidak
sumber
9

Java 8, 32 26 byte.

Long::numberOfLeadingZeros

Dibangun FTW.

-6 byte terima kasih kepada Kevin Cruijssen

Cobalah online!

lukeg
sumber
Ah, benar-benar lupa tentang numberOfLeadingZeros.. Anda dapat golf itu hingga 28 byte btw:n->n.numberOfLeadingZeros(n)
Kevin Cruijssen
2
Sebenarnya, Long::numberOfLeadingZerosbahkan lebih pendek (26 byte).
Kevin Cruijssen
6
Wow, itu tidak sering terjadi bahwa Java mengalahkan Python. Selamat!
Eric Duminil
9

C (gcc) , 14 byte

__builtin_clzl

Bekerja dengan baik di tio

C (gcc) , 35 29 byte

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

Cobalah online!

Daripada Dennis untuk 6 byte

Bendera kompiler C (gcc) , 29 byte oleh David Foerster

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

Cobalah online!

l4m2
sumber
3
Perlu dicatat bahwa ini hanya untuk mesin 64-bit (atau yang lainnya dengan LP64 / ILP64 / dll. ABI)
Ruslan
1
Ya ampun, itu bahkan lebih pendek daripada penggunaan GCC built-in__builtin_clzl dengan yang saya dapat datang .
David Foerster
@Ruslan: poin bagus, pada sistem di mana long32 bit (termasuk Windows x64), Anda perlu __builtin_clzll(lama tidak ditandai). godbolt.org/z/MACCKf . (Tidak seperti Intel intrinsik, GNU C builtin didukung terlepas dari operasi yang dapat dilakukan dengan satu instruksi mesin. Pada 32-bit x86, clzll mengkompilasi ke cabang atau cmov untuk melakukan lzcnt(low half)+32atau lzcnt(high half). Atau bsrjika lzcnttidak tersedia.
Peter Cordes
Kasus uji termasuk "0" tetapi __builtin_clz(l)(l)perilaku tidak terdefinisi untuk nol: "Jika x adalah 0, hasilnya tidak terdefinisi."
MCCCS
1
@MCCCS Jika berhasil, itu diperhitungkan. Itu juga mengapa saya menyimpan jawaban terakhir
l4m2
6

Perl 6 , 35 28 26 byte

-2 byte terima kasih kepada nwellnhof

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

Cobalah online!

Blok kode anonim yang mengambil nomor dan mengembalikan nomor. Ini mengubah angka menjadi string biner dan menghitung nol terkemuka. Ini berfungsi untuk angka negatif karena karakter pertama adalah -eg -00000101, jadi tidak ada nol di depan.

Penjelasan:

{                        }  # 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
Jo King
sumber
6

JavaScript (Node.js) , 25 byte

Mengambil input sebagai literal BigInt.

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

Cobalah online!

0

Arnauld
sumber
Tidak akan n=>n<1?0:n.toString(2)-64melakukan hal yang sama?
Ismael Miguel
@ IsmaelMiguel saya kira Anda maksud n=>n<1?0:n.toString(2).length-64, tapi itu tidak akan berhasil. Ini akan , saya pikir.
Arnauld
1
@IsmaelMiguel Jangan khawatir. :) Memang mungkin untuk memiliki .toString()pendekatan yang berfungsi, tetapi kita masih membutuhkan BigInt literal sebagai input. Jika tidak, kami hanya memiliki 52 bit mantissa, yang mengarah ke hasil yang tidak valid ketika presisi hilang .
Arnauld
1
Fakta bahwa sufiks BigInt adalah karakter yang sama dengan parameter Anda sangat membingungkan ...
Neil
1
@Neil Kode tidak dapat dibaca di PPCG ?? Ini tidak mungkin! Tetap! : p
Arnauld
5

J , 18 byte

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

Cobalah online!

J , 19 byte

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

Cobalah online!

Penjelasan:

                #:  - convert 
                  ] - the input to
          (64$2)    - 64 binary digits
         =          - check if each digit equals 
        0           - zero
   [:*/\            - find the running product
1#.                 - sum
Galen Ivanov
sumber
1
1#.[:*/\1-_64{.#:(17) dekat tetapi tidak berfungsi untuk angka negatif :(
Conor O'Brien
@Conor O'Brien Pendekatan yang bagus juga!
Galen Ivanov
5

Perl 6 , 18 byte

-2 byte terima kasih kepada Jo King

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

Cobalah online!

nwellnhof
sumber
4

05AB1E , 10 9 byte

·bg65αsd*

I / O keduanya bilangan bulat

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

·         # 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
Kevin Cruijssen
sumber
4

Haskell , 56 byte

Terima kasih xnor karena menemukan kesalahan!

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

Mungkin mengalokasikan banyak memori, coba online!

Mungkin Anda ingin mengujinya dengan konstanta yang lebih kecil: Coba 8-bit!

Penjelasan

mapM(pure[0,1])[1..64]mapM(pure[1,0])[1..64]{0,1}641sum.fst.span(>0)

ბიმო
sumber
3

Powershell, 51 byte

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

Skrip uji:

$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"
}

Keluaran:

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
mazzy
sumber
3

Java 8, 38 byte

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

Masukkan sebagai long (integer 64-bit), output sebagai int(integer 32-bit).

Port C (gcc) jawaban @ l4m2 .

Cobalah online.

Penjelasan:

 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

EDIT: Dapat 26 byte dengan menggunakan builtin Long::numberOfLeadingZerosseperti yang ditampilkan dalam jawaban Java 8 @ lukeg .

Kevin Cruijssen
sumber
3

APL + WIN, 34 byte

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

Penjelasan:

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
Graham
sumber
3

Jelly ,  10  9 byte

-1 berkat trik yang rapi oleh Erik the Outgolfer (is-non-negative sekarang cukup AƑ)

ḤBL65_×AƑ

Tautan monadik yang menerima bilangan bulat (dalam kisaran) yang menghasilkan bilangan bulat.

Cobalah online! Atau lihat test-suite .

10 adalah ḤBL65_ɓ>-×

Berikut ini adalah solusi 10 byte lain, yang saya suka karena katanya "BOSS" ...

BoṠS»-~%65

Test-suite di sini

... BoṠS63r0¤i,, BoṠS63ŻṚ¤iatau BoṠS64ḶṚ¤ijuga akan berfungsi.

Lain byter 10 (dari Dennis) adalah æ»64ḶṚ¤Äċ0(lagi æ»63r0¤Äċ0dan æ»63ŻṚ¤Äċ0juga akan bekerja)

Jonathan Allan
sumber
9 byte
Erik the Outgolfer
@EriktheOutgolfer, saya berpikir, "pasti ada cara golf untuk memperbanyak dengan isNonNegative" dan tidak memikirkan Ƒcepat sama sekali, kerja yang sangat bagus!
Jonathan Allan
1
Sebenarnya, saya sudah berteori AƑuntuk beberapa waktu sekarang. Berhati-hatilah karena itu tidak membuat vektor! ;-) Ini sebenarnya "ratakan dan periksa apakah semua elemen tidak negatif".
Erik the Outgolfer
2

Perl 5 , 37 byte

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

Cobalah online!

Atau 46 byte ini jika "pengetatan" tidak diizinkan: sub z

sub{my$i=0;$_[0]>>64-$_?last:$i++for 1..64;$i}
Kjetil S.
sumber
s/length$&/$+[0]/(-3 byte);)
Dada
IMO, Anda tidak diizinkan untuk menghapus subkata kunci dari jawaban yang berisi fungsi Perl 5.
nwellnhof
Saya telah melihat apa yang mirip dengan menghapus subjawaban untuk bahasa lain, perl6, PowerShell dan banyak lagi.
Kjetil S.
Di Perl6, saya pikir Anda tidak perlu sub{}membuat sub (anonim?), Yang menjelaskan mengapa itu dihilangkan dari jawaban Perl6. Saya setuju dengan @nwellnhof bahwa Anda tidak boleh menghapus sub. (ketika saya masih aktif, seperti setahun yang lalu atau lebih, itu aturannya)
Dada
berubah sekarang. Dan termasuk $+[0].
Kjetil S.
2

Swift (pada platform 64-bit), 41 byte

Menyatakan penutupan yang disebut fmenerima dan mengembalikan Int. Solusi ini hanya bekerja dengan benar platform 64-bit, di mana Intadalah typealiased untuk Int64. (Pada platform 32-bit, Int64dapat digunakan secara eksplisit untuk tipe parameter penutupan, menambahkan 2 byte.)

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

Di Swift, bahkan tipe integer dasar adalah objek biasa yang dideklarasikan di pustaka standar. Ini berarti Intdapat memiliki metode dan properti, seperti leadingZeroBitCount(yang diperlukan pada semua jenis yang sesuai dengan FixedWidthIntegerprotokol perpustakaan standar ).

NobodyNada - Pasang kembali Monica
sumber
menarik. mengingatkan saya pada Rust. saya pikir itu harus dihitung sebagai 20 byte, .leadingZeroBitCount
don bright
2

Haskell , 24 byte

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

Cobalah online!

Ini pada dasarnya sama dengan solusi Java Kevin Cruijssen, tetapi saya menemukannya secara mandiri.

Argumen tersebut harus memiliki tipe Intuntuk build 64-bit, atau Int64untuk apa pun.

Penjelasan

Jika argumennya negatif, hasilnya langsung 0. Kalau tidak, kita bergeser ke kiri, mengisinya , sampai kita mencapai angka negatif. Pengisian itu memungkinkan kita menghindari kasus khusus untuk 0.

Hanya untuk referensi, inilah cara yang jelas / efisien:

34 byte

import Data.Bits
countLeadingZeros
dfeuer
sumber
1

Bersih , 103 byte

Menggunakan " bawaan " yang sama dengan jawaban ceilingcat.

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

Cobalah online!

Bersih , 58 byte

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

Cobalah online!

Suram
sumber
1

Perl 5 -p , 42 byte

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

Cobalah online!

Lebih lama dari solusi berbasis bitstring, tetapi solusi berbasis matematika yang layak.

Xcali
sumber
Tidak benar-benar berfungsi jika saya tidak salah
Dada
@Dada saya melihat bahwa ada beberapa kasus di mana divisi floating point tidak bekerja dengan baik. Saya melakukan intpanggilan yang harus menyelesaikan masalah.
Xcali
Maaf, sepertinya saya gagal menyalin-melewati. Ini yang ingin saya kirim;)
Dada
1

APL (NARS), 15 karakter, 30 byte

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

uji beberapa angka untuk melihat cara menggunakan:

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

K (ngn / k) , 6 byte

64-#2\

Cobalah online!

2\ menyandikan argumen dalam biner

# panjangnya

64- kurangi dari 64

ngn
sumber
# = length... tampak berbasis tali
Titus
2
@Itus 2\ memberikan daftar bilangan bulat dan #menemukan panjangnya. tidak ada ikatan yang terlibat di sini.
ngn
1

PHP, 50 46 byte

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

Jalankan sebagai pipa dengan -Ratau coba online ,

<?=$argn<0?0:0|64-log($argn+1,2);memiliki masalah pembulatan; jadi saya mengambil jalan panjang.

Titus
sumber
1

Bahasa Wolfram (Mathematica) , 41 byte

Formula untuk angka positif adalah adil 63-Floor@Log2@#&. Aturan penggantian digunakan untuk kasus khusus input nol dan negatif.

Input tidak harus berupa integer bertanda 64-bit. Ini secara efektif akan mengambil dasar input untuk mengubahnya menjadi integer. Jika Anda memasukkan angka di luar batas normal untuk integer 64-bit, ia akan memberi tahu angka negatif yang menunjukkan berapa banyak bit yang diperlukan untuk menyimpan integer ini.

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

Cobalah online!

Solusi @ LegionMammal978 sedikit lebih pendek pada 28 byte. Input harus berupa bilangan bulat. Per dokumentasi: " BitLength[n]secara efektif merupakan versi efisien Floor[Log[2,n]]+1." Secara otomatis menangani kasus nol pelaporan dengan benar 0daripada -∞.

Bahasa Wolfram (Mathematica) , 28 byte

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

Cobalah online!

Kelly Lowder
sumber
1
Boole[#>=0](64-BitLength@#)&sedikit lebih baik pada 28 byte. Ini menggunakan konsep dasar yang sama seperti milik Anda, tetapi berlaku BitLengthdan Boole.
LegionMammal978
Saya benar-benar lupa tentang BitLength!
Kelly Lowder
1

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

mis. 64 bit NUMBER: 9223372036854775807 math.ceil (math.log (9223372036854775807) / math.log (2)) ANS: 63

user90293
sumber
Jika Anda dapat menambahkan nama bahasa ke ini, itu akan menjadi luar biasa, karena orang-orang cenderung menurunkan jawaban yang tidak menyertakan nama bahasa
Jono 2906