Finde die "Bittiest" Nummer [geschlossen]

Question

Die Herausforderung

Bei einer Liste von ganzen Zahlen ist die "kleinste" Zahl unter ihnen die mit den meisten Bits, dh die größte Anzahl von Bits, die auf 1 gesetzt sind.

Schreiben Sie eine Funktion (oder ein Programm), die eine Liste von 32-Bit-Ganzzahlen mit Vorzeichen als Eingabe verwendet und als Ausgabe die "kleinste" Zahl unter ihnen zurückgibt.

Sie können davon ausgehen, dass die Liste mindestens ein Element enthält.

Testfälle

Eingang: 1, 2, 3, 4

Ausgabe: 3

Eingang: 123, 64, 0, -4

Ausgabe: -4

Eingang: 7, 11

Ausgabe: Entweder 7oder 11(aber nicht beide)

Eingang: 1073741824, 1073741823

Ausgabe: 1073741823

Viel Glück

Dies ist Code Golf, also gewinnt das kürzeste Programm in Bytes.

Klärung

Wenn Ihre Sprache keine vorzeichenbehafteten 32-Bit-Ganzzahlen unterstützt, können Sie eine andere numerische Darstellung (gelesen: nicht in Textform) verwenden, solange alle Ganzzahlen von -2^31bis 2^31 - 1einschließlich dargestellt werden können, wobei für Negative das Zweierkomplement verwendet wird .

Answer 1

Gelee , 13 12 8 Bytes

%Ø%B§µÞṪ

Probieren Sie es online aus!

Erläuterung

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

Edit: danke euch allen für die freundliche Antwort auf meine erste Frage! Ich denke, ich habe es jetzt behoben, es scheint für alle Testfälle zu funktionieren.

Originalcode

2*31
B%¢S€iṀị

Answer 2

x86-Maschinensprache, 18 Byte

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

Die obigen Bytes definieren eine Funktion, die die Adresse des Arrays im esiRegister und die Anzahl der Elemente im Array im ecxRegister akzeptiert und die "kleinste" Nummer im Array im eaxRegister zurückgibt .

Beachten Sie, dass dies eine benutzerdefinierte Aufrufkonvention ist, die Argumente in den Registern ecxund akzeptiert esi, aber ansonsten einer C-Funktion ähnelt, die die Länge des Arrays und einen Zeiger auf das Array als ihre beiden Argumente verwendet. Diese benutzerdefinierte Aufrufkonvention behandelt alle Register als aufrufersicher, einschließlich ebx.

Die Implementierung dieser Funktion führt zu einigen schmutzigen Tricks, bei denen davon ausgegangen wird, dass das Array mindestens 1 Element enthält, wie in der Herausforderung vorgesehen. Es wird auch davon ausgegangen, dass das Richtungsflag ( DF) clear ( 0) ist, was in allen mir bekannten Aufrufkonventionen Standard ist.

In ungolfed Assembler-Mnemonik:

; 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

Das Hauptmerkmal dieses Codes ist natürlich der x86- popcntBefehl, der die Anzahl der gesetzten Bits in einer Ganzzahl zählt. Es durchläuft das Eingabearray und verfolgt sowohl den Wert des maximalen Elements als auch die Anzahl der darin enthaltenen gesetzten Bits. Es überprüft jeden Wert im Array, um festzustellen, ob die Anzahl der gesetzten Bits höher ist als der zuvor gesehene Wert. In diesem Fall werden die Tracking-Werte aktualisiert. Wenn nicht, wird dieser Schritt übersprungen.

Die popcntAnweisung ist eine große Anweisung (4 Byte), aber es kann nichts unternommen werden, um dies zu vermeiden. Der sehr kurze lodsBefehl (1 Byte) wurde jedoch verwendet, um Werte aus dem Array zu laden, während gleichzeitig der Zeiger inkrementiert wurde. Der kurze loopBefehl (2 Byte) wurde zur Schleifensteuerung verwendet (automatisches Dekrementieren des Elementzählers und Schleifen so lange) da noch mehr Elemente zu durchlaufen sind) und der sehr kurze (1-Byte-) xchgBefehl durchgehend verwendet wurde.

Am xchgEnde musste ein Extra verwendet werden, um die Verwendung des Befehls zu ermöglichen lods, der immer in das eaxRegister geladen wird, aber dieser Kompromiss ist mehr als wert.

Probieren Sie es online aus!

Mein erster Versuch war eine 20-Byte-Funktion. Bisher sind 18 Bytes das Beste, was ich mir vorstellen konnte. Ich bin gespannt, ob noch jemand diese Punktzahl schlagen kann!

Der einzige Weg zur Verbesserung, den ich sehe, wäre, wenn eine LOOPAAnweisung vorhanden wäre. Leider nicht - die einzigen unterstützten Bedingungscodes LOOPsind E/ Zund NE/ NZ. Aber vielleicht kann jemand anderes seinen Verstand weiter ausdehnen als ich!

Answer 3

JavaScript (ES6),  49 48 47  45 Byte

2 Bytes dank @ user81655 gespeichert

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

Probieren Sie es online aus!

Wie?

Wir haben .sort()die Eingabeliste mit einer rekursiven Funktion, die das gegebene niedrigstwertige Bit in jeder Variablen gibt pund qlöscht, bis eines von ihnen gleich 0 ist (oder beide gleichzeitig). Dies ermöglicht es, die Liste von den meisten bis zu den kleinsten gesetzten Bits zu ordnen. Wir geben dann den ersten Eintrag zurück, dh den "kleinsten".

Kommentiert

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 Bytes

Dank Adam und ngn wurden viele Bytes gespeichert.

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

Probieren Sie es online aus!

Answer 5

C (GCC) , ⁸⁰ 77 Bytes

3 Bytes dank att gespeichert !!!

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

Probieren Sie es online aus!

Answer 6

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

145-> 141 dank Benutzer
128-> 116 dank 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;}

Probieren Sie es online aus!

Answer 7

Kotlin , 41 38 29 Bytes

Richtiger Code mit viel weniger Bytes :) {Danke @vrintle}

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

Kotlin Spielplatz

---

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

Kotlin Spielplatz

---

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

Probieren Sie es online aus!

Answer 8

05AB1E , 9 Bytes

ΣžJ%b1¢}θ

Probieren Sie es online aus!

Σž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 Bytes

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

Probieren Sie es online aus!

-2 danke an Robin Ryder

-1 dank Dominic van Essen.

Answer 10

Stax , 18 Bytes

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

Führen Sie es aus und debuggen Sie es

Pads manuell mit 1s / 0s, um die richtige Darstellung zu erhalten.

Zeigt für jeden Testfall eine einzelne Nummer an.

Answer 11

K (ngn / k) , 11 Bytes

{*x@>+/2\x}

Probieren Sie es online aus!

Answer 12

Python 3 , 52 Bytes

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

Probieren Sie es online aus!

n%2**31- Da in Python ganze Zahlen unendlich sind, müssen negative Zahlen geändert werden. zum Beispiel -4wird2147483644

bin(...) - ins Binärformat übersetzen

count("1") - Zählen Sie die Anzahl der Einheiten

---

Python 3 , 50 Bytes

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

Probieren Sie es online aus!

zwei Bytes kürzer, funktioniert aber nicht mit negativen Zahlen

Answer 13

Scala , 54 42 40 36 Bytes

Dank Caird Coinheringaahing, Didymus, User und einigen Tipps wurden einige Bytes gespeichert

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

Probieren Sie es online aus!

Answer 14

Schale , 17 16 13 Bytes

Bearbeiten: -1 Byte dank Razetime und dann -3 Byte dank Leo

►(ΣḋΩ≥0+^32 2

Probieren Sie es online aus!

Husk verwendet nativ Ganzzahlen mit beliebiger Genauigkeit und hat daher keine Vorstellung vom 32-Bit-2-Komplement zur Darstellung negativer 4-Byte-Ganzzahlen mit Vorzeichen: Daher ist die Funktion "Binärziffern abrufen" - ḋ- hier für negative Eingaben leider unbrauchbar.
Wir müssen also die '2's Complement Bittiness' von Hand berechnen.

Vielen Dank an Husk Hilfe von Leo für die Verwendung Ωhier.

►                       # 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 Bytes

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

Probieren Sie es online aus.

Erläuterung:

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

Gelee , 9 8 Bytes

%Ø%BSƲÞṪ

Probieren Sie es online aus!

-1 Byte durch Verwendung von Þ(sortieren) anstelle von ÐṀ(maximal). Dies wurde von Gio Ds Antwort inspiriert und nach ihrer und meiner Bearbeitung sind beide Lösungen ziemlich gleich.

Erläuterung

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

Answer 17

Japt -h , 10 Bytes

ñÈu2pH)¤¬x

Versuch es

ñÈ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 Bytes

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

Probieren Sie es online aus!

Answer 19

Ruby 2.7 , 36 33 34 Bytes

Vielen Dank an Dingus für die Korrektur meines Codes für einen Sonderfall! :) :)

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

Probieren Sie es online aus!

Verwendet Befehlszeilenargumente für die Eingabe und gibt die kleinste Zahl als Zeichenfolge aus. TIO verwendet eine ältere Version von Ruby, während wir in Ruby 2.7 Parameter nummeriert haben, wodurch zwei Bytes gespart werden.

Answer 20

Java (JDK) , 44 Byte

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

Probieren Sie es online aus!

Dies ist eine Art Betrug, da es a Stream<Integer>als Eingabe akzeptiert und ein zurückgibt Optional<Int>.

Answer 21

Scala , 24 Bytes

_ maxBy Integer.bitCount

Probieren Sie es online aus!

Spaltung von Gabbers großartiger erster Antwort .

Answer 22

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

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

Probieren Sie es online aus!

• Überarbeitet, um ein Lambda zu verwenden, wie von @user in Kommentaren vorgeschlagen

Answer 23

Holzkohle , 22 Bytes

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

Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Erläuterung:

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

Wandeln Sie für jede Zahl in der Liste eine vorzeichenlose 32-Bit-Zahl um, konvertieren Sie sie in eine Binärzahl und summieren Sie die Bits.

Ｉ§θ⌕η⌈η

Geben Sie die Nummer an der Position der höchsten Bitanzahl aus.

Answer 24

SystemVerilog, 66 Bytes

Dies ist vorerst eine unvollständige Antwort, da ich von meinem Telefon aus poste, aber die $countones()Funktion von SV ist hier perfekt.

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

Answer 25

Wolfram Language (Mathematica) , 39 Bytes

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

Probieren Sie es online aus!

Answer 26

PowerShell, 53 56 Byte

+5 Bytes, weil Negative
dank mazzy nicht richtig behandelt wurden -2 Bytes

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

Answer 27

Nim , 75 Bytes

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

Probieren Sie es online aus!

Answer 28

Zsh, 85 Bytes

Probieren Sie es online aus!

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

Große Herausforderung, erforderte einige der seltsamsten ZshBeschwörungsformeln! Erläuterung:
_{for i;{... implizite Iteration über alle Argumente
$((i<0?[##2]2**32+i:[##2]i))... Konvertieren iin das 32-Bit-Format unter Verwendung des Zweierkomplementtricks, wenn i<0
${#${(M)${(s::) //expression// }#1}}... Zeichenfolge zu Array erweitern, Elemente zählen, die (M) atch 1
((c>d))&&j=$i&&d=$c... verfolgen, welche Eingabe die iist "bittiest" nach der Zählung c
<<<$j... geben Sie den Gewinner aus}

Answer 29

J , 20 Bytes

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

Wie geschrieben, gibt bei Angabe mehrerer gleicher, maximal kleiner Zahlen die erste im Array zurück. Wenn {.\:geändert wird {:/:, gibt es das letzte. Probieren Sie es online aus!

Answer 30

AArch64, 48 44 Bytes

Rohe Anweisungen (32-Bit-Little-Endian-Hex):

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

Nicht kommentierte Montage:

        .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

Erläuterung

C-Funktionssignatur:

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;
}

Der Populationszählbefehl von AArch64 befindet sich in NEON (dem SIMD / Gleitkomma-Befehlssatz) und zählt jedes Byte einzeln. Daher ist es etwas umständlich, hier mit Skalaren zu arbeiten, damit wir alles in NEON erledigen.

v4 ist die maximale Bevölkerungszahl (v4, s4, h4 und d4 beziehen sich alle auf dasselbe Register). Setzen Sie es auf 0.

        fmov    s4, #0

Laden Sie das nächste int32-Wort in v0 und erhöhen Sie die Wörter (x0) um 4.

        ldr     s0, [x0], #4

Speichern Sie die Populationszahl jedes Bytes in v0 in dem entsprechenden Byte in v1.

        cnt     v1.8b, v0.8b

Addieren Sie alle 8-Bit-Lanes in Version 1, um die vollständige Bevölkerungszahl zu erhalten, und speichern Sie sie erneut in Version 1.

        uaddlv  h1, v1.8b

Vergleichen Sie die Bevölkerungszahl dieses Wortes mit dem Maximum. Wenn es größer oder gleich ist, ist v3 alle 1 Bits (wahr), andernfalls sind es alle 0 Bits (falsch).

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

Wenn v3 wahr ist, setzen Sie das maximale Wort (v2) auf das aktuelle Wort. max wird bei der ersten Iteration nicht initialisiert, wird jedoch immer festgelegt, da die Anzahl der Populationen immer> = 0 ist.

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

Gleich, aber für die neue maximale Bevölkerungszahl.

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

Dekrementiere len (x1) und schleife, wenn es nicht Null ist

        subs    x1, x1, #1
        bne     .Lloop

Ende der Schleife: Verschieben Sie den Maximalwert von einem NEON-Register in das Rückgaberegister (w0) und kehren Sie zurück.

        fmov    w0, s2
        ret

11 Anweisungen = 44 Bytes