Trouvez le numéro le plus «bittest» [fermé]

Question

Le défi

Étant donné une liste d'entiers, le nombre le plus «bittest» parmi eux est celui avec le plus de bits, c'est-à-dire le plus grand nombre de bits mis à 1.

Ecrivez une fonction (ou un programme) qui prend en entrée une liste d'entiers signés 32 bits et renvoie en sortie le nombre le plus "bittest" parmi eux.

Vous pouvez supposer que la liste contient au moins un élément.

Cas de test

Contribution: 1, 2, 3, 4

Production: 3

Contribution: 123, 64, 0, -4

Production: -4

Contribution: 7, 11

Sortie: l'un 7ou l' autre ou 11(mais pas les deux)

Contribution: 1073741824, 1073741823

Production: 1073741823

Bonne chance

Il s'agit de code golf, donc le programme le plus court en octets l'emporte.

Clarification

Si votre langage ne prend pas en charge les entiers signés 32 bits, vous pouvez utiliser toute autre représentation numérique (lue: non textuelle) tant qu'elle peut représenter tous les entiers de -2^31à 2^31 - 1inclus, en utilisant le complément à deux pour les négatifs.

Answer 1

Gelée , 13 12 8 octets

%Ø%B§µÞṪ

Essayez-le en ligne!

Explication

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

Edit: merci à tous pour l'aimable réponse à ma première question! Je pense que je l'ai corrigé maintenant, cela semble fonctionner pour tous les cas de test.

Code d'origine

2*31
B%¢S€iṀị

Answer 2

Langage machine x86, 18 octets

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

Les octets ci-dessus définissent une fonction qui accepte l'adresse du tableau dans le esiregistre et le nombre d'éléments du tableau dans le ecxregistre, et renvoie le nombre le plus "bitumineux" du tableau dans le eaxregistre.

Notez qu'il s'agit d'une convention d'appel personnalisée qui accepte les arguments dans les registres ecxet esi, mais cela ressemble beaucoup à une fonction C qui prend la longueur du tableau et un pointeur vers le tableau comme ses deux arguments. Cette convention d'appel personnalisée traite tous les registres comme une sauvegarde de l'appelant, y compris ebx.

L'implémentation de cette fonction tire quelques sales tours, qui supposent que le tableau a au moins 1 élément, comme prévu dans le défi. Il suppose également que l'indicateur de direction ( DF) est clear ( 0), ce qui est standard dans toutes les conventions d'appel que je connais.

Dans les mnémoniques du langage d'assemblage non golfées:

; 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

La caractéristique clé de ce code est, bien sûr, l' popcntinstruction x86 , qui compte le nombre de bits définis dans un entier. Il parcourt le tableau d'entrée, en gardant une trace de la valeur de l'élément maximum et du nombre de bits définis qu'il contient. Il vérifie chaque valeur du tableau pour voir si son nombre de bits définis est supérieur à toute valeur qu'il a vue auparavant. Si tel est le cas, il met à jour les valeurs de suivi; sinon, il saute cette étape.

L' popcntinstruction est une instruction volumineuse (4 octets), mais rien ne peut être fait pour éviter cela. Cependant, l' lodsinstruction très courte (1 octet) a été utilisée pour charger les valeurs du tableau tout en incrémentant simultanément le pointeur, l' loopinstruction courte (2 octets) a été utilisée pour le contrôle de boucle (décrémentant automatiquement le compteur d'élément et bouclant aussi longtemps car il reste plus d'éléments à parcourir), et l' xchginstruction très courte (1 octet) a été utilisée partout.

Un supplément xchga dû être utilisé à la fin pour permettre l'utilisation de l' lodsinstruction, qui se charge toujours dans le eaxregistre, mais ce compromis en vaut la peine.

Essayez-le en ligne!

Ma première tentative était une fonction de 20 octets. Jusqu'à présent, 18 octets est le meilleur que j'ai pu trouver. Je suis curieux de voir si quelqu'un d'autre peut battre ce score!

La seule voie d'amélioration que je vois serait si une LOOPAinstruction existait. Malheureusement, ce n'est pas le cas - les seuls codes de condition pris en charge par LOOPsont E/ Zet NE/ NZ. Mais peut-être que quelqu'un d'autre peut étirer son esprit plus loin que moi!

Answer 3

JavaScript (ES6),  49 48 47  45 octets

Sauvegardé 2 octets grâce à @ user81655

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

Essayez-le en ligne!

Comment?

Nous avons .sort()la liste d'entrée avec une fonction récursive qui, étant donné pet q, efface le bit le moins significatif défini dans chaque variable jusqu'à ce que l'un d'eux soit égal à 0 (ou les deux simultanément). Cela permet d'ordonner la liste du plus au moins ensemble de bits. Nous retournons ensuite la première entrée, c'est-à-dire la plus "bittest".

Commenté

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 octets

Sauvegardé de nombreux octets grâce à Adam et ngn.

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

Essayez-le en ligne!

Answer 5

C (gcc) , ⁸⁰ 77 octets

Sauvegardé 3 octets grâce à att !!!

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

Essayez-le en ligne!

Answer 6

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

145-> 141 grâce à l'utilisateur
128-> 116 grâce au plafonnier

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

Essayez-le en ligne!

Answer 7

Kotlin , 41 38 29 octets

Code correct avec beaucoup moins d'octets :) {Merci @vrintle}

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

Aire de jeux Kotlin

---

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

Aire de jeux Kotlin

---

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

Essayez-le en ligne!

Answer 8

05AB1E , 9 octets

ΣžJ%b1¢}θ

Essayez-le en ligne!

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

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

Essayez-le en ligne!

-2 merci à Robin Ryder

-1 merci à Dominic van Essen.

Answer 10

Stax , 18 octets

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

Exécutez et déboguez-le

Remplit manuellement avec 1s / 0s pour obtenir la représentation correcte.

Affiche un numéro unique pour chaque cas de test.

Answer 11

K (ngn / k) , 11 octets

{*x@>+/2\x}

Essayez-le en ligne!

Answer 12

Python 3 , 52 octets

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

Essayez-le en ligne!

n%2**31- comme en python les entiers sont infinis, doivent changer les nombres négatifs. par exemple -4devient2147483644

bin(...) - traduire au format binaire

count("1") - compter le nombre d'unités

---

Python 3 , 50 octets

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

Essayez-le en ligne!

deux octets plus courts, mais ne fonctionne pas avec des nombres négatifs

Answer 13

Scala , 54 42 40 36 octets

Sauvegardé quelques octets grâce à caird coinheringaahing, didymus, user et quelques astuces

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

Essayez-le en ligne!

Answer 14

Husk , 17 16 13 octets

Edit: -1 octet grâce à Razetime, puis -3 octets grâce à Leo

►(ΣḋΩ≥0+^32 2

Essayez-le en ligne!

Husk utilise nativement des entiers de précision arbitraire, et n'a donc aucune notion de complément de 32 bits 2 pour représenter des entiers signés négatifs de 4 octets: en conséquence, la fonction 'get binary digits' - ḋ- est malheureusement inutile ici pour les entrées négatives.
Nous devons donc calculer à la main la «bittiness du complément à 2».

Merci à l' aide de Husk de Leo pour l'utilisation d' Ωici.

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

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

Essayez-le en ligne.

Explication:

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

Gelée , 9 8 octets

%Ø%BSƲÞṪ

Essayez-le en ligne!

-1 octet en utilisant Þ(tri) au lieu de ÐṀ(maximum). Cela a été inspiré par la réponse de Gio D et après leur et ma modification, les deux solutions sont à peu près les mêmes.

Explication

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

Answer 17

Japt -h , 10 octets

ñÈu2pH)¤¬x

Essayez-le

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

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

Essayez-le en ligne!

Answer 19

Ruby 2.7 , 36 33 34 octets

Merci à Dingus d' avoir corrigé mon code pour un cas particulier! :)

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

Essayez-le en ligne!

Utilise des arguments de ligne de commande pour l'entrée, génère le nombre le plus bête sous forme de chaîne. TIO utilise une ancienne version de Ruby, alors que dans Ruby 2.7, nous avons numéroté des paramètres, ce qui économise deux octets.

Answer 20

Java (JDK) , 44 octets

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

Essayez-le en ligne!

C'est une sorte de triche, car il accepte un Stream<Integer>comme entrée et renvoie un Optional<Int>.

Answer 21

Scala , 24 octets

_ maxBy Integer.bitCount

Essayez-le en ligne!

Séparez-vous de la grande première réponse de Gabber .

Answer 22

C # (compilateur interactif Visual C #) , 71 58 octets

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

Essayez-le en ligne!

• Refactorisé pour utiliser un lambda comme suggéré par @user dans les commentaires

Answer 23

Charbon , 22 octets

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

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication:

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

Pour chaque nombre de la liste, transtypez-le en un nombre non signé de 32 bits, convertissez-le en binaire et additionnez les bits.

Ｉ§θ⌕η⌈η

Sortez le nombre à la position du nombre de bits le plus élevé.

Answer 24

SystemVerilog, 66 octets

Ce sera une réponse imparfaite pour le moment car je poste depuis mon téléphone, mais la $countones()fonction de SV est parfaite ici.

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

Answer 25

Wolfram Language (Mathematica) , 39 octets

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

Essayez-le en ligne!

Answer 26

PowerShell, 53 56 octets

+5 octets car il ne traitait pas correctement les négatifs
-2 octets grâce à mazzy

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

Answer 27

Nim , 75 octets

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

Essayez-le en ligne!

Answer 28

Zsh, 85 octets

essayez-le en ligne!

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

Grand défi, a nécessité certaines des Zshincantations les plus étranges ! Explication:
_{for i;{... itération implicite sur tous les arguments
$((i<0?[##2]2**32+i:[##2]i))... convertir iau format 32 bits, en utilisant l'astuce du complément à deux si i<0
${#${(M)${(s::) //expression// }#1}}... développer la chaîne en tableau, compter les éléments qui (M) atch 1
((c>d))&&j=$i&&d=$c... garder une trace de quelle entrée iest le "bittiest" selon le décompte c
<<<$j... sortie le gagnant}

Answer 29

J , 20 octets

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

Tel qu'écrit, lorsqu'il est donné plusieurs nombres de manière égale et maximale, renvoie le premier du tableau. Si {.\:est changé en {:/:, il donne le dernier. Essayez-le en ligne!

Answer 30

AArch64, 48 44 octets

Instructions brutes (hexadécimal petit-boutiste 32 bits):

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

Assemblage non commenté:

        .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

Explication

Signature de la fonction 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;
}

L'instruction de comptage de population de AArch64 est en NEON (le jeu d'instructions SIMD / virgule flottante), et elle compte chaque octet individuellement. Par conséquent, il est un peu gênant de travailler avec des scalaires ici, donc nous faisons tout dans NEON.

v4 est le nombre maximum de population (v4, s4, h4 et d4 font tous référence au même registre). Réglez-le sur 0.

        fmov    s4, #0

Chargez le mot int32 suivant dans v0 et incrémentez les mots (x0) de 4.

        ldr     s0, [x0], #4

Stockez le nombre de population de chaque octet de la v0 dans l'octet correspondant de la v1.

        cnt     v1.8b, v0.8b

Ajoutez toutes les voies 8 bits de la v1 ensemble pour obtenir le décompte complet de la population et stockez-les à nouveau dans la v1.

        uaddlv  h1, v1.8b

Comparez la population de ce mot au maximum. S'il est plus grand ou égal, v3 sera tous les 1 bits (vrai), sinon ce sera tous les 0 bits (faux).

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

Si v3 est vrai, définissez le mot max (v2) sur le mot actuel. max n'est pas initialisé à la première itération, mais il sera toujours défini car le nombre de population sera toujours> = 0.

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

Idem, mais pour le nouveau nombre maximum de population.

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

Décrémenter len (x1), et boucler s'il n'est pas nul

        subs    x1, x1, #1
        bne     .Lloop

Fin de boucle: déplacez la valeur maximale d'un registre NEON vers le registre de retour (w0) et retournez.

        fmov    w0, s2
        ret

11 instructions = 44 octets