Encontre o número “Bittiest” [fechado]
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 7
ou 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^31
a 2^31 - 1
inclusive, usando complemento de dois para negativos.
Respostas
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Ṁị
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 esi
registro e o número de elementos na matriz no ecx
registro, e retorna o número mais "bittiest" na matriz no eax
registro.
Observe que esta é uma convenção de chamada personalizada que aceita argumentos nos registradores ecx
e 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 popcnt
instruçã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 popcnt
instrução é uma instrução grande (4 bytes), mas não há nada que possa ser feito para evitar isso. No entanto, a lods
instrução muito curta (1 byte) foi usada para carregar valores da matriz enquanto simultaneamente incrementava o ponteiro, a loop
instruçã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 xchg
instrução muito curta (1 byte) foi usada em todo o processo.
Um extra xchg
teve que ser usado no final para permitir o uso da lods
instrução, que sempre carrega no eax
registrador, 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 LOOPA
existisse uma instrução. Infelizmente, isso não acontece - os únicos códigos de condição suportados por LOOP
são E
/ Z
e NE
/ NZ
. Mas talvez outra pessoa possa expandir sua mente além de mim!
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 p
e 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
APL (Dyalog Unicode) , 15 bytes
Economizei muitos bytes graças a Adam e ngn.
{⊃⍒+⌿⍵⊤⍨32⍴2}⊃⊢
Experimente online!
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!
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!
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!
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
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.
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.
K (ngn / k) , 11 bytes
{*x@>+/2\x}
Experimente online!
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 -4
se 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
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!
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
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
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
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
Perl 5 , 54 bytes
sub f{(sprintf"%b",@_)=~y/1//}($_)=sort{f($b)<=>f$a}@F
Experimente online!
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.
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>
.
Scala , 24 bytes
_ maxBy Integer.bitCount
Experimente online!
Separe-se da ótima primeira resposta de Gabber .
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
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.
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
Wolfram Language (Mathematica) , 39 bytes
Last@*SortBy[Mod[#,2^32]~DigitCount~2&]
Experimente online!
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
Nim , 75 bytes
import algorithm,bitops
func b(n:seq):int=n.sortedByIt(it.countSetBits)[^1]
Experimente online!
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 Zsh
encantamentos mais estranhos ! Explicação:
for i;{
... iteração implícita sobre todos os argumentos
$((i<0?[##2]2**32+i:[##2]i))
... converter i
para 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
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!
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