Hitung jumlah yang dalam bilangan bulat 16-bit yang tidak ditandatangani

24

Tulis beberapa pernyataan yang akan menghitung jumlah yang dalam bilangan bulat enam belas bit yang tidak ditandatangani.

Misalnya, jika inputnya adalah 1337, maka hasilnya adalah 6karena 1337sebagai angka biner enam belas bit 0000010100111001, yang berisi enam angka .

ayane
sumber
2
Kiat: sama seperti beberapa digit dalam angka kongruen dengan angka mod 9, beberapa bit sama dengan angka mod 1.
PyRulez
8
@PyRulez Angka apa pun adalah nol modulo 1.
Thomas
1
Hai, Anda telah memilih jawaban yang salah sebagai jawaban yang diterima (dengan logika default tie breaker dari posting paling awal).
Pengoptimal
4
@ Thomas Saya tidak pernah mengatakan itu adalah tip yang membantu.
PyRulez
2
Mengapa pertanyaan ini menarik suara dekat SETELAH sebagian besar jawaban telah diposting? Tutup pemilih harap tunjukkan alasan Anda di komentar. Jika itu adalah penerimaan jawaban 4-byte es1024 (sangat pintar) yang tidak sesuai dengan celah standar (karena menggunakan builtin) tolong sebutkan bahwa ini adalah alasannya. Kalau tidak, apa itu?
Level River St

Jawaban:

37

80386 Kode Mesin, 4 byte

F3 0F B8 C1

yang mengambil bilangan bulat cxdan mengeluarkan hitungan ax, dan setara dengan:

popcnt ax, cx     ; F3 0F B8 C1

Dan berikut adalah solusi 11 10 byte yang tidak menggunakan POPCNT:

31 C0 D1 E9 10 E0 85 C9 75 F8

yang setara dengan:

xor ax, ax        ; 31 C0   Set ax to 0
shr cx, 1         ; D1 E9   Shift cx to the right by 1 (cx >> 1)
adc al, ah        ; 10 E0   al += (ah = 0) + (cf = rightmost bit before shifting)
test cx, cx       ; 85 C9   Check if cx == 0
jnz $-6           ; 75 F8   Jump up to shr cx, 1 if not
es1024
sumber
Apakah ini dalam mode 32-bit atau 16-bit (baik nyata atau dilindungi)?
FUZxxl
2
@ FuZxxl Rakitan yang disediakan adalah untuk 16-bit, meskipun mengganti axdan cxdengan eaxdan ecxmengubahnya menjadi 32-bit. Bytecode sama untuk keduanya.
es1024
1
@ es1024 Kode byte sama jika ini dikompilasi dalam mode 16-bit dan versi 32-bit dalam mode 32-bit.
Cole Johnson
2
Bukankah popcnt builtin dan dengan demikian jatuh dari celah standar? Masih kredit untuk solusi kedua.
Alchymist
5
Saat Anda mengklaim panjang kode mesin , bukankah judulnya harus "80386 Kode Mesin", bukan "80386 Assembler"?
Kevin Reid
14

Python 2, 17 byte

bin(s).count('1')

The binbuilt-in kembali integer dikonversi ke string biner. Kami kemudian menghitung 1digit:

>>> s=1337
>>> bin(s)
'0b10100111001'
>>> bin(s).count('1')
6
Ksatria Logika
sumber
11

J (5 karakter)

J tidak memiliki tipe eksplisit. Ini melakukan hal yang benar untuk semua bilangan bulat.

+/@#:
  • +/ jumlah
  • @ dari
  • #: representasi dasar dua
FUZxxl
sumber
11

C, 21

for(n=0;x;n++)x&=x-1;

Anda mengatakan "tulis beberapa pernyataan" (bukan "fungsi") jadi saya berasumsi nomornya disertakan xdan angka 1 dikembalikan n. Jika saya tidak perlu menginisialisasi, nsaya dapat menyimpan 3 byte.

Ini adalah adaptasi dari ekspresi terkenal x&x-1untuk menguji apakah sesuatu adalah kekuatan 2 (salah jika ya, benar jika tidak.)

Ini dia beraksi pada nomor 1337 dari pertanyaan. Perhatikan bahwa mengurangi 1 membalik 1 bit paling tidak signifikan dan semua nol ke kanan.

0000010100111001 & 0000010100111000 = 0000010100111000
0000010100111000 & 0000010100110111 = 0000010100110000
0000010100110000 & 0000010100101111 = 0000010100100000
0000010100100000 & 0000010100011111 = 0000010100000000
0000010100000000 & 0000010011111111 = 0000010000000000
0000010000000000 & 0000001111111111 = 0000000000000000

EDIT: untuk kelengkapan, inilah algoritma naif, yang satu byte lebih panjang (dan sedikit lebih lambat.)

for(n=0;x;x/=2)n+=x&1;
Level River St
sumber
1
@ edc65 sehingga ternyata, saya menemukan kembali kemudi. Setidaknya saya menyimpan 2 byte dengan menghilangkan {}. Ini adalah tugas yang sangat sederhana sehingga saya tidak perlu heran jika seseorang telah melakukannya.
Level River St
"Pertama kali diterbitkan pada tahun 1960" , mengesankan.
mbomb007
Algoritma koreksi ke naif:for(n=0;x;x/=2)n+=x&1;
Helios
1
@nmxprime OP meminta int unsigned. untuk -7 = 11111111 11111111 11111111 11111001 pada kompiler 32 bit saya, saya mendapatkan 30 untuk algoritma cepat, yang benar. Untuk algoritma naif, ia mengulangi melalui -7, -7 / 2 = -3, -3 / 2 = -1, -1 / 2 = 0. Itu memberikan jawaban yang salah. Mengubah x / = 2 menjadi x >> = 1 dapat memberikan jawaban yang benar pada beberapa kompiler, tetapi C tidak ditentukan apakah 1 atau 0 digeser ke dalam bit kosong untuk >> pada angka negatif. Kompilator yang menggeser 1 dalam akan masuk ke loop tak terbatas. Solusinya adalah mendefinisikan x sebagai int yang tidak ditandatangani. Kemudian x = -7 memuat (1 << 32) -7 = 4294967289 ke x.
Level River St
5

Jelly , tidak bersaing

Jawaban ini tidak bersaing, karena bahasa tersebut dibuat setelah tantangan diposting.

2 byte:

BS

Jelly adalah bahasa baru yang ditulis oleh @Dennis, dengan sintaksis mirip J.

         implicit: function of command-line arguments
B        Binary digits as list
 S       Sum

Coba di sini .

lirtosiast
sumber
4

Pyth, 4 byte

sjQ2

Program ini mengambil nomor yang berat hammingnya dapat ditemukan di STDIN.

isaacg
sumber
4

Julia, 29 27 19 byte

n->sum(digits(n,2))

Ini menciptakan fungsi anonim yang menerima satu argumen n,. Untuk menggunakannya, tetapkan ke sesuatu seperti f=n->...dan menyebutnya seperti f(1337).

The digits()fungsi, saat dipanggil dengan 2 argumen, mengembalikan array angka dari input di dasar diberikan. Jadi digits(n, 2)mengembalikan digit biner dari n. Ambil jumlah array dan Anda memiliki jumlah yang dalam representasi biner n.

Alex A.
sumber
Ini bisa menjadi jauh lebih singkat: Julia memiliki fungsicount_ones
Andrew mengatakan Reinstate Monica
@AndrewPiliser: Terima kasih atas sarannya, tetapi fungsi built-in yang tepat menyelesaikan tugas dianggap sebagai celah standar dan disukai ketika tidak secara eksplisit dianulir.
Alex A.
3

CJam, 6 byte

ri2b:+

ri         "Read the input and convert it to integer";
  2b       "Convert the integer into base 2 format";
    :+     "Sum the digits of base 2 form";

Cobalah online di sini

Pengoptimal
sumber
3

Joe , 4 byte

/+Ba

Ini adalah fungsi anonim. Bamemberikan representasi biner dari angka dan /+menjumlahkannya.

   (/+Ba)13
3
   (/+Ba)500
6
seequ
sumber
3

R, 24 byte

sum(intToBits(scan())>0)

scan() membaca input dari stdin.

intToBits()mengambil integer dan mengembalikan vektor tipe yang rawberisi nol dan representasi biner dari input.

intToBits(scan())>0mengembalikan vektor logis di mana setiap elemen adalah TRUEjika elemen vektor biner yang sesuai adalah 1 (karena semua elemen adalah 0 atau 1 dan 1> 0), jika tidak FALSE.

Dalam R, Anda dapat menjumlahkan vektor logis untuk mendapatkan jumlah TRUEelemen, jadi menjumlahkan vektor logis seperti di atas memberi kita apa yang kita inginkan.

Catatan yang sum()tidak dapat menangani rawinput secara langsung, oleh karena itu solusinya menggunakan logika.

Alex A.
sumber
Tidak sum(intToBits(scan()))akan sama?
seequ
@ Sieg: Sayangnya tidak ada karena sum()tidak dapat mengambil input tipe raw, dari mana kembali intToBits().
Alex A.
Itu sangat aneh bagi saya.
seequ
1
@ Sieg: Ya, itu aneh bagi saya juga. Baiklah. Jika setiap porkchop sempurna, kami tidak akan memiliki hotdog.
Alex A.
Dan itu adalah metafora paling aneh yang pernah ada.
seequ
3

Ruby, 18 byte

n.to_s(2).count'1'

GreyCat
sumber
1
n.to_s(2).count ?1juga bekerja, tetapi memiliki panjang yang sama
Piccolo
Versi 2019: n.digits (2) .sum / 15 byte
GB
3

Keempat, 48 49 byte

: c ?dup if dup 1- and recurse 1+ then ;
0 1337 c

Jika fungsi aktual diperlukan maka baris kedua menjadi

: c 0 swap c ;

dan Anda menyebutnya dengan "1337 c". Kata-kata kontrol Forth yang relatif verbose membuat ini sulit (sebenarnya, mereka membuat banyak ini sulit).

Sunting: Versi saya sebelumnya tidak menangani angka negatif dengan benar.

Nagora
sumber
3

Mathematica, 22 18 byte

Terima kasih kepada alephalpha untuk mengingatkan saya pada DigitCount.

DigitCount[#,2,1]&
Martin Ender
sumber
@alephalpha terima kasih, tetapi DigitCount mengambil parameter lain :)
Martin Ender
3

ES6 (34 22 21 byte):

Ini adalah fungsi rekursif sederhana yang dapat disingkat lebih sedikit. Hanya perlu sedikit dan berjalan sendiri lagi:

B=n=>n&&(1&n)+B(n>>1)

Cobalah di http://www.es6fiddle.net/imt5ilve/ (Anda memerlukannya varkarena 'use strict';).

Aku tidak percaya aku telah mengalahkan Fish !!!

Yang tua:

n=>n.toString(2).split(1).length-1

ES5 (39 byte):

Kedua fungsi dapat dengan mudah disesuaikan dengan ES5:

function B(n){return n?(1&n)+B(n>>1):0}

//ungolfed:

function B(number)
{
    if( number > 0 )
    {
        //arguments.callee points to the function itself
        return (number & 1) + arguments.callee( number >> 1 );
    }
    else
    {
        return 0;
    }
}

Yang lama:

function(n){return n.toString(2).split(1).length-1}

@ user1455003 memberi saya ide yang sangat bagus, yang 'memicu' yang terkecil:

function B(n,x){for(x=0;n;n>>=1)x+=n&1;return x}

Saya telah mengadaptasinya ke ES6 dan membuatnya rekursif untuk mempersingkat banyak!

Ismael Miguel
sumber
1
Inilah fungsi javascript 'reguar' yang lebih kecil. fungsi B (n, x) {untuk (x = 0; n; n >> = 1) x + = n & 1; kembali x}
wolfhammer
@ user1455003 Terima kasih BANYAK atau saran Anda! Saya sudah menggunakannya dan mengadaptasinya ke ES6 dan lebih pendek. Terima kasih!
Ismael Miguel
Sama-sama! Saya suka apa yang Anda lakukan dengan itu. Dengan rekursi javascript biasa turun ke 39! function B (n) {return n? (1 & n) + B (n >> 1): 0}
wolfhammer
@ user1455003 Jika Anda mau, Anda dapat mengedit bagian ES5 dan menambahkan jumlah byte ke versi golf. (Saya pikir Anda memenangkan reputasi dengan suntingan).
Ismael Miguel
@ user81655 WOW! Berhasil!!! Terima kasih banyak! Saya benar-benar tahu ini bisa dibuat lebih singkat
Ismael Miguel
2

> <> (Ikan) , 24 byte + 2 = 26

0$11.>~n;
2,:?!^:2%:{+}-

Program hanya mengulangi mod 2, kurangi dan bagi sampai jumlah input menjadi nol, lalu cetak jumlah mod 2s.

Uji dengan -vbendera, mis

py -3 fish.py ones.fish -v 1337
Sp3000
sumber
Untuk integer 16bit, input codepoint mungkin tidak memadai. (Versi -vbendera masih berfungsi.)
randomra
@randomra Sialan, kau benar. Sementara input Unicode bekerja, 16-bit hanya beberapa perintah yang besarnya di luar jangkauan ...
Sp3000
2

PHP (38 byte):

Ini menggunakan pendekatan yang sama dengan jawaban ES6 saya

<?=count(split(1,decbin($_GET[n])))-1;

Ini adalah kode lengkap, Anda hanya perlu memasukkannya ke dalam file dan mengaksesnya melalui browser, dengan parameter n=<number>.

PHP <4.2 (32 byte):

Ini sedikit lebih pendek:

<?=count(split(1,decbin($n)))-1;

Ini hanya berfungsi dengan baik pada PHP <4.2 karena arahan register_globalsdiatur ke Offdefault dari PHP4.2 hingga PHP5.4 (yang telah dihapus saat itu).

Jika Anda membuat php.inifile dengan register_globals=On, ini akan berfungsi.

Untuk menggunakan kode, akses file menggunakan browser, dengan POST atau GET.

@ViniciusMonteiro 's saran (38/45 bytes):

Dia memberikan 2 saran yang sangat bagus yang memiliki fungsi penggunaan yang sangat menarik array_sum:

38 byte:

<?=array_sum(str_split(decbin(1337)));

45 byte:

<?=array_sum(preg_split('//', decbin(1337)));

Ini adalah ide yang sangat bagus dan dapat dipersingkat lebih lama, menjadi 36 byte:

<?=array_sum(split(1,decbin(1337)));
Ismael Miguel
sumber
2
Atau Anda dapat menggunakan echo array_sum (str_split (decbin (1337))); dan Anda dapat menggunakan terlalu echo array_sum (preg_split ('//', decbin (1337)));
Vinicius Monteiro
1
@ViniciusMonteiro Terima kasih banyak atas saran Anda. Saya sangat menyukainya! Saya telah menambahkannya ke jawabannya.
Ismael Miguel
Dapatkan empat byte menggunakan <?=substr_count(decbin(1337),"1");(34 byte)
Cogicero
1
@Cogicero Dan Anda dapat menyimpan lebih banyak dengan menghapus tanda kutip: <?=substr_count(decbin(1337),1);. Itu adalah total 32 byte. Mengingat kode ini cukup berbeda, bukankah Anda ingin mempostingnya sebagai jawaban Anda sendiri? Saya yakin akan mengungguli itu!
Ismael Miguel
@Cogicero Hanya dua byte lebih pendek jika Anda menggunakan parametrization: <?=substr_count(decbin($argv[1]),1);(atau $_GET[n]; 36 byte)
Titus
2

C #, 45 byte

Convert.ToString((ushort)15,2).Sum(b=>b-48);

https://dotnetfiddle.net/kJDgOY

albertjan
sumber
b-48bahkan lebih pendek, AFAIK
ThreeFx
Benar! :) Saya akan memperbarui.
albertjan
2

Japt, 3 byte (tidak kompetitif)

¢¬x

Coba di sini.

Mama Fun Roll
sumber
Sobat, saya tidak pernah melihat tanggal itu untuk beberapa alasan.
Mama Fun Roll
1
Haha, Japt adalah yang terpendek: D BTW, ¢o1 lakan bekerja juga. Pendekatan lain yang menarik adalah -¢¬r-0; ¢¬membagi menjadi array angka biner, r-0mengurangi dengan mengurangi, mulai dari 0, dan -meniadakan hasilnya, menjadikannya positif.
ETHproduk
Sampai semalam, Anda sekarang dapat menggunakan ¢¬x.
ETHproductions
2

lilin lebah ,31 27 byte

Jawaban tidak bersaing. Lilin lebah lebih baru dari tantangan ini.

Solusi ini menggunakan cara Brian Kherigan untuk menghitung bit yang ditetapkan dari situs web "Bit Twiddling Hacks".

itu hanya berjalan melalui loop, menambah jumlah bit, sementara iterasi number=number&(number-1)sampai number = 0. Solusinya hanya melewati loop sesering ada bit yang ditetapkan.

Saya bisa mencukur 4 byte dengan mengatur ulang beberapa instruksi. Kode sumber dan penjelasan diperbarui:

pT_
>"p~0+M~p
d~0~@P@&<
{@<

Penjelasan:

pT_            generate IP, input Integer, redirect
>"             if top lstack value > 0 jump next instruction,
               otherwise continue at next instruction
  p            redirect if top lstack value=0 (see below)
   ~           flip top and 2nd lstack values
    0+         set top lstack value to 0, set top=top+2nd
      M        decrement top lstack value
       ~       flip top and 2nd lstack values
        p      redirect to lower left
        <      redirect to left
       &       top=top&2nd
      @        flip top and 3rd lstack values
    @P         increment top lstack value, flip top and 3rd values
 ~0~           flip top and 2nd values, set top=0, flip top and 2nd again
d              redirect to upper left
>"p~0+M.....   loop back

  p            if top lstack = 0 at " instruction (see above), redirect
  0            set lstack top to zero (irrelevant instruction)
  <            redirect to the left
 @             flip top and 3rd lstack values
{              output top lstack value as integer (bitcount)

Klon repositori GitHub saya yang berisi juru bahasa lilin lebah, spesifikasi bahasa, dan contoh-contoh.

ML
sumber
1

Java, 17 byte

Bekerja untuk byte, short, char, dan int. Gunakan sebagai lambda.

Integer::bitCount

Tes di sini

Tanpa menggunakan built-in:

42 byte

s->{int c=0;for(;s!=0;c++)s&=s-1;return c}

Tes di sini

TheNumberOne
sumber
6
ini adalah celah standar: fungsi builtin yang melakukan persis apa yang Anda inginkan dilarang.
FUZxxl
@FUZxxl OP tidak pernah melarang celah standar
Cole Johnson
1
@ColeJohnson Celah standar diasumsikan ditutup secara default
es1024
6
@FUZxxl Sementara es1024 benar bahwa celah standar ditutup secara default, menggunakan fungsi bawaan saat ini bukan celah yang diterima pada perincian suara +43 / -26.
Martin Ender
1

Klip , 6

2 cara:

cb2nx1

Ini adalah terjemahan langsung dari persyaratan: hitungan yang ada di representasi angka-2 basis.

r+`b2n

Metode lain, yang mengambil jumlah digit dari representasi basis-2.

Ypnypn
sumber
1

Oktaf, 18

sum(dec2bin(s)-48)

Contoh:

octave:1> s=1337
s =  1337
octave:2> sum(dec2bin(s)-48)
ans =  6
alephalpha
sumber
1

GML (Game Maker Language), 21 byte

for(n=0;x;n/=2)n+=x&1
Timtech
sumber
1

C # 39 byte

Convert.ToString(X,2).Count(C=>C=='1');
sbecker
sumber
1

Perl, 21

$r=grep$v&1<<$_,0..15
nutki
sumber
1

PowerShell (51 byte)

"$([char[]][convert]::ToString($s,2)|%{"+$_"})"|iex

Penjelasan:
[convert]::ToString($s,2)menghasilkan representasi string biner dari $s.
[char[]]melemparkannya sebagai array char dan memungkinkan kita untuk menghitung setiap char.
|%{"+$_"}menambahkan setiap karakter dengan tanda +
"$()"secara implisit memanggil .ToString()sub ekspresi yang dihasilkan
|iexmenjumlahkan string yang disalurkan (mis. "+1 +0 +1 +1 +0 +1 +0 +0" = 4)

Mathias R. Jessen
sumber
Hai! Mengikuti logika yang sama yang Anda miliki, mengapa tidak menggunakan -joinoperator sebaris dan implisit .ToString()untuk mencapai 45 byte dengan [char[]][convert]::ToString($s,2)-join'+'|iex... ATAU, sebagai pendekatan yang berbeda gunakan -replaceoperator sebaris untuk mencapai 43 byte dengan([convert]::ToString($s,2)-replace0).length
AdmBorkBork
1

Clojure, 42 byte

#(count(filter #{\1}(Long/toString % 2)))

Membaca dari kanan ke kiri, mengonversi ke string biner, mengonversi ke urutan karakter, memfilter 1s dan menghitung berapa banyak yang Anda miliki.

Diedit dengan bantuan dari Sieg

Neil Masson
sumber
42:#(count(filter #{\1}(Integer/toString% 2)))
seequ
Anda memerlukan satu karakter lagi#(count(filter #{\1}(Integer/toString % 2)))
Neil Masson
Tidak, kamu tidak. :)
seequ
Inilah yang saya dapatkan ketika saya mencobanya:CompilerException java.lang.IllegalArgumentException: No matching method: toString_PERCENT_
Neil Masson
Saya mengujinya di Try Clojure. Tampaknya halaman itu tiba-tiba tidak dikenali Integer/toString. Tapi itu berhasil sedetik yang lalu.
seequ
1

Haskell 42 karakter

t 0=[]
t n=t(quot n 2)++[rem n 2]
f=sum.t

mendeklarasikan penggunaan fungsi f :: Integer -> Integer
dari interpreter interaktif sebagai f <number>atau menambahkan baris main=print$f <number>ke akhir file.

HEGX64
sumber
Anda dapat menyimpan banyak byte dengan langsung menjumlahkan rem n 2s alih-alih membangun daftar itu dan dengan menggunakan divalih-alih quot: t 0=0 t n=t(div n 2)+rem n 2- tidak flagi.
nimi
1

Matlab, 13 byte

de2bimembuat vektor nol dan yang mewakili angka biner, dan sumhanya mengembalikan jumlah semua entri.

sum(de2bi(n))
cacat
sumber
1

𝔼𝕊𝕄𝕚𝕟, 4 karakter / 11 byte (tidak kompetitif)

⨭⟦ïⓑ

Try it here (Firefox only).

Penjelasan

Mengonversi input ke biner, membelah karakter, dan mendapatkan jumlah array yang dihasilkan.

Mama Fun Roll
sumber