ค้นหาหมายเลข“ Bittiest” [ปิด]

Question

ความท้าทาย

จากรายการจำนวนเต็มจำนวนที่ "bittiest" ในหมู่พวกเขาคือจำนวนที่มีบิตมากที่สุดนั่นคือจำนวนบิตที่มากที่สุดที่กำหนดเป็น 1

เขียนฟังก์ชัน (หรือโปรแกรม) ที่ป้อนรายการของจำนวนเต็ม 32 บิตที่เซ็นชื่อแล้วส่งกลับเป็นเอาต์พุตตัวเลขที่ "bittiest" ในหมู่พวกเขา

คุณอาจถือว่ารายการมีอย่างน้อยหนึ่งรายการ

กรณีทดสอบ

อินพุต: 1, 2, 3, 4

เอาท์พุต: 3

อินพุต: 123, 64, 0, -4

เอาท์พุต: -4

อินพุต: 7, 11

เอาต์พุต: อย่างใดอย่างหนึ่ง7หรือ11(แต่ไม่ใช่ทั้งสองอย่าง)

อินพุต: 1073741824, 1073741823

เอาท์พุต: 1073741823

โชคดี

นี่คือโค้ดกอล์ฟดังนั้นโปรแกรมที่สั้นที่สุดในหน่วยไบต์จึงชนะ

การชี้แจง

หากภาษาของคุณไม่รองรับจำนวนเต็ม 32 บิตที่มีการเซ็นชื่อคุณสามารถใช้การแทนค่าตัวเลขอื่น ๆ (อ่าน: ไม่ใช่ข้อความ) ได้ตราบเท่าที่สามารถแสดงจำนวนเต็มทั้งหมดจาก-2^31ถึง2^31 - 1รวมโดยใช้สองส่วนเติมเต็มสำหรับเชิงลบ

Answer 1

เจลลี่ , 13 12 8 ไบต์

%Ø%B§µÞṪ

ลองออนไลน์!

คำอธิบาย

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

แก้ไข: ขอบคุณทุกคนสำหรับการตอบคำถามแรกของฉัน! ฉันคิดว่าฉันได้แก้ไขแล้วดูเหมือนว่าจะใช้ได้กับทุกกรณีทดสอบ

รหัสเดิม

2*31
B%¢S€iṀị

Answer 2

x86 ภาษาเครื่อง 18 ไบต์

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

ไบต์ข้างต้นกำหนดฟังก์ชันที่ยอมรับที่อยู่ของอาร์เรย์ในesiรีจิสเตอร์และจำนวนองค์ประกอบในอาร์เรย์ในecxรีจิสเตอร์และส่งกลับหมายเลข "bittiest" ในอาร์เรย์ในeaxรีจิสเตอร์

โปรดทราบว่านี่เป็นรูปแบบการเรียกแบบกำหนดเองที่ยอมรับอาร์กิวเมนต์ในecxและesiรีจิสเตอร์ แต่อย่างอื่นก็เหมือนกับฟังก์ชัน C ที่ใช้ความยาวของอาร์เรย์และตัวชี้ไปยังอาร์เรย์เป็นสองอาร์กิวเมนต์ ebxที่กำหนดเองนี้เรียกประชุมถือว่าการลงทะเบียนทั้งหมดเป็นโทรบันทึกรวมทั้ง

การใช้งานฟังก์ชั่นนี้ดึงลูกเล่นสกปรกออกมาซึ่งสมมติว่าอาร์เรย์มีองค์ประกอบอย่างน้อย 1 รายการตามที่ระบุไว้ในการท้าทาย นอกจากนี้ยังถือว่าธงทิศทาง ( DF) ชัดเจน ( 0) ซึ่งเป็นมาตรฐานในรูปแบบการเรียกทั้งหมดที่ฉันทราบ

ในการจำภาษาแอสเซมบลีที่ไม่มีการเปลี่ยนแปลง:

; 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

คุณสมบัติที่สำคัญของรหัสนี้คือpopcntคำสั่งx86 ซึ่งจะนับจำนวนบิตที่กำหนดเป็นจำนวนเต็ม มันวนซ้ำผ่านอาร์เรย์อินพุตติดตามทั้งค่าขององค์ประกอบสูงสุดและจำนวนบิตชุดที่ประกอบด้วย ตรวจสอบแต่ละค่าในอาร์เรย์เพื่อดูว่าจำนวนบิตที่กำหนดไว้สูงกว่าค่าใด ๆ ที่เคยเห็นมาก่อนหรือไม่ หากเป็นเช่นนั้นระบบจะอัปเดตค่าการติดตาม ถ้าไม่เช่นนั้นจะข้ามขั้นตอนนี้ไป

popcntการเรียนการสอนเป็นคำแนะนำที่มีขนาดใหญ่ (4 ไบต์) แต่ไม่มีอะไรที่สามารถทำได้เพื่อหลีกเลี่ยงการที่ อย่างไรก็ตามlodsคำสั่งสั้นมาก (1 ไบต์) ถูกใช้เพื่อโหลดค่าจากอาร์เรย์ในขณะที่เพิ่มตัวชี้ไปพร้อม ๆ กันloopคำสั่งสั้น (2 ไบต์) ถูกใช้สำหรับการควบคุมลูป (ลดตัวนับองค์ประกอบโดยอัตโนมัติและการวนซ้ำตามความยาว เนื่องจากมีองค์ประกอบอีกมากที่ต้องผ่าน) และคำสั่งสั้น ๆ (1 ไบต์) xchgจึงถูกนำมาใช้ตลอด

ต้องใช้สิ่งพิเศษxchgในตอนท้ายเพื่อเปิดใช้งานlodsคำสั่งซึ่งจะโหลดลงeaxทะเบียนเสมอ แต่การแลกเปลี่ยนนั้นคุ้มค่ากว่า

ลองออนไลน์!

ความพยายามครั้งแรกของฉันคือฟังก์ชัน 20 ไบต์ จนถึงตอนนี้ 18 ไบต์เป็นสิ่งที่ดีที่สุดที่ฉันสามารถทำได้ ฉันอยากรู้อยากเห็นว่ามีใครเอาชนะคะแนนนี้ได้บ้าง!

เส้นทางเดียวของการปรับปรุงที่ฉันเห็นคือถ้ามีLOOPAคำสั่ง แต่น่าเสียดายที่มัน doesn't-เพียงรหัสเงื่อนไขการสนับสนุนโดยLOOPจะE/ Zและ/NE NZแต่อาจจะมีคนอื่นยืดอกไปได้ไกลกว่าฉัน!

Answer 3

JavaScript (ES6),  49 48 47  45 ไบต์

บันทึก 2 ไบต์ขอบคุณ @ user81655

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

ลองออนไลน์!

อย่างไร?

เรา.sort()เป็นรายการอินพุตที่มีฟังก์ชันวนซ้ำที่กำหนดpและqล้างบิตที่มีนัยสำคัญน้อยที่สุดที่ตั้งไว้ในแต่ละตัวแปรจนกว่าหนึ่งในนั้นจะมีค่าเท่ากับ 0 (หรือทั้งสองอย่างพร้อมกัน) สิ่งนี้อนุญาตให้จัดลำดับรายการจากชุดบิตส่วนใหญ่ไปหาน้อยที่สุด จากนั้นเราจะส่งคืนรายการแรกคือรายการที่ "bittiest"

แสดงความคิดเห็น

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 ไบต์

บันทึกหลายไบต์ขอบคุณ Adam และ ngn

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

ลองออนไลน์!

Answer 5

C (GCC) , ⁸⁰ 77 ไบต์

บันทึก 3 ไบต์ขอบคุณatt !!!

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

ลองออนไลน์!

Answer 6

c ++ (GCC) , 145 141 140 135 134 133 130 128 116 ไบต์

145-> 141 ขอบคุณผู้ใช้
128-> 116 ขอบคุณ 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;}

ลองออนไลน์!

Answer 7

Kotlin , 41 38 29 ไบต์

แก้ไขโค้ดโดยมีจำนวนไบต์น้อยลงมาก :) {ขอบคุณ @vrintle}

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

สนามเด็กเล่น Kotlin

---

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

สนามเด็กเล่น Kotlin

---

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

ลองออนไลน์!

Answer 8

05AB1E , 9 ไบต์

ΣžJ%b1¢}θ

ลองออนไลน์!

Σž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 ไบต์

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

ลองออนไลน์!

-2 ขอบคุณ Robin Ryder

-1 ขอบคุณ Dominic van Essen

Answer 10

Stax , 18 ไบต์

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

เรียกใช้และแก้ไขข้อบกพร่อง

แผ่นอิเล็กโทรดด้วยตนเองด้วย 1s / 0s เพื่อให้ได้การแสดงที่ถูกต้อง

แสดงหมายเลขเดียวสำหรับแต่ละกรณีทดสอบ

Answer 11

K (ngn / k) , 11 ไบต์

{*x@>+/2\x}

ลองออนไลน์!

Answer 12

Python 3 , 52 ไบต์

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

ลองออนไลน์!

n%2**31- เนื่องจากใน python จำนวนเต็มไม่มีที่สิ้นสุดต้องเปลี่ยนจำนวนลบ ตัวอย่างเช่น-4กลายเป็น2147483644

bin(...) - แปลเป็นรูปแบบไบนารี

count("1") - นับจำนวนหน่วย

---

Python 3 , 50 ไบต์

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

ลองออนไลน์!

สั้นกว่าสองไบต์ แต่ใช้ไม่ได้กับจำนวนลบ

Answer 13

Scala , 54 42 40 36 ไบต์

บันทึกไบต์บางส่วนด้วย caird coinheringaahing, Didymus, ผู้ใช้และเคล็ดลับ

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

ลองออนไลน์!

Answer 14

Husk , 17 16 13 ไบต์

แก้ไข: -1 ไบต์ขอบคุณ Razetime แล้วก็ขอบคุณลีโอ 3 ไบต์

►(ΣḋΩ≥0+^32 2

ลองออนไลน์!

Huskใช้จำนวนเต็มที่มีความแม่นยำตามอำเภอใจโดยกำเนิดดังนั้นจึงไม่มีความคิดเกี่ยวกับส่วนเติมเต็มของ 32 บิต 2 สำหรับการแทนจำนวนเต็มลบ 4 ไบต์ที่มีการลงนามดังนั้นฟังก์ชัน 'รับเลขฐานสอง' ḋจึงไร้ประโยชน์สำหรับอินพุตเชิงลบ
ดังนั้นเราต้องคำนวณ 'ความขมเสริม 2' ด้วยมือ

ขอขอบคุณความช่วยเหลือจากHuskจากLeoสำหรับการใช้งานΩที่นี่

►                       # 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 ไบต์

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

ลองออนไลน์

คำอธิบาย:

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

เจลลี่ , 9 8 ไบต์

%Ø%BSƲÞṪ

ลองออนไลน์!

-1 ไบต์โดยใช้Þ(เรียงลำดับ) แทนÐṀ(สูงสุด) สิ่งนี้ได้รับแรงบันดาลใจจากคำตอบของ Gio D และหลังจากการแก้ไขของพวกเขาและของฉันโซลูชันทั้งสองก็เหมือนกันมาก

คำอธิบาย

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

Answer 17

Japt -h , 10 ไบต์

ñÈu2pH)¤¬x

ลองมัน

ñÈ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 ไบต์

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

ลองออนไลน์!

Answer 19

Ruby 2.7 , 36 33 34 ไบต์

ขอบคุณDingusสำหรับการแก้ไขรหัสของฉันเป็นกรณีพิเศษ! :)

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

ลองออนไลน์!

ใช้อาร์เรย์บรรทัดคำสั่งสำหรับอินพุตเอาต์พุตตัวเลขที่บิตที่สุดเป็นสตริง TIO ใช้ Ruby เวอร์ชันเก่ากว่าในขณะที่ Ruby 2.7 เราได้กำหนดหมายเลขพารามิเตอร์ซึ่งจะช่วยประหยัดสองไบต์

Answer 20

Java (JDK) , 44 ไบต์

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

ลองออนไลน์!

นี่คือการโกงเนื่องจากยอมรับ a Stream<Integer>เป็นอินพุตและส่งกลับOptional<Int>ไฟล์.

Answer 21

Scala , 24 ไบต์

_ maxBy Integer.bitCount

ลองออนไลน์!

แยกออกจากGabber ของดีคำตอบแรก

Answer 22

C # (Visual C # Interactive Compiler) , 71 58 ไบต์

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

ลองออนไลน์!

• Refactored เพื่อใช้ lambda ตามที่ @user แนะนำในความคิดเห็น

Answer 23

ถ่าน 22 ไบต์

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

ลองออนไลน์! ลิงก์คือรหัสเวอร์ชันที่ละเอียด คำอธิบาย:

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

สำหรับแต่ละหมายเลขในรายการให้ส่งเป็นหมายเลขที่ไม่ได้ลงชื่อ 32 บิตแปลงเป็นเลขฐานสองและรวมบิต

Ｉ§θ⌕η⌈η

แสดงตัวเลขที่ตำแหน่งของจำนวนบิตสูงสุด

Answer 24

SystemVerilog, 66 ไบต์

นี่จะเป็นคำตอบที่ไม่สมบูรณ์สำหรับตอนนี้เนื่องจากฉันโพสต์จากโทรศัพท์ แต่$countones()ฟังก์ชันของ SV นั้นสมบูรณ์แบบ

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

Answer 25

ภาษา Wolfram (Mathematica) , 39 ไบต์

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

ลองออนไลน์!

Answer 26

PowerShell, 53 56 ไบต์

+5 ไบต์เนื่องจากไม่ได้จัดการเชิงลบอย่างถูกต้อง
-2 ไบต์ขอบคุณ mazzy

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

Answer 27

Nim , 75 ไบต์

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

ลองออนไลน์!

Answer 28

Zsh 85 ไบต์

ลองออนไลน์!

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

ความท้าทายที่ยิ่งใหญ่ต้องใช้Zshคาถาที่แปลกประหลาดที่สุด! คำอธิบาย:
_{for i;{... การทำซ้ำโดยปริยายเหนืออาร์กิวเมนต์ทั้งหมด
$((i<0?[##2]2**32+i:[##2]i))... แปลงiเป็นรูปแบบ 32 บิตโดยใช้เคล็ดลับเสริมของสองถ้าi<0
${#${(M)${(s::) //expression// }#1}}... ขยายสตริงไปยังอาร์เรย์นับองค์ประกอบที่ (M) atch 1
((c>d))&&j=$i&&d=$c... ติดตามว่าอินพุตiใดเป็น "bittiest" ตามจำนวนc
<<<$j... ผลลัพธ์ผู้ชนะ}

Answer 29

J , 20 ไบต์

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

ตามที่เขียนไว้เมื่อกำหนดให้หลาย ๆ ตัวเท่า ๆ กันโดยจะส่งกลับค่าแรกในอาร์เรย์ หาก{.\:เปลี่ยนเป็นจะ{:/:ให้ค่าสุดท้าย ลองออนไลน์!

Answer 30

AArch64, 48 44 ไบต์

คำแนะนำดิบ (32 บิต endian hex):

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

การประกอบที่ไม่มีองค์ประกอบ:

        .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

คำอธิบาย

ลายเซ็นฟังก์ชัน C:

int32_t bittiest(int32_t *words, size_t len);

หลอก -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;
}

คำสั่งการนับประชากรของ AArch64 อยู่ใน NEON (ชุดคำสั่ง SIMD / ทศนิยม) และจะนับทีละไบต์ ดังนั้นการทำงานกับสเกลาร์ที่นี่จึงเป็นเรื่องน่าอึดอัดเล็กน้อยดังนั้นเราจึงทำทุกอย่างใน NEON

v4 คือจำนวนประชากรสูงสุด (v4, s4, h4 และ d4 ทั้งหมดอ้างถึงทะเบียนเดียวกัน) ตั้งค่าเป็น 0

        fmov    s4, #0

โหลดคำ int32 ถัดไปลงใน v0 และเพิ่มคำ (x0) ด้วย 4

        ldr     s0, [x0], #4

จัดเก็บจำนวนประชากรของแต่ละไบต์ใน v0 ลงในไบต์ที่สอดคล้องกันใน v1

        cnt     v1.8b, v0.8b

เพิ่มเลน 8 บิตทั้งหมดใน v1 เข้าด้วยกันเพื่อรับจำนวนประชากรทั้งหมดและจัดเก็บลงใน v1 อีกครั้ง

        uaddlv  h1, v1.8b

เปรียบเทียบจำนวนประชากรของคำนี้กับค่าสูงสุด ถ้ามีขนาดใหญ่กว่าหรือเท่ากัน v3 จะเป็น 1 บิตทั้งหมด (จริง) มิฉะนั้นจะเป็น 0 บิตทั้งหมด (เท็จ)

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

ถ้า v3 เป็นจริงให้ตั้งค่าคำสูงสุด (v2) เป็นคำปัจจุบัน max ไม่ได้เริ่มต้นในการทำซ้ำครั้งแรก แต่จะถูกตั้งค่าไว้เสมอเนื่องจากจำนวนประชากรจะเป็น> = 0 เสมอ

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

เหมือนกัน แต่สำหรับจำนวนประชากรสูงสุดใหม่

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

ลดความเลน (x1) และวนซ้ำถ้าไม่ใช่ศูนย์

        subs    x1, x1, #1
        bne     .Lloop

สิ้นสุดการวนซ้ำ: ย้ายค่าสูงสุดจากทะเบียน NEON ไปยังรีจิสเตอร์การส่งคืน (w0) และส่งคืน

        fmov    w0, s2
        ret

11 คำแนะนำ = 44 ไบต์