Anda akan diberikan sebagai input bilangan bulat k
dalam rentang dari -4503599627370496
(−2 52 ) hingga 4503599627370496
(2 52 ). Seperti diketahui , bilangan bulat dalam kisaran ini dapat direpresentasikan tepat sebagai nilai floating-point presisi ganda.
Anda harus keluaran yang berat Hamming (jumlah orang) dari pengkodean k
dalam format yang binary64 . Ini menggunakan 1 bit untuk tanda, 11 bit untuk eksponen (dikodekan dengan offset), dan 52 bit untuk mantissa; lihat tautan di atas untuk detailnya.
Sebagai contoh , angka 22
direpresentasikan sebagai
0 10000000011 0110000000000000000000000000000000000000000000000000
Karena ada 5
, outputnya adalah 5
.
Perhatikan bahwa endianness tidak memengaruhi hasil, sehingga Anda dapat dengan aman menggunakan representasi internal aktual dari nilai presisi ganda untuk menghitung output.
Aturan tambahan
- Program atau fungsi diizinkan.
- Setiap bahasa pemrograman dapat digunakan.
- Celah standar dilarang
- Nomor input akan dalam desimal. Selain itu, sarana dan format input / output fleksibel seperti biasa.
- Kode terpendek dalam byte menang.
Uji kasus
22 -> 5
714 -> 6
0 -> 0
1 -> 10
4503599627370496 -> 5
4503599627370495 -> 55
1024 -> 3
-1024 -> 4
-4096 -> 5
1000000000 -> 16
-12345678 -> 16
sumber
binary64
format floating-point jika mereka mau? Beberapa orang (termasuk saya sendiri, awalnya) yang menafsirkan pertanyaan sebagai membutuhkan yang berfungsi menerima masukan sebagai tipe integer seperti Clong
. Di C, Anda dapat berargumen bahwa bahasa akan dikonversi untuk Anda, sama seperti ketika Anda meneleponsqrt((int)foo)
. Tetapi ada beberapa jawaban kode mesin x86 asm (seperti codegolf.stackexchange.com/a/136360/30206 dan milik saya) yang sama-sama berasumsi kita harus menerima input integer 64-bit. Menerimabinary64
nilai akan menghemat 5 byte.binary64
sebagai bilangan bulat basis2. Jika Anda perlu menanganinya secara terpisah, mungkin ada baiknya melakukan sesuatu selain mengetik-pun dan mengulangi semua bit.long
, jadi Anda tidak bisa hanya mengatakan binary64double
, karena tidak semua ganda adalah bilangan bulat. Tetapi semua nilai integerdouble
dapat dikonversi kelong
dan kembali, hingga bataslong
. (Seperti yang Anda tunjukkan, kebalikannya tidak benar. Anda mendapatkan representable terdekatdouble
, dengan asumsi mode pembulatan default). Bagaimanapun, ini adalah cara yang benar-benar valid untuk mengatur pertanyaan; Saya hanya tidak membacanya dengan cermat>. <Jawaban:
MATL , 5 byte
Cobalah online!
Transliterasi yang tepat dari jawaban MATLAB saya. Perhatikan bahwa input dan output bersifat implisit. -2 byte terima kasih kepada Luis Mendo.
sumber
bahasa mesin x86_64 (Linux), 16 byte
Menerima parameter integer 64-bit tunggal dalam
RDI
, mengubahnya menjadi nilai floating-pointXMM0
, menyimpan bit-bit itu kembaliRAX
, dan kemudian menghitung berat hammingRAX
, meninggalkan hasilnyaRAX
sehingga dapat dikembalikan ke pemanggil.Membutuhkan prosesor yang mendukung
POPCNT
instruksi, yang akan menjadi Intel Nehalem, AMD Barcelona, dan kemudian mikroarsitektur.Untuk Mencoba secara online! , kompilasi dan jalankan program C berikut:
sumber
objdump -drwC -Mintel
untuk membongkar dalam sintaks Intel. Jika Anda memiliki pointer dalam register yang bisa Anda gunakan untuk menyimpan / memuat ulang, Anda bisa menyimpan byte denganmovaps [rsi], xmm0
/popcnt rax, [rsi]
. (movaps hanya 3 byte, 2 lebih pendek dari movq.) Tapi itu tidak membantu di sini, karena[rsp-24]
membutuhkan 2 byte tambahan (SIB menggunakan RSP sebagai basis, plus disp8). Dan byte tambahan itu diperlukan baik di store maupun reload. Oh well, saya pikir saya melihat tabungan, tetapi tidak: /C (gcc) ,
8268 byte9 byte berkat Neil.
peretasan tingkat bit floating point jahat
Cobalah online!
sumber
;long l=
...;l*=2;)s+=l<0;
...long
. Ini bekerja pada x86-64 Linux, tetapi akan gagal pada Windows. Saya sarankan mengatakan "gcc dengan 64-bitlong
", karena gcc berjalan pada banyak platform, banyak dari mereka dengan ABI yang berbeda.Python 3 ,
7271 byteTerima kasih 1 byte untuk Lynn.
Cobalah online!
Penjelasan
Format binary64 terdiri dari tiga komponen:
1
jika angkanya negatifsumber
n and(…)-(n>0)
Apakah byte lebih pendek, bukan?C (gcc) , 47 byte
Ini tidak portabel; itu diuji dengan gcc 7.1.1 pada x86_64 yang menjalankan Linux, tanpa flag compiler.
Cobalah online!
sumber
long
kedouble
di situs panggilan?n
dirax
dengan un-kode dioptimalkan cukup cheesy. Itu rusak jika Anda mengaktifkan-O3
, jadi itu bukan hanya gcc pada umumnya, itu gcc pada x86-64 dengan 64-bitlong
dengan optimasi dinonaktifkan. Jika Anda memasukkan semua persyaratan itu ke dalam jawaban Anda, saya akan menang. Saya akan berasumsi ada platform yang mendukung gcc yang memiliki 64-bitlong
tetapi itu meninggalkanpopcountl
hasil dalam register selain dari register nilai-kembali.double
hal yang baik-baik saja. Itu tidak mengatakan apa-apa tentang memerlukan fungsi untuk menerimanya dalam format base2. Dan ya, berbagai versi gcc dapat memancarkan kode yang berbeda, jadi itu juga penting. (Fakta menyenangkan: tanpa-mpopcnt
, gcc tidak akan menggunakanpopcnt
insn, dan akan memancarkan urutan instruksi untuk menirunya. Beberapa arsitektur tidak memiliki instruksi popcnt sama sekali, jadi__builtin_popcountl
selalu harus menggunakan beberapa urutan insns)__builtin_*
fungsi (sebagian besar?) Memiliki versi lama untuk menghindari pembuatan instruksi ilegal. hanya-march=native
digunakanpopcntq
jika tersedia.Java (OpenJDK 8) , 92 byte
Cobalah online!
sumber
C (gcc), 63 byte
Solusi ini didasarkan pada jawaban @ LeakyNun, tetapi karena dia tidak ingin meningkatkan jawabannya sendiri, saya memposting di sini versi yang lebih golf.
Cobalah online
sumber
C #,
817068 byteSimpan 11 byte berkat @Leaky Nun.
Disimpan 2 byte berkat @Neil.
Cobalah online! Menggunakan
System.BitConverter.DoubleToInt64Bits
alih-alihunsafe
kode karena saya tidak bisa membuat TIO bekerja dengannya.Versi Lengkap / Diformat:
sumber
for(;l!=0;l*=2)
dan Anda tidak akan memerlukan ternarys-=l>>31
?s+=l<0?1:0
?l
panjang, jadi itu perlus-=l>>63
?Python 2 , 69 byte
-12 byte, terima kasih hanya untuk @ ASCII
Cobalah online!
sumber
!
tidak diperlukan karena urutan byte tidak masalah di siniJavaScript (ES6),
818077 byteSunting: Disimpan 1 byte berkat @Arnauld. Disimpan 3 byte berkat @DocMax.
sumber
g(i^i&-i,x++)
untuk -1 byte?new Float64Array([n])
denganFloat64Array.of(n)
kode mesin x86-64, 12 byte untuk
int64_t
input6 byte untuk
double
inputMembutuhkan
popcnt
ekstensi ISA (CPUID.01H:ECX.POPCNT [Bit 23] = 1
).(Atau 13 byte jika memodifikasi arg di tempat membutuhkan penulisan semua 64-bit, daripada meninggalkan sampah di atas 32. Saya pikir masuk akal untuk berargumen bahwa penelepon mungkin hanya ingin memuat 32b yang rendah, dan x86 nol -memperluas dari 32 ke 64 secara implisit dengan setiap operasi 32-bit. Namun, itu menghentikan penelepon untuk melakukan
add rbx, [rdi]
atau sesuatu.)Instruksi x87 lebih pendek daripada SSE2
cvtsi2sd
/ yang lebih jelasmovq
(digunakan dalam jawaban @ ceilingcat ), dan[reg]
mode pengalamatan berukuran sama denganreg
: hanya mod / byte byte.Kuncinya adalah menemukan cara agar nilai yang dilewatkan dalam memori, tanpa perlu terlalu banyak byte untuk menangani mode. (mis. meneruskan pada stack tidak terlalu bagus.) Untungnya, aturan memperbolehkan read / write args, atau memisahkan output args , jadi saya bisa membuat penelepon memberikan saya sebuah pointer ke memori yang saya boleh tulis.
Dipanggil dari C dengan tanda tangan:
void popc_double(int64_t *in_out);
Hanya 32b rendah dari hasilnya yang valid, yang mungkin aneh untuk C tetapi wajar untuk asm. (Memperbaiki ini membutuhkan awalan REX di toko akhir (mov [rdi], rax
), jadi satu byte lagi.) Di Windows, ubahrdi
kerdx
, karena Windows tidak menggunakan Sistem V ABI x86-64.Daftar NASM. TIO link memiliki kode sumber tanpa pembongkaran.
Cobalah online! Termasuk
_start
program pengujian yang memberikan nilai dan keluar dengan status keluar = nilai balik popcnt. (Buka tab "debug" untuk melihatnya.)Melewati pointer input / output yang terpisah juga akan berfungsi (rdi dan rsi di System86 ABI x86-64), tetapi kemudian kita tidak dapat menghancurkan input 64-bit atau dengan mudah membenarkan memerlukan buffer output 64-bit sementara hanya menulis rendah 32b.
Jika kita ingin berdebat bahwa kita dapat mengambil pointer ke integer input dan menghancurkannya, sambil mengembalikan output
rax
, maka cukup hilangkanmov [rdi], eax
daripopcnt_double_outarg
, turunkan menjadi 10 byte.Alternatif tanpa trik konvensi panggilan yang konyol, 14 byte
gunakan tumpukan sebagai ruang awal, dengan
push
untuk mendapatkannya di sana. Gunakanpush
/pop
untuk menyalin register dalam 2 byte, bukan 3 untukmov rdi, rsp
. ([rsp]
selalu membutuhkan SIB byte, jadi perlu menghabiskan 2 byte untuk menyalinrsp
sebelum tiga instruksi yang menggunakannya.)Panggilan dari C dengan tanda tangan ini:
int popcnt_double_push(int64_t);
Menerima input dalam
double
formatPertanyaannya hanya mengatakan itu adalah bilangan bulat dalam rentang tertentu, bukan karena itu harus dalam representasi bilangan bulat biner base2. Menerima
double
input berarti tidak ada gunanya menggunakan x87 lagi. (Kecuali jika Anda menggunakan konvensi panggilan kustomdouble
di mana s dilewatkan dalam register x87. Kemudian simpan ke zona merah di bawah tumpukan, dan muncul dari sana.)11 byte:
Tetapi kita dapat menggunakan trik pass-by-reference yang sama seperti sebelumnya untuk membuat versi 6-byte:
int pcd(const double&d);
6 byte .
sumber
Perl 5 ,
3332 + 1 (-p) =3433 byteDisimpan 1 byte berkat hobbs
Cobalah online!
sumber
d
kata kunci (pack d,$_
bukanpack"d",$_
)MATLAB, 36 byte
Menggunakan fakta yang
de2bi
tidak hanya lebih pendek daridec2bin
, tetapi juga memberikan hasil dalam satu dan nol daripada ASCII 48, 49.sumber
Java (64, 61, 41 byte)
Benar-benar mudah menggunakan perpustakaan standar (Java SE 5+):
Kontribusi oleh Kevin Cruijssen (Java SE 5+):
Kontribusi oleh Kevin Cruijssen (Java SE 8+, fungsi lambda):
sumber
Long n
dan menggunakann.bitCount(...)
sebagai gantinyaLong.bitCount(...)
. Selain itu, jika Anda menggunakan Java 8+, Anda dapat memasukkannya ken->n.bitCount(Double.doubleToLongBits(n))
( 41 byte )Hanya untuk mencoba yang berbeda, lebih aman dari- daripada TheLethalCoder , saya datang dengan ini (Sayang sekali C # memiliki nama metode yang panjang):
C # (.NET Core) , 76 + 13 byte
Cobalah online!
Jumlah byte termasuk 13 byte untuk
using System;
. Pertama, saya perlu mengonversikandouble
ke along
yang memiliki representasi biner yang sama, lalu saya dapat mengonversinya menjadi binerstring
, dan kemudian saya menghitung1
s hanya dengan memisahkan string dan menghitung substring minus 1.sumber
using
ke dalam byte byte Anda.namespace System.Linq;{d=>Convert.ToString(BitConverter.DoubleToInt64Bits(d),2).Count(c=>c>48)}
. Meskipun saya belum mengujinya, itu seharusnya berhasil.using
arahan kedua .namespace
berguna. Tapi ya dalam hal ini menghindari Linq sedikit lebih murah. Hanya ingin berkomentar dengan pendekatan itu jika Anda punya ide tentang cara mempersingkatnya untuk menghemat byte.Sum(c=>c&1)
lebih pendek. AtauSum()-768
Jelly , 19 byte
Cobalah online!
sumber
dc, 79 byte
Output dibiarkan di atas tumpukan.
Saya akan menambahkan penjelasan nanti.
Cobalah online!
Perhatikan bahwa angka negatif didahului oleh
_
, bukan-
.sumber
Groovy (dengan Parrot parser) , 46 byte
sumber
C, 67 byte
kode kontrol dan hasil
sumber
Erlang 55 byte
Fungsi anonim yang menghitung semua
1
s dalam angka yang dikodekan sebagai float 64 bit.referensi:
sumber