Encontre o número “Bittiest” [fechado]

Dec 20 2020

O desafio

Dada uma lista de inteiros, o número "mais bit" entre eles é aquele com a maioria dos bits ativados - ou seja, a maior quantidade de bits definida como 1.

Escreva uma função (ou um programa) que recebe como entrada uma lista de inteiros com sinal de 32 bits e retorna como saída o número mais "bittiest" entre eles.

Você pode presumir que a lista tem pelo menos um item.

Casos de teste

Entrada: 1, 2, 3, 4

Resultado: 3

Entrada: 123, 64, 0, -4

Resultado: -4

Entrada: 7, 11

Resultado: um 7ou 11(mas não ambos)

Entrada: 1073741824, 1073741823

Resultado: 1073741823

Boa sorte

Este é o código de golfe, então o programa mais curto em bytes vence.

Esclarecimento

Se o seu idioma não suportar inteiros com sinal de 32 bits, você pode usar qualquer outra representação numérica (leia-se: não textual), desde que possa representar todos os inteiros de -2^31a 2^31 - 1inclusive, usando complemento de dois para negativos.

Respostas

10 GioD Dec 21 2020 at 13:54

Jelly , 13 12 8 bytes

%Ø%B§µÞṪ

Experimente online!

Explicação

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

Edit: obrigado a todos pela amável resposta à minha primeira pergunta! Acho que consertei agora, parece funcionar para todos os casos de teste.

Código original

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

Linguagem de máquina x86, 18 bytes

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

Os bytes acima definem uma função que aceita o endereço da matriz no esiregistro e o número de elementos na matriz no ecxregistro, e retorna o número mais "bittiest" na matriz no eaxregistro.

Observe que esta é uma convenção de chamada personalizada que aceita argumentos nos registradores ecxe esi, mas é muito parecida com uma função C que leva o comprimento da matriz e um ponteiro para a matriz como seus dois argumentos. Esta convenção de chamada personalizada trata todos os registros como salvos pelo chamador, inclusive ebx.

A implementação desta função puxa alguns truques sujos, que assumem que o array tem pelo menos 1 elemento, conforme previsto no desafio. Ele também assume que o sinalizador de direção ( DF) é claro ( 0), que é padrão em todas as convenções de chamada que conheço.

Em mnemônicos de linguagem assembly não-golfados:

; 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

A principal característica desse código é, obviamente, a popcntinstrução x86 , que conta o número de bits definidos em um inteiro. Ele itera por meio da matriz de entrada, acompanhando o valor do elemento máximo e o número de bits definidos que ele contém. Ele verifica cada valor na matriz para ver se seu número de bits definidos é maior do que qualquer valor que ele viu antes. Nesse caso, ele atualiza os valores de rastreamento; caso contrário, ele pula esta etapa.

A popcntinstrução é uma instrução grande (4 bytes), mas não há nada que possa ser feito para evitar isso. No entanto, a lodsinstrução muito curta (1 byte) foi usada para carregar valores da matriz enquanto simultaneamente incrementava o ponteiro, a loopinstrução curta (2 bytes) foi usada para controle de loop (diminuindo automaticamente o contador de elemento e fazendo loop por tanto tempo pois há mais elementos restantes para serem examinados), e a xchginstrução muito curta (1 byte) foi usada em todo o processo.

Um extra xchgteve que ser usado no final para permitir o uso da lodsinstrução, que sempre carrega no eaxregistrador, mas essa compensação vale a pena.

Experimente online!

Minha primeira tentativa foi uma função de 20 bytes. Até agora, 18 bytes é o melhor que consegui propor. Estou curioso para ver se mais alguém consegue bater essa pontuação!

A única rota de melhoria que vejo seria se LOOPAexistisse uma instrução. Infelizmente, isso não acontece - os únicos códigos de condição suportados por LOOPsão E/ Ze NE/ NZ. Mas talvez outra pessoa possa expandir sua mente além de mim!

18 Arnauld Dec 20 2020 at 03:58

JavaScript (ES6),  49 48 47  45 bytes

2 bytes salvos graças a @ user81655

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

Experimente online!

Como?

Nós .sort()a lista de entrada com uma função recursiva que, dado pe q, limpa o conjunto de bits menos significativo em cada variável até que um deles seja igual a 0 (ou ambos simultaneamente). Isso permite ordenar a lista da maioria dos bits definidos. Em seguida, retornamos a primeira entrada, ou seja, a mais "pequena".

Comentado

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 bytes

Economizei muitos bytes graças a Adam e ngn.

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

Experimente online!

8 Noodle9 Dec 20 2020 at 09:07

C (gcc) , 80 77 bytes

Economizei 3 bytes graças ao att !!!

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

Experimente online!

7 Zaiborg Dec 21 2020 at 22:41

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

145-> 141 graças ao usuário
128-> 116 graças ao roofcat

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

Experimente online!

6 pavi2410 Dec 21 2020 at 23:13

Kotlin , 41 38 29 bytes

Código correto com muito menos bytes :) {Obrigado @vrintle}

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

Kotlin Playground


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

Kotlin Playground


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

Experimente online!

6 Makonede Dec 21 2020 at 01:44

05AB1E , 9 bytes

ΣžJ%b1¢}θ

Experimente 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 bytes

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

Experimente online!

-2 graças a Robin Ryder

-1 graças a Dominic van Essen.

4 Razetime Dec 20 2020 at 10:30

Stax , 18 bytes

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

Execute e depure-o

Preenchimento manual com 1s / 0s para obter a representação correta.

Exibe um único número para cada caso de teste.

4 GalenIvanov Dec 21 2020 at 15:02

K (ngn / k) , 11 bytes

{*x@>+/2\x}

Experimente online!

4 Danis Dec 20 2020 at 19:02

Python 3 , 52 bytes

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

Experimente online!

n%2**31- uma vez que em python os inteiros são infinitos, tem que mudar os números negativos. por exemplo -4se torna2147483644

bin(...) - traduzir para o formato binário

count("1") - conte o número de unidades


Python 3 , 50 bytes

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

Experimente online!

dois bytes mais curtos, mas não funciona com números negativos

4 Gabber Dec 22 2020 at 00:56

Scala , 54 42 40 36 bytes

Economizei alguns bytes graças a caird coinheringaahing, didymus, user e algumas dicas

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

Experimente online!

3 DominicvanEssen Dec 20 2020 at 15:17

Husk , 17 16 13 bytes

Editar: -1 byte graças a Razetime, e então -3 bytes graças a Leo

►(ΣḋΩ≥0+^32 2

Experimente online!

Husk usa nativamente inteiros de precisão arbitrária e, portanto, não tem noção do complemento de 2 de 32 bits para representar inteiros com sinal de 4 bytes negativos: como resultado, a função 'obter dígitos binários' - - infelizmente é inútil aqui para entradas negativas.
Portanto, precisamos calcular o 'bittness do complemento de 2' manualmente.

Agradeço a ajuda de Husk de Leo por usar Ωaqui.

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

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

Experimente online.

Explicação:

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

Jelly , 9 8 bytes

%Ø%BSƲÞṪ

Experimente online!

-1 byte usando Þ(classificar) em vez de ÐṀ(máximo). Isso foi inspirado pela resposta de Gio D e depois da edição deles e da minha, ambas as soluções são praticamente as mesmas.

Explicação

%Ø%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 bytes

ñÈu2pH)¤¬x

Tente

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

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

Experimente online!

2 vrintle Dec 20 2020 at 10:55

Ruby 2.7 , 36 33 34 bytes

Obrigado a Dingus por corrigir meu código para um caso especial! :)

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

Experimente online!

Usa argumentos de linha de comando para entrada, produz o número mais bittest como uma string. TIO usa uma versão mais antiga do Ruby, enquanto que no Ruby 2.7, numeramos os parâmetros, o que economiza dois bytes.

2 user Dec 21 2020 at 22:25

Java (JDK) , 44 bytes

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

Experimente online!

Isso é uma espécie de trapaça, pois aceita um Stream<Integer>como entrada e retorna um Optional<Int>.

2 user Dec 22 2020 at 04:21

Scala , 24 bytes

_ maxBy Integer.bitCount

Experimente online!

Separe-se da ótima primeira resposta de Gabber .

2 didymus Dec 22 2020 at 03:29

C # (compilador interativo do Visual C #) , 71 58 bytes

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

Experimente online!

  • Refatorado para usar lambda, conforme sugerido por @user nos comentários
1 Neil Dec 20 2020 at 04:34

Carvão , 22 bytes

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

Experimente online! O link é para a versão detalhada do código. Explicação:

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

Para cada número na lista, lance-o em um número não assinado de 32 bits, converta-o em binário e some os bits.

I§θ⌕η⌈η

Produza o número na posição de maior contagem de bits.

1 ChrisLoonam Dec 20 2020 at 13:14

SystemVerilog, 66 bytes

Esta será uma resposta imperfeita por enquanto, já que estou postando do meu telefone, mas a $countones()função do SV é perfeita aqui.

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

Wolfram Language (Mathematica) , 39 bytes

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

Experimente online!

1 ZaelinGoodman Dec 21 2020 at 03:32

PowerShell, 53 56 bytes

+5 bytes porque não lida com negativos adequadamente
-2 bytes graças ao mazzy

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

Nim , 75 bytes

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

Experimente online!

1 roblogic Dec 22 2020 at 05:17

Zsh, 85 bytes

experimente online!

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

Grande desafio, exigiu alguns dos Zshencantamentos mais estranhos ! Explicação:
for i;{... iteração implícita sobre todos os argumentos
$((i<0?[##2]2**32+i:[##2]i))... converter ipara o formato de 32 bits, usando o truque do complemento de dois se i<0
${#${(M)${(s::) //expression// }#1}}... expandir a string para o array, contar os elementos que (M) atch 1
((c>d))&&j=$i&&d=$c... manter o controle de qual entrada ié o "bittiest" de acordo com a contagem c
<<<$j... saída o vencedor

1 wroth Dec 22 2020 at 08:54

J , 20 bytes

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

Conforme escrito, quando dados múltiplos igualmente, números maximamente bitty, retorna o primeiro na matriz. Se {.\:for alterado para {:/:, dá o último. Experimente online!

1 EasyasPi Dec 23 2020 at 12:09

AArch64, 48 44 bytes

Instruções brutas (little endian hex de 32 bits):

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

Montagem não comentada:

        .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

Explicação

Assinatura da função 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;
}

A instrução de contagem de população de AArch64 está em NEON (o conjunto de instruções SIMD / ponto flutuante) e conta cada byte individualmente. Portanto, é um pouco estranho trabalhar com escalares aqui, então fazemos tudo em NEON.

v4 é a contagem máxima da população (v4, s4, h4 e d4 referem-se ao mesmo registro). Defina-o como 0.

        fmov    s4, #0

Carregue a próxima palavra int32 em v0 e aumente as palavras (x0) em 4.

        ldr     s0, [x0], #4

Armazene a contagem da população de cada byte em v0 no byte correspondente em v1.

        cnt     v1.8b, v0.8b

Adicione todas as faixas de 8 bits na v1 para obter a contagem total da população e armazene na v1 novamente.

        uaddlv  h1, v1.8b

Compare a contagem da população desta palavra ao máximo. Se for maior ou igual, v3 terá apenas 1 bits (verdadeiro), caso contrário, será todo 0 bits (falso).

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

Se v3 for verdadeiro, defina a palavra máxima (v2) como a palavra atual. max não é inicializado na primeira iteração, mas sempre será definido porque a contagem da população sempre será> = 0.

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

O mesmo, mas para a nova contagem máxima de população.

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

Decremente len (x1), e faça um loop se não for zero

        subs    x1, x1, #1
        bne     .Lloop

Fim do loop: Mova o valor máximo de um registrador NEON para o registrador de retorno (w0) e retorne.

        fmov    w0, s2
        ret

11 instruções = 44 bytes