Znajdź „najbardziej gorzką” liczbę [zamknięte]

Dec 20 2020

Wyzwanie

Biorąc pod uwagę listę liczb całkowitych, „najbardziej bitowa” liczba spośród nich to ta z największą liczbą bitów - to znaczy największą liczbą bitów ustawioną na 1.

Napisz funkcję (lub program), która pobiera jako dane wejściowe listę 32-bitowych liczb całkowitych ze znakiem i zwraca na wyjściu „najbardziej bitową” liczbę spośród nich.

Możesz założyć, że lista zawiera co najmniej jedną pozycję.

Przypadki testowe

Wejście: 1, 2, 3, 4

Wynik: 3

Wejście: 123, 64, 0, -4

Wynik: -4

Wejście: 7, 11

Dane wyjściowe: albo 7albo 11(ale nie oba)

Wejście: 1073741824, 1073741823

Wynik: 1073741823

Powodzenia

To jest kod golfowy, więc wygrywa najkrótszy program w bajtach.

Wyjaśnienie

Jeśli twój język nie obsługuje 32-bitowych liczb całkowitych ze znakiem, możesz użyć dowolnej innej reprezentacji numerycznej (czytaj: nie tekstowej), o ile może ona reprezentować wszystkie liczby całkowite od -2^31do 2^31 - 1włącznie, używając dopełnienia do dwóch dla liczb ujemnych.

Odpowiedzi

10 GioD Dec 21 2020 at 13:54

Galaretka , 13 12 8 bajtów

%Ø%B§µÞṪ

Wypróbuj online!

Wyjaśnienie

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

Edycja: dziękuję wszystkim za miłą odpowiedź na moje pierwsze pytanie! Myślę, że naprawiłem to teraz, wydaje się, że działa we wszystkich przypadkach testowych.

Oryginalny kod

2*31
B%¢S€iṀị
26 CodyGray Dec 20 2020 at 18:26

Język maszynowy x86, 18 bajtów

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

Powyższe bajty definiują funkcję, która akceptuje adres tablicy w esirejestrze oraz liczbę elementów tablicy w ecxrejestrze i zwraca „najbardziej bitową” liczbę w tablicy w eaxrejestrze.

Zauważ, że jest to niestandardowa konwencja wywoływania, która akceptuje argumenty w rejestrach ecxi esi, ale poza tym jest bardzo podobna do funkcji C, która przyjmuje długość tablicy i wskaźnik do tablicy jako jej dwa argumenty. Ta niestandardowa konwencja wywoływania traktuje wszystkie rejestry jako zapisywanie rozmówców, w tym ebx.

Realizacja tej funkcji pociąga za sobą kilka brudnych sztuczek, które zakładają, że tablica ma co najmniej 1 element, jak przewidziano w wyzwaniu. Zakłada również, że flaga kierunku ( DF) jest clear ( 0), co jest standardem we wszystkich znanych mi konwencjach wywoływania.

W ungolfed mnemonikach języka asemblera:

; 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

Kluczową cechą tego kodu jest oczywiście popcntinstrukcja x86 , która zlicza liczbę ustawionych bitów w liczbie całkowitej. Iteruje po tablicy wejściowej, śledząc zarówno wartość maksymalnego elementu, jak i liczbę zawartych w nim ustawionych bitów. Sprawdza każdą wartość w tablicy, aby zobaczyć, czy jej liczba ustawionych bitów jest większa niż jakakolwiek wartość, którą widział wcześniej. Jeśli tak, aktualizuje wartości śledzenia; jeśli nie, pomija ten krok.

popcntInstrukcja jest duży (4 bajty) pouczenie, ale nie ma nic, co można zrobić, aby tego uniknąć. Jednak bardzo krótka (1-bajtowa) lodsinstrukcja została użyta do załadowania wartości z tablicy przy jednoczesnym zwiększaniu wskaźnika, krótka (2-bajtowa) loopinstrukcja została wykorzystana do sterowania pętlą (automatyczne zmniejszanie licznika elementów i zapętlanie tak długo) ponieważ pozostało więcej elementów do przejścia), a bardzo krótka (1-bajtowa) xchginstrukcja została wykorzystana w całym dokumencie.

Na xchgkońcu należało użyć dodatku , aby umożliwić korzystanie z lodsinstrukcji, która zawsze ładuje się do eaxrejestru, ale ten kompromis jest tego więcej niż wart.

Wypróbuj online!

Moją pierwszą próbą była funkcja 20-bajtowa. Jak dotąd 18 bajtów to najlepsze, co udało mi się wymyślić. Jestem ciekawy, czy ktoś inny może pokonać ten wynik!

Jedyna droga do poprawy, jaką widzę, to gdyby LOOPAistniała instrukcja. Niestety tak nie jest - jedynymi obsługiwanymi kodami warunków LOOPE/ Zi NE/ NZ. Ale może ktoś inny może rozciągnąć swój umysł bardziej niż ja!

18 Arnauld Dec 20 2020 at 03:58

JavaScript (ES6),  49 48 47  45 bajtów

Zapisano 2 bajty dzięki @ user81655

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

Wypróbuj online!

W jaki sposób?

Mamy .sort()listę wejściową z funkcją rekurencyjną, która, podana pi q, czyści najmniej znaczący bit ustawiony w każdej zmiennej, aż jeden z nich będzie równy 0 (lub oba jednocześnie). Pozwala to uporządkować listę od największej do najmniejszej liczby bitów. Następnie zwracamy pierwszy wpis, czyli ten „najbardziej gorzki”.

Skomentowano

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
9 KamilaSzewczyk Dec 20 2020 at 03:45

APL (Dyalog Unicode) , 15 bajtów

Zaoszczędzono wiele bajtów dzięki Adamowi i ngn.

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

Wypróbuj online!

8 Noodle9 Dec 20 2020 at 09:07

C (gcc) , 80 77 bajtów

Zapisano 3 bajty dzięki att !!!

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

Wypróbuj online!

7 Zaiborg Dec 21 2020 at 22:41

C ++ (GCC) , 145 141 140 135 134 133 130 128 116 bajtów

145-> 141 dzięki użytkownikowi
128-> 116 dzięki sufitowicat

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

Wypróbuj online!

6 pavi2410 Dec 21 2020 at 23:13

Kotlin , 41 38 29 bajtów

Poprawny kod z dużo mniejszą liczbą bajtów :) {Dzięki @vrintle}

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

Plac zabaw Kotlin


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

Plac zabaw Kotlin


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

Wypróbuj online!

6 Makonede Dec 21 2020 at 01:44

05AB1E , 9 bajtów

ΣžJ%b1¢}θ

Wypróbuj 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
4 Giuseppe Dec 20 2020 at 05:32

R , 58 55 54 bajty

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

Wypróbuj online!

-2 dzięki Robin Ryder

-1 dzięki Dominicowi van Essenowi.

4 Razetime Dec 20 2020 at 10:30

Stax , 18 bajtów

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

Uruchom i debuguj

Ręcznie wypełnia 1s / 0s, aby uzyskać poprawną reprezentację.

Wyświetla jeden numer dla każdego przypadku testowego.

4 GalenIvanov Dec 21 2020 at 15:02

K (ngn / k) , 11 bajtów

{*x@>+/2\x}

Wypróbuj online!

4 Danis Dec 20 2020 at 19:02

Python 3 , 52 bajty

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

Wypróbuj online!

n%2**31- ponieważ w Pythonie liczby całkowite są nieskończone, należy zmienić liczby ujemne. na przykład -4staje się2147483644

bin(...) - przetłumacz na format binarny

count("1") - policz liczbę jednostek


Python 3 , 50 bajtów

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

Wypróbuj online!

dwa bajty krótsze, ale nie działa z liczbami ujemnymi

4 Gabber Dec 22 2020 at 00:56

Scala , 54 42 40 36 bajtów

Zapisano trochę bajtów dzięki caird coinheringaahing, didymus, user i kilku wskazówkom

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

Wypróbuj online!

3 DominicvanEssen Dec 20 2020 at 15:17

Husk , 17 16 13 bajtów

Edycja: -1 bajt dzięki Razetime, a następnie -3 bajty dzięki Leo

►(ΣḋΩ≥0+^32 2

Wypróbuj online!

Husk natywnie używa liczb całkowitych o dowolnej precyzji, więc nie ma pojęcia uzupełnienia 32-bitowego 2 do reprezentowania ujemnych 4-bajtowych liczb całkowitych ze znakiem: w rezultacie funkcja „pobierz cyfry binarne” - - jest tutaj niestety bezużyteczna dla ujemnych danych wejściowych.
Musimy więc ręcznie obliczyć „dopełnienie dwójki”.

Dzięki pomocy Huska od Leo za korzystanie z Ωtego miejsca.

►                       # 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
3 KevinCruijssen Dec 21 2020 at 22:13

Java 10, 73 bajty

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

Wypróbuj online.

Wyjaśnienie:

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
3 xigoi Dec 21 2020 at 20:53

Galaretka , 9 8 bajtów

%Ø%BSƲÞṪ

Wypróbuj online!

-1 bajt przy użyciu Þ(sort) zamiast ÐṀ(maximum). Zostało to zainspirowane odpowiedzią Gio D i po ich i moim redagowaniu oba rozwiązania są prawie takie same.

Wyjaśnienie

%Ø%BSƲÞṪ   Main monadic link
      Þ    Sort by
     Ʋ     (
%            Modulo
 Ø%            2^32
   B         Binary
    S        Sum
     Ʋ     )
       Ṫ   Last item
3 Shaggy Dec 21 2020 at 17:11

Japt -h , 10 bajtów

ñÈu2pH)¤¬x

Spróbuj

ñÈ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
2 Xcali Dec 20 2020 at 06:47

Perl 5 , 54 bajty

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

Wypróbuj online!

2 vrintle Dec 20 2020 at 10:55

Ruby 2.7 , 36 33 34 bajty

Dziękuję Dingusowi za poprawienie mojego kodu w specjalnym przypadku! :)

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

Wypróbuj online!

Używa argumentów wiersza polecenia jako danych wejściowych, wyświetla najbardziej bitową liczbę jako ciąg. TIO używa starszej wersji Rubiego, podczas gdy w Rubim 2.7 mamy ponumerowane parametry, co pozwala zaoszczędzić dwa bajty.

2 user Dec 21 2020 at 22:25

Java (JDK) , 44 bajty

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

Wypróbuj online!

Jest to rodzaj oszustwa, ponieważ przyjmuje a Stream<Integer>jako dane wejściowe i zwraca Optional<Int>.

2 user Dec 22 2020 at 04:21

Scala , 24 bajty

_ maxBy Integer.bitCount

Wypróbuj online!

Oderwane od wspaniałej pierwszej odpowiedzi Gabbera .

2 didymus Dec 22 2020 at 03:29

C # (interaktywny kompilator Visual C #) , 71 58 bajtów

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

Wypróbuj online!

  • Refaktoryzowano, aby używać lambdy zgodnie z sugestią @user w komentarzach
1 Neil Dec 20 2020 at 04:34

Węgiel , 22 bajty

≔EθΣ⍘﹪ιX²¦³²¦²ηI§θ⌕η⌈η

Wypróbuj online! Link prowadzi do pełnej wersji kodu. Wyjaśnienie:

≔EθΣ⍘﹪ιX²¦³²¦²η

Dla każdej liczby z listy przerzuć ją na 32-bitową liczbę bez znaku, przekonwertuj ją na liczbę binarną i zsumuj bity.

I§θ⌕η⌈η

Podaj liczbę na pozycji największej liczby bitów.

1 ChrisLoonam Dec 20 2020 at 13:14

SystemVerilog, 66 bajtów

Na razie będzie to niedoskonała odpowiedź, ponieważ piszę z telefonu, ale $countones()funkcja SV jest tutaj idealna.

function m(int q[$]);
m=q.max with ($countones(item));
endfunction
1 att Dec 21 2020 at 04:29

Język Wolfram (Mathematica) , 39 bajtów

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

Wypróbuj online!

1 ZaelinGoodman Dec 21 2020 at 03:32

PowerShell, 53 56 bajtów

+5 bajtów, ponieważ nie obsługiwał poprawnie negatywów
-2 bajty dzięki mazzy

$args|sort{$v=$_;0..31|%{$o+=!!(1-shl$_-band$v)};$o}-b 1
1 xigoi Dec 21 2020 at 21:20

Nim , 75 bajtów

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

Wypróbuj online!

1 roblogic Dec 22 2020 at 05:17

Zsh, 85 bajtów

wypróbuj online!

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

Wielkie wyzwanie wymagało kilku najdziwniejszych Zshzaklęć! Objaśnienie:
for i;{... niejawna iteracja wszystkich argumentów
$((i<0?[##2]2**32+i:[##2]i))... konwersja ido formatu 32-bitowego, przy użyciu sztuczki uzupełniającej do dwóch, jeśli i<0
${#${(M)${(s::) //expression// }#1}}... rozszerza ciąg do tablicy, liczy elementy, które (M) atch 1
((c>d))&&j=$i&&d=$c... śledzi, które wejście ijest „najbardziej gorzki” według liczby c
<<<$j... wygraj zwycięzcę

1 wroth Dec 22 2020 at 08:54

J , 20 bajtów

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

Jak napisano, gdy podano wiele równych, maksymalnie bitowych liczb, zwraca pierwszą z tablicy. Jeśli {.\:zostanie zmienione na {:/:, daje ostatnie. Wypróbuj online!

1 EasyasPi Dec 23 2020 at 12:09

AArch64, 48 44 bajty

Nieprzetworzone instrukcje (32-bitowe little endian hex):

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

Niekomentowany montaż:

        .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

Wyjaśnienie

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

Instrukcja liczenia populacji AArch64 jest w NEON (zestaw instrukcji SIMD / zmiennoprzecinkowych) i zlicza każdy bajt indywidualnie. Dlatego praca ze skalarami jest tutaj trochę niewygodna, więc wszystko robimy w NEON.

v4 to maksymalna liczba ludności (v4, s4, h4 i d4 wszystkie odnoszą się do tego samego rejestru). Ustaw na 0.

        fmov    s4, #0

Załaduj następne słowo int32 do v0 i zwiększ liczbę słów (x0) o 4.

        ldr     s0, [x0], #4

Przechowuj liczbę ludności każdego bajtu w v0 do odpowiedniego bajtu w v1.

        cnt     v1.8b, v0.8b

Dodaj wszystkie 8-bitowe pasy w wersji 1, aby uzyskać pełną liczbę ludności, i ponownie zapisz w wersji 1.

        uaddlv  h1, v1.8b

Porównaj liczbę populacji tego słowa z maksymalną. Jeśli jest większa lub równa, wersja v3 będzie miała wszystkie 1 bity (prawda), w przeciwnym razie wszystkie będą miały wartość 0 bitów (fałsz).

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

Jeśli v3 to prawda, ustaw słowo max (v2) na słowo bieżące. max nie jest inicjowany w pierwszej iteracji, ale zawsze będzie ustawiony, ponieważ liczba populacji będzie zawsze> = 0.

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

To samo, ale dla nowej maksymalnej liczby ludności.

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

Zmniejsz len (x1) i zapętlaj, jeśli nie jest równe zero

        subs    x1, x1, #1
        bne     .Lloop

Koniec pętli: Przenieś maksymalną wartość z rejestru NEON do rejestru powrotu (w0) i wróć.

        fmov    w0, s2
        ret

11 instrukcji = 44 bajty