Temukan Nomor "Paling Sedikit" [tertutup]

Question

Tantangan

Diberikan daftar bilangan bulat, nomor "bittiest" di antara mereka adalah yang paling banyak bitnya - yaitu, jumlah bit terbesar diatur ke 1.

Tulis sebuah fungsi (atau program) yang menerima masukan daftar bilangan bulat 32-bit yang ditandatangani dan mengembalikan sebagai keluaran nomor "bittiest" di antara mereka.

Anda mungkin menganggap daftar tersebut memiliki setidaknya satu item.

Kasus Uji

Memasukkan: 1, 2, 3, 4

Keluaran: 3

Memasukkan: 123, 64, 0, -4

Keluaran: -4

Memasukkan: 7, 11

Output: Salah satu 7atau 11(tetapi tidak keduanya)

Memasukkan: 1073741824, 1073741823

Keluaran: 1073741823

Semoga berhasil

Ini adalah kode golf, jadi program terpendek dalam byte yang menang.

Klarifikasi

Jika bahasa Anda tidak mendukung bilangan bulat bertanda tangan 32-bit, Anda dapat menggunakan representasi numerik (baca: bukan tekstual) lainnya selama dapat mewakili semua bilangan bulat dari -2^31hingga 2^31 - 1inklusif, menggunakan komplemen dua untuk negatif.

Answer 1

Jelly , 13 12 8 byte

%Ø%B§µÞṪ

Cobalah secara online!

Penjelasan

     µÞ  | sort input by
%Ø%      | modulo by 2^32 (Ø% is a quick for 2^32)
   B     | converted to binary
    §    | sum
       Ṫ | get the last

Edit: terima kasih semua atas tanggapan yang baik untuk pertanyaan pertama saya! Saya pikir saya sudah memperbaikinya sekarang, tampaknya berfungsi untuk semua kasus uji.

Kode asli

2*31
B%¢S€iṀị

Answer 2

x86 Bahasa Mesin, 18 byte

31 D2 AD F3 0F B8 F8 39 FA 77 03 87 FA 93 E2 F2 93 C3 

Byte di atas mendefinisikan fungsi yang menerima alamat dari array di esiregister dan jumlah elemen dalam array di ecxregister, dan mengembalikan nomor "bittiest" di array di eaxregister.

Perhatikan bahwa ini adalah konvensi pemanggilan kustom yang menerima argumen di register ecxdan esi, tetapi sebaliknya seperti fungsi C yang mengambil panjang array dan penunjuk ke array sebagai dua argumennya. Konvensi pemanggilan kustom ini memperlakukan semua register sebagai caller-save, termasuk ebx.

Implementasi fungsi ini menarik beberapa trik kotor, yang mengasumsikan bahwa array memiliki setidaknya 1 elemen, seperti yang diatur dalam tantangan. Ini juga mengasumsikan bahwa arah flag ( DF) adalah clear ( 0), yang merupakan standar di semua konvensi pemanggilan yang saya ketahui.

Dalam mnemonik bahasa assembly yang tidak berstruktur:

; ecx = length of array
; esi = address of first element in array
Find:
    31 D2          xor    edx, edx                ; start with max bit count set to 0
Next:
    AD             lods   eax, DWORD PTR [esi]    ; load the next value from the array, and
                                                  ;   increment ptr by element size
    F3 0F B8 F8    popcnt edi, eax                ; count # of set bits in value
    39 FA          cmp    edx, edi                ; if # of set bits in value is less than
    77 03          ja     SHORT Skip              ;   the running maximum, skip next 2 insns
    87 FA          xchg   edx, edi                ; save current # of set bits (for comparisons)
    93             xchg   eax, ebx                ; save current array value (for comparisons)
Skip:
    E2 F2          loop   SHORT Next              ; decrement element count, looping until it is 0
    93             xchg   eax, ebx                ; move running maximum value to eax
    C3             ret                            ; return, with result in eax

Fitur kunci dari kode ini, tentu saja, popcntinstruksi x86 , yang menghitung jumlah bit set dalam sebuah integer. Ini melakukan iterasi melalui larik input, melacak nilai elemen maksimum dan jumlah bit set yang dikandungnya. Ia memeriksa setiap nilai dalam larik untuk melihat apakah jumlah bit setnya lebih tinggi dari nilai apa pun yang telah dilihat sebelumnya. Jika demikian, itu memperbarui nilai pelacakan; jika tidak, langkah ini dilewati.

The popcntinstruksi adalah besar (4-byte) instruksi, tapi tidak ada yang dapat dilakukan untuk menghindari itu. Namun, lodsinstruksi yang sangat pendek (1-byte) telah digunakan untuk memuat nilai-nilai dari array sambil menaikkan pointer secara bersamaan, loopinstruksi pendek (2-byte) telah digunakan untuk kontrol loop (secara otomatis mengurangi penghitung elemen dan melakukan perulangan selama karena ada lebih banyak elemen yang tersisa untuk dilalui), dan xchginstruksi yang sangat singkat (1-byte) telah digunakan di seluruh.

Ekstra xchgharus digunakan di akhir untuk mengaktifkan penggunaan lodsinstruksi, yang selalu dimuat ke eaxregister, tetapi trade-off itu lebih dari sepadan.

Cobalah secara online!

Upaya pertama saya adalah fungsi 20-byte. Sejauh ini, 18 byte adalah yang terbaik yang bisa saya hasilkan. Saya penasaran untuk melihat apakah ada orang lain yang bisa mengalahkan skor ini!

Satu-satunya rute perbaikan yang saya lihat adalah jika LOOPAada instruksi. Sayangnya, tidak — satu-satunya kode kondisi yang didukung oleh LOOPare E/ Zdan NE/ NZ. Tapi mungkin orang lain bisa memperluas pikiran mereka lebih jauh dariku!

Answer 3

JavaScript (ES6),  49 48 47  45 byte

2 byte disimpan berkat @ user81655

a=>a.sort(g=(p,q)=>!p|-!q||g(p&p-1,q&q-1))[0]

Cobalah secara online!

Bagaimana?

Kami .sort()daftar input dengan fungsi rekursif yang, diberikan pdan q, menghapus set bit paling tidak signifikan di setiap variabel sampai salah satunya sama dengan 0 (atau keduanya secara bersamaan). Ini memungkinkan untuk mengurutkan daftar dari kumpulan bit paling banyak hingga terkecil. Kami kemudian mengembalikan entri pertama, yaitu entri "bittiest".

Berkomentar

a =>                 // a[] = input list
  a.sort(            // sort a[] ...
    g = (p, q) =>    // ... using the recursive function g:
      !p | -!q       //     -> +1 if p = 0 and q ≠ 0,
                     //     or -1 if q = 0,
      ||             //     or  0 if p ≠ 0 and q ≠ 0, in which case ...
        g(           //     ... we do a recursive call:
          p & p - 1, //       clear the least significant bit set in p
          q & q - 1  //       clear the least significant bit set in q
        )            //     end of recursive call
  )[0]               // end of sort(); return the first entry

Answer 4

APL (Dyalog Unicode) , 15 byte

Banyak byte yang disimpan berkat Adam dan ngn.

{⊃⍒+⌿⍵⊤⍨32⍴2}⊃⊢

Cobalah secara online!

Answer 5

C (gcc) , ⁸⁰ 77 byte

Disimpan 3 byte berkat att !!!

#define b __builtin_popcount(f(n,l
f(n,l)int*l;{n=--n?f(n,l+(b))<b+1)))):*l;}

Cobalah secara online!

Answer 6

C ++ (GCC) , 145 141 140 135 134 133 130 128 116 bytes

145-> 141 berkat pengguna
128-> 116 berkat ceilingcat

#import<bits/stdc++.h>
int i,b,v,c;main(){for(;std::cin>>i;b<c?b=c,v=i:0)c=std::bitset<32>(i).count();std::cout<<v;}

Cobalah secara online!

Answer 7

Kotlin , 41 38 29 byte

Kode yang benar dengan byte yang jauh lebih sedikit :) {Terima kasih @vrintle}

{it.maxBy{it.countOneBits()}}

Kotlin Playground

---

{it.maxBy{it.toByte().countOneBits()}}

Kotlin Playground

---

{it.maxBy{it.toString(2).count{it=='1'}}}

Cobalah secara online!

Answer 8

05AB1E , 9 byte

ΣžJ%b1¢}θ

Cobalah secara online!

ΣžJ%b1¢}θ  # full program
        θ  # last element of...
           # implicit input...
Σ          # sorted in increasing order by...
      ¢    # number of...
     1     # ones...
      ¢    # in...
           # (implicit) current element in list...
   %       # modulo...
 žJ        # 4294967296...
    b      # in binary
           # implicit output

Answer 9

R , 58 55 54 byte

function(x)x[order(colSums(sapply(x,intToBits)<1))][1]

Cobalah secara online!

-2 Terima kasih kepada Robin Ryder

-1 berkat Dominic van Essen.

Answer 10

Stax , 18 byte

é·║⌂╞8Q⌡ë♀NM╟¥É▌╦!

Jalankan dan debug

Padatkan dengan 1s / 0s secara manual untuk mendapatkan representasi yang benar.

Menampilkan satu nomor untuk setiap testcase.

Answer 11

K (ngn / k) , 11 byte

{*x@>+/2\x}

Cobalah secara online!

Answer 12

Python 3 , 52 byte

lambda l:max(l,key=lambda n:bin(n%2**31).count("1"))

Cobalah secara online!

n%2**31- karena dalam bilangan bulat python tidak terbatas, harus mengubah angka negatif. misalnya -4menjadi2147483644

bin(...) - terjemahkan ke format biner

count("1") - hitung jumlah unit

---

Python 3 , 50 byte

lambda n:n and n%2+z(n//b)
f=lambda l:max(l,key=z)

Cobalah secara online!

dua byte lebih pendek, tetapi tidak berfungsi dengan angka negatif

Answer 13

Scala , 54 42 40 36 byte

Menyimpan beberapa byte berkat piramida dr batu kasar coinheringaahing, didymus, pengguna, dan beberapa tip

_.maxBy(_.toBinaryString.count(48<))

Cobalah secara online!

Answer 14

Husk , 17 16 13 byte

Edit: -1 byte berkat Razetime, dan kemudian -3 byte berkat Leo

►(ΣḋΩ≥0+^32 2

Cobalah secara online!

Husk secara native menggunakan bilangan bulat presisi sewenang-wenang, dan karenanya tidak memiliki gagasan tentang komplemen 32-bit 2 untuk mewakili bilangan bulat bertanda 4-byte negatif: sebagai hasilnya, fungsi 'dapatkan digit biner' - ḋ- sayangnya tidak berguna di sini untuk input negatif.
Jadi kita perlu menghitung '2's komplemen bittiness' dengan tangan.

Terima kasih atas bantuan Husk dari Leo untuk penggunaan di Ωsini.

►                       # element of input that maximises result of:
 (Σḋ                    # sum of binary digits of
    Ω                   # repeat until result is
     ≥0                 # greater than or equal to zero:
       +^32 2           # add 2^32

Answer 15

Java 10, 73 byte

a->{int r=0,m=0,t;for(var i:a)if((t=i.bitCount(i))>m){m=t;r=i;}return r;}

Cobalah secara online.

Penjelasan:

a->{                     // Method with Integer-array parameter and int return-type
  int r=0,               //  Result-integer, starting at 0
      m=0,               //  Maximum bit-count integer, starting at 0
      t;                 //  Temp integer, uninitialized
  for(var i:a)           //  Loop over each Integer in the input-array:
    if((t=i.bitCount(i)) //   If its amount of 1s in the binary representation
       >m){              //   is larger than the current maximum:
      m=t;               //    Update the maximum with this bit-count
      r=i;}              //    And update the result with this integer
  return r;}             //  After the loop, return the resulting integer

Answer 16

Jelly , 9 8 byte

%Ø%BSƲÞṪ

Cobalah secara online!

-1 byte dengan menggunakan Þ(sort) bukan ÐṀ(maksimum). Ini terinspirasi oleh jawaban Gio D dan setelah mereka dan saya edit, kedua solusi tersebut kurang lebih sama.

Penjelasan

%Ø%BSƲÞṪ   Main monadic link
      Þ    Sort by
     Ʋ     (
%            Modulo
 Ø%            2^32
   B         Binary
    S        Sum
     Ʋ     )
       Ṫ   Last item

Answer 17

Japt -h , 10 byte

ñÈu2pH)¤¬x

Cobalah

ñÈu2pH)¤¬x     :Implicit input of array
ñ              :Sort by
 È             :Passing each element through the following function
  u            :Positive modulo
   2p          :  2 raised to the power of
     H         :  32
      )        :End modulo
       ¤       :To binary string
        ¬      :Split
         x     :Reduce by addition
               :Implicit output of last element

Answer 18

Perl 5 , 54 byte

sub f{(sprintf"%b",@_)=~y/1//}($_)=sort{f($b)<=>f$a}@F

Cobalah secara online!

Answer 19

Ruby 2.7 , 36 33 34 byte

Terima kasih kepada Dingus karena telah mengoreksi kode saya untuk kasus khusus! :)

p$*.max_by{("%034b"%_1)[2,32].sum}

Cobalah secara online!

Menggunakan argumen baris perintah untuk input, menghasilkan angka bittiest sebagai string. TIO menggunakan versi Ruby yang lebih lama, sedangkan di Ruby 2.7, kami telah memberi nomor parameter, yang menghemat dua byte.

Answer 20

Java (JDK) , 44 byte

a->a.max((x,y)->x.bitCount(x)-x.bitCount(y))

Cobalah secara online!

Ini semacam kecurangan, karena menerima a Stream<Integer>sebagai masukan dan mengembalikan Optional<Int>.

Answer 21

Scala , 24 byte

_ maxBy Integer.bitCount

Cobalah secara online!

Berpisah dari jawaban pertama Gabber yang hebat .

Answer 22

C # (Visual C # Interactive Compiler) , 71 58 byte

l=>l.OrderBy(r=>Convert.ToString(r,2).Sum(c=>c-48)).Last()

Cobalah secara online!

• Refactored untuk menggunakan lambda seperti yang disarankan oleh @user di komentar

Answer 23

Arang , 22 byte

≔ＥθΣ⍘﹪ιＸ²¦³²¦²ηＩ§θ⌕η⌈η

Cobalah secara online! Tautan adalah untuk verbose versi kode. Penjelasan:

≔ＥθΣ⍘﹪ιＸ²¦³²¦²η

Untuk setiap nomor dalam daftar, transmisikan ke nomor 32-bit unsigned, konversikan ke biner, dan jumlahkan bit.

Ｉ§θ⌕η⌈η

Keluarkan angka pada posisi jumlah bit tertinggi.

Answer 24

SystemVerilog, 66 byte

Ini akan menjadi jawaban yang tidak sempurna untuk saat ini karena saya memposting dari ponsel saya, tetapi $countones()fungsi SV sempurna di sini.

function m(int q[$]);
m=q.max with ($countones(item));
endfunction

Answer 25

Bahasa Wolfram (Mathematica) , 39 byte

Last@*SortBy[Mod[#,2^32]~DigitCount~2&]

Cobalah secara online!

Answer 26

PowerShell, 53 56 byte

+5 byte karena tidak menangani negatif dengan benar
-2 byte berkat mazzy

$args|sort{$v=$_;0..31|%{$o+=!!(1-shl$_-band$v)};$o}-b 1

Answer 27

Nim , 75 byte

import algorithm,bitops
func b(n:seq):int=n.sortedByIt(it.countSetBits)[^1]

Cobalah secara online!

Answer 28

Zsh, 85 byte

coba online!

for i;{c=${#${(M)${(s::)$((i<0?[##2]2**32+i:[##2]i))}#1}}
((c>d))&&j=$i&&d=$c;}
<<<$j

Tantangan besar, membutuhkan Zshmantra teraneh ! Penjelasan:
_{for i;{... iterasi implisit atas semua argumen
$((i<0?[##2]2**32+i:[##2]i))... ubah ike format 32-bit, menggunakan trik pelengkap dua jika i<0
${#${(M)${(s::) //expression// }#1}}... perluas string ke array, hitung elemen yang (M) atch 1
((c>d))&&j=$i&&d=$c... lacak input mana yang imerupakan "bittiest" menurut hitungan c
<<<$j... menghasilkan pemenang}

Answer 29

J , 20 byte

{.@\:[:+/"1(32$2)&#:

Seperti yang tertulis, ketika diberi kelipatan yang sama, bilangan kecil maksimal, mengembalikan yang pertama dalam larik. Jika {.\:diubah menjadi {:/:, itu memberikan yang terakhir. Cobalah secara online!

Answer 30

AArch64, 48 44 byte

Instruksi mentah (32-bit little endian hex):

1e2703e4 bc404400 0e205801 2e303821
0ea43c23 2ea31c02 2ea31c24 f1000421
54ffff21 1e260040 d65f03c0

Perakitan tanpa komentar:

        .globl bittiest
bittiest:
        fmov    s4, #0
.Lloop:
        ldr     s0, [x0], #4
        cnt     v1.8b, v0.8b
        uaddlv  h1, v1.8b
        cmge    v3.2s, v1.2s, v4.2s
        bit     v2.8b, v0.8b, v3.8b
        bit     v4.8b, v1.8b, v3.8b
        subs    x1, x1, #1
        bne     .Lloop
        fmov    w0, s2
        ret

Penjelasan

Tanda tangan fungsi C:

int32_t bittiest(int32_t *words, size_t len);

Pseudo-C:

int32_t bittiest(int32_t *words, size_t len)
{
    int32_t maxcount = 0;
    int32_t maxvalue;
    do {
        int32_t value = *words++;
        int8_t counts[4] = popcount8x4((int8_t *)&value);
        int32_t count = counts[0] + counts[1] + counts[2] + counts[3];
        if (count >= maxcount) {
            maxvalue = value;
            maxcount = count;
        }
    } while (--len);
    return maxvalue;
}

Instruksi penghitungan populasi AArch64 ada di NEON (set instruksi SIMD / floating point), dan menghitung setiap byte secara individual. Oleh karena itu, agak canggung bekerja dengan skalar di sini jadi kami melakukan semuanya di NEON.

v4 adalah jumlah populasi maksimal (v4, s4, h4, dan d4 semuanya mengacu pada register yang sama). Setel ke 0.

        fmov    s4, #0

Muat kata int32 berikutnya ke dalam v0, dan tambahkan kata (x0) sebanyak 4.

        ldr     s0, [x0], #4

Simpan jumlah populasi setiap byte di v0 ke dalam byte yang sesuai di v1.

        cnt     v1.8b, v0.8b

Tambahkan semua jalur 8-bit di v1 bersama-sama untuk mendapatkan jumlah populasi penuh, dan simpan lagi ke dalam v1.

        uaddlv  h1, v1.8b

Bandingkan jumlah populasi kata ini dengan maksimal. Jika lebih besar atau sama, v3 akan menjadi semua 1 bit (benar), jika tidak semua akan menjadi 0 bit (salah).

        cmge    v3.2s, v1.2s, v4.2s

Jika v3 benar, atur kata maks (v2) ke kata saat ini. max tidak diinisialisasi pada iterasi pertama, tetapi akan selalu disetel karena jumlah populasi akan selalu> = 0.

        bit     v2.8b, v0.8b, v3.8b

Sama, tetapi untuk jumlah populasi maks baru.

        bit     v4.8b, v1.8b, v3.8b

Penurunan len (x1), dan lakukan loop jika bukan nol

        subs    x1, x1, #1
        bne     .Lloop

End of loop: Pindahkan nilai maksimum dari register NEON ke register return (w0), dan return.

        fmov    w0, s2
        ret

11 instruksi = 44 byte