Objetivo

Escreva uma função ou programa que classifique uma matriz de números inteiros em ordem decrescente pelo número de 1's presentes em sua representação binária. Nenhuma condição de classificação secundária é necessária.

Exemplo de lista classificada

(usando números inteiros de 16 bits)

  Dec                Bin        1's
16375   0011111111110111        13
15342   0011101111101110        11
32425   0111111010101001        10
11746   0010110111100010         8
28436   0000110111110100         8
19944   0100110111101000         8
28943   0000011100011111         8
 3944   0000011111101000         7
15752   0011110110001000         7
  825   0000000011111001         6
21826   0101010101000010         6

Entrada

Uma matriz de números inteiros de 32 bits.

Saída

Uma matriz dos mesmos números inteiros classificados como descrito.

Pontuação

Esse é o código golf para o menor número de bytes a ser selecionado em uma semana.

J (11)

(\:+/"1@#:)

Esta é uma função que leva uma lista:

     (\:+/"1@#:) 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
16375 15342 32425 28943 11746 28436 19944 3944 15752 825 21826

Se você quiser dar um nome, custa um caractere extra:

     f=:\:+/"1@#:
     f 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
16375 15342 32425 28943 11746 28436 19944 3944 15752 825 21826

Explicação:

• \:: classificar para baixo em
• +/: soma de
• "1: cada linha de
• #:: representação binária

JavaScript, 39

Atualização: Agora menor que o Ruby.

x.sort(q=(x,y)=>!x|-!y||q(x&x-1,y&y-1))

40.

x.sort(q=(x,y)=>x&&y?q(x&x-1,y&y-1):x-y)

Explicação:

q é uma função recursiva. Se x ou y forem 0, ele retornará x-y(um número negativo se x for zero ou um número positivo se y for zero). Caso contrário, ele remove o bit mais baixo ( x&x-1) de x e ye repete.

Versão anterior (42)

x.sort(q=(x,y)=>x^y&&!x-!y+q(x&x-1,y&y-1))

Ruby 41

f=->a{a.sort_by{|n|-n.to_s(2).count(?1)}}

Teste:

a = [28943, 825, 11746, 16375, 32425, 19944, 21826, 15752, 15342, 3944, 28436];
f[a]
=> [16375, 15342, 32425, 11746, 28436, 28943, 19944, 15752, 3944, 21826, 825]

Python 3 (44):

def f(l):l.sort(lambda n:-bin(n).count('1'))

Lisp comum, 35

logcountretorna o número de 'on' bits em um número. Para uma lista l, temos:

(sort l '> :key 'logcount)

CL-USER> (sort (list 16375 15342 32425 11746 28436 19944 28943 3944 15752 825 21826) '> :key 'logcount)
;=> (16375 15342 32425 11746 28436 19944 28943 3944 15752 825 21826)

Como uma função autônoma, e no que basearemos a contagem de bytes:

(lambda(l)(sort l'> :key'logcount))

Python 3, 90 77 72 67 caracteres.

Nossa solução obtém uma entrada da linha de comando e imprime o número em ordem decrescente (67 caracteres) ou crescente (66).

Ordem decrescente

print(sorted(input().split(),key=lambda x:-bin(int(x)).count("1"))) # 67

Obrigado a @daniero , pela sugestão de usar um sinal de menos na contagem de 1 para reverter isso, em vez de usar uma fatia para reverter a matriz no final! Isso efetivamente salvou 5 caracteres.

Apenas para publicá-lo, a versão da ordem crescente (que foi a primeira que fizemos) levaria um caractere a menos.

Ordem crescente :

print(sorted(input().split(),key=lambda x:bin(int(x)).count("1"))) # 66

Obrigado a @Bakuriu pela sugestão = lambda x… . ; D

JavaScript [76 bytes]

a.sort(function(x,y){r='..toString(2).split(1).length';return eval(y+r+-x+r)})

onde aé uma matriz de entrada de números.

Teste:

[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort(function(x, y) {
    r = '..toString(2).split(1).length';
    return eval(y + r + -x + r);
});

[16375, 15342, 32425, 19944, 11746, 28943, 28436, 15752, 3944, 21826, 825]

Mathematica 30

SortBy[#,-DigitCount[#,2,1]&]&

Uso:

SortBy[#,-DigitCount[#,2,1]&]&@
                           {19944,11746,15342,21826,825,28943,32425,16375,28436,3944,15752}

{16375, 15342, 32425, 11746, 19944, 28436, 28943, 3944, 15752, 825, 21826}

k [15 caracteres]

{x@|<+/'0b\:'x}

Exemplo 1

{x@|<+/'0b\:'x}19944, 11746, 15342, 21826, 825, 28943, 32425, 16375, 28436, 3944, 15752

16375 15342 32425 28436 28943 11746 19944 15752 3944 825 21826

Exemplo 2 (todos os números são 2 ^ n -1)

{x@|<{+/0b\:x}'x}3 7 15 31 63 127

127 63 31 15 7 3

Mathematica 39

IntegerDigits[#,2] converte um número base 10 na lista de 1 e 0.

Tr soma os dígitos.

f@n_:=SortBy[n,-Tr@IntegerDigits[#,2]&]

Caso de teste

f[{19944, 11746, 15342, 21826, 825, 28943, 32425, 16375, 28436, 3944, 15752}]

{16375, 15342, 32425, 11746, 19944, 28436, 28943, 3944, 15752, 825, 21826}

Java 8 - 87/113 81/111 60/80 60/74/48 caracteres

Este não é um programa java completo, é apenas uma função (um método, para ser exato).

Ele assume que java.util.Liste java.lang.Long.bitCounté importado e tem 60 caracteres:

void s(List<Long>a){a.sort((x,y)->bitCount(x)-bitCount(y));}

Se nenhum material pré-importado for permitido, aqui está com 74 caracteres:

void s(java.util.List<Long>a){a.sort((x,y)->x.bitCount(x)-x.bitCount(y));}

Adicione mais 7 caracteres, se for necessário static.

[4 anos depois] Ou, se preferir, pode ser um lambda (obrigado @KevinCruijssen pela sugestão), com 48 bytes:

a->{a.sort((x,y)->x.bitCount(x)-x.bitCount(y));}

Python 2.x - 65 caracteres (bytes)

print sorted(input(),key=lambda x:-sum(int(d)for d in bin(x)[2:]))

Na verdade, são 66 caracteres, 65 se fizermos isso uma função (então você precisa de algo para chamá-lo, que é lamer para apresentar).

f=lambda a:sorted(a,key=lambda x:-sum(int(d)for d in bin(x)[2:]))

Demonstração no Bash / CMD:

echo [16, 10, 7, 255, 65536, 5] | python -c "print sorted(input(),key=lambda x:-sum(int(d)for d in bin(x)[2:]))"

Matlab, 34

Entrada em 'a'

[~,i]=sort(-sum(dec2bin(a)'));a(i)

Funciona para números não negativos.

C - 85 bytes (108 106 bytes)

Versão portátil no GCC / Clang / onde quer que __builtin_popcountesteja disponível (106 bytes):

#define p-__builtin_popcount(
c(int*a,int*b){return p*b)-p*a);}
void s(int*n,int l){qsort(n,l,sizeof l,c);}

Versão ultracondensada, não portátil, apenas funcional para MSVC (85 bytes):

#define p __popcnt
c(int*a,int*b){return p(*b)-p(*a);}
s(int*n,int l){qsort(n,l,4,c);}         /* or 8 as needed */

• A primeira nova linha incluída na contagem de bytes, por causa do #define, os outros não são necessários.

• A função a ser chamada está de s(array, length)acordo com as especificações.

• É possível codificar sizeofna versão portátil para salvar outros 7 caracteres, como algumas outras respostas em C fizeram. Não tenho certeza de qual deles vale mais em termos de relação comprimento / usabilidade, você decide.

PowerShell v3, 61 58 53

$args|sort{while($_){if($_-band1){1};$_=$_-shr1}}-des

O ScriptBlock do Sort-Objectcmdlet retorna uma matriz de 1 para cada 1 na representação binária do número. Sort-Objectclassifica a lista com base no comprimento da matriz retornada para cada número.

Executar:

script.ps1 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944

ECMAScript 6, 61

Assume que zé a entrada

z.sort((a,b)=>{c=d=e=0;while(++c<32)d+=a>>c&1,e+=b>>c&1},e-d)

Dados de teste

[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort(
    (a,b)=>{
        c=d=e=0;
        while(++c<32)
            d+=a>>c&1,e+=b>>c&1
    },e-d
)

[16375, 15342, 32425, 11746, 19944, 28436, 28943, 15752, 3944, 21826, 825]

Obrigado, escova de dentes para a solução mais curta.

R , 132 96 94 88 84 75 73 53 51 bytes

-20 graças à implementação de J.Doe -2 mais graças a Giuseppe

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

Minha postagem original:

pryr::f(rev(x[order(sapply(x,function(y)sum(as.double(intToBits(y)))))]))

Experimente online!

Eu tentei vários métodos diferentes antes de chegar a esse resultado.

Método da matriz: Criou uma matriz de duas colunas, uma coluna com o vetor de entrada, uma da soma da representação binária e, em seguida, classifiquei a soma do binário.

function(x){m=matrix(c(x,colSums(sapply(x,function(y){as.integer(intToBits(y))}))),nc=2,nr=length(x));m[order(m[,2],decreasing=T),]}

Não matriz: percebi que eu poderia jogar fora a função da matriz e criar um vetor de valores binários, somar, ordená-los e depois usar os valores ordenados para reordenar o vetor de entrada.

function(x){m=colSums(sapply(x,function(y){as.integer(intToBits(y))}));x[order(m,decreasing=T)]}

Pequenas alterações

function(x){m=colSums(sapply(x,function(y)as.double(intToBits(y))));x[order(m,decreasing=T)]}

Mais pequenas alterações Convertendo tudo para uma linha de código em vez de duas separadas por ponto e vírgula.

function(x)x[order(colSums(sapply(x,function(y)as.double(intToBits(y)))),decreasing=T)]

Método Sum Em vez de adicionar as colunas com colSumsa matriz binária criada por sapply, adicionei os elementos na coluna antes de sapply"terminar".

function(x)x[order(sapply(x,function(y)sum(as.double(intToBits(y)))),decreasing=T)]

Diminuindo para Rev Eu realmente queria diminuir a diminuição, mas R grita comigo se eu tentar diminuir decreasinga orderfunção, necessária para obter a ordem desejada como orderpadrão para aumentar, então lembrei da revfunção de reverter um vetor. EUREKA !!! A última mudança na solução final foi functionpara pryr::fsalvar mais 2 bytes

function(x)rev(x[order(sapply(x,function(y)sum(as.double(intToBits(y)))))])

Haskell, 123C

import Data.List
import Data.Ord
b 0=[]
b n=mod n 2:b(div n 2)
c n=(n,(sum.b)n)
q x=map fst$sortBy(comparing snd)(map c x)

Esta é a primeira maneira que pensei em resolver isso, mas aposto que há uma maneira melhor de fazer isso. Além disso, se alguém souber uma maneira de jogar golfe nas importações de Haskell, eu ficaria muito interessado em ouvi-la.

Exemplo

*Main> q [4,2,15,5,3]
[4,2,5,3,15]
*Main> q [7,0,2]
[0,2,7]

Versão não destruída (com explicações)

import Data.List
import Data.Ord

-- Converts an integer into a list of its bits
binary 0 = []
binary n = mod n 2 : binary (div n 2)

-- Creates a tuple where the first element is the number and the second element
-- is the sum of its bits.
createTuple n = (n, (sum.binary) n)

-- 1) Turns the list x into tuples
-- 2) Sorts the list of tuples by its second element (bit sum)
-- 3) Pulls the original number out of each tuple
question x = map fst $ sortBy (comparing snd) (map createTuple x)

CoffeeScript (94)

Código legível (212):

sort_by_ones_count = (numbers) ->
  numbers.sort (a, b) ->
    a1 = a.toString(2).match(/1/g).length
    b1 = b.toString(2).match(/1/g).length
    if a1 == b1
      0
    else if a1 > b1
      1
    else
      -1

console.log sort_by_ones_count [825, 3944, 11746, 15342, 15752, 16375, 19944, 21826, 28436, 28943, 32425]

Otimizado (213):

count_ones = (number) -> number.toString(2).match(/1/g).length
sort_by_ones_count = (numbers) -> numbers.sort (a, b) ->
  a1 = count_ones(a)
  b1 = count_ones(b)
  if a1 == b1 then 0 else if a1 > b1 then 1 else -1

Ofuscante (147):

c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  if a1 == b1 then 0 else if a1 > b1 then 1 else -1

Os operadores ternários são excessivamente longos (129):

c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  (0+(a1!=b1))*(-1)**(0+(a1>=b1))

Ainda por muito tempo, pare de transmitir (121):

c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  (-1)**(a1>=b1)*(a1!=b1)

Final (94):

c=(n)->n.toString(2).match(/1/g).length
s=(n)->n.sort((a, b)->(-1)**(c(a)>=c(b))*(c(a)!=c(b)))

Smalltalk (Smalltalk / X), 36 (ou talvez 24)

entrada em a; classifica destrutivamente um:

a sort:[:a :b|a bitCount>b bitCount]

versão funcional: retorna uma nova matriz classificada:

a sorted:[:a :b|a bitCount>b bitCount]

existe ainda uma variante mais curta (passando o nome ou a função como argumento) em 24 caracteres. Mas (suspiro) ele será o mais alto por último. Pelo que entendi, isso não foi solicitado, por isso não considero isso como pontuação de golfe:

a sortBySelector:#bitCount

PHP 5.4+ 131

Eu nem sei por que me preocupo com PHP, neste caso:

<?unset($argv[0]);usort($argv,function($a,$b){return strcmp(strtr(decbin($b),[0=>'']),strtr(decbin($a),[0=>'']));});print_r($argv);

Uso:

> php -f sortbybinaryones.php 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
Array
(
    [0] => 16375
    [1] => 15342
    [2] => 32425
    [3] => 28436
    [4] => 19944
    [5] => 11746
    [6] => 28943
    [7] => 3944
    [8] => 15752
    [9] => 825
    [10] => 21826
)

Scala, 58

def c(l:List[Int])=l.sortBy(-_.toBinaryString.count(_>48))

DFSORT (produto de classificação IBM Mainframe) 288 (cada linha de origem possui 72 caracteres, deve ter espaço na posição um)

 INREC IFTHEN=(WHEN=INIT,BUILD=(1,2,1,2,TRAN=BIT)), 
       IFTHEN=(WHEN=INIT,FINDREP=(STARTPOS=3,INOUT=(C'0',C'')))
 SORT FIELDS=(3,16,CH,D) 
 OUTREC BUILD=(1,2)

Apenas por diversão e sem matemática.

Pega um arquivo (pode ser executado a partir de um programa que usou uma "matriz") com os números inteiros. Antes da classificação, ele converte os números inteiros em bits (em um campo de 16 caracteres). Em seguida, altera os 0s nos bits para nada. ORDENAR Descendente do resultado dos bits alterados. Cria o arquivo classificado apenas com os números inteiros.

C

void main()
{
 int a[]={7,6,15,16};
 int b,i,n=0;
 for(i=0;i<4;i++)
 {  for(b=0,n=0;b<=sizeof(int);b++)
      (a[i]&(1<<b))?n++:n;   
    a[i]=n;
 }
 for (i = 1; i < 4; i++) 
  {   int tmp = a[i];
      for (n = i; n >= 1 && tmp < a[n-1]; n--)
         a[n] = a[n-1];
      a[n] = tmp;
  }    
}

C #, 88 89

int[] b(int[] a){return a.OrderBy(i=>-Convert.ToString(i,2).Count(c=>c=='1')).ToArray();}

Editar: ordem decrescente adiciona um caractere.

Javascript 84

Inspirado por outras respostas javascript, mas sem eval e regex.

var r=(x)=>(+x).toString(2).split('').reduce((p,c)=>p+ +c)
[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort((x,y)=>r(x)-r(y));

Javascript (82)

a.sort(function(b,c){q=0;while(b|c){b%2?c%2?0:q++:c%2?q--:0;b>>=1;c>>=1}return q})

Postscript, 126

Como a lista de valores pelos quais classificamos é conhecida de antemão e é muito limitada (32), essa tarefa pode ser realizada facilmente, mesmo que não haja uma classificação interna, escolhendo valores correspondentes para 1 .. 32. (É O (32n)? Provavelmente).

O procedimento espera a matriz na pilha e retorna a matriz 'classificada'.

/sort_by_bit_count {
    [ exch
    32 -1 1 {
        1 index
        {
            dup 2 32 string cvrs
            0 exch
            {48 sub add} forall
            2 index eq 
            {3 1 roll} {pop} ifelse
        } forall
        pop
    } for
    pop ]
} def

Ou, ritualmente sem espaço em branco e legibilidade:

/s{[exch 32 -1 1{1 index{dup 2 32 string cvrs 0 exch{48 sub add}forall 2 index eq{3 1 roll}{pop}ifelse}forall pop}for pop]}def

Então, se salvo em bits.ps nele, pode ser usado assim:

gs -q -dBATCH bits.ps -c '[(%stdin)(r)file 1000 string readline pop cvx exec] s =='
825 3944 11746 15342 15752 16375 19944 21826 28436 28943 32425
[16375 15342 32425 11746 19944 28436 28943 3944 15752 825 21826]

Eu acho que efetivamente é o mesmo que este Perl (ainda não há Perl aqui também):

sub f{map{$i=$_;grep{$i==(()=(sprintf'%b',$_)=~/1/g)}@_}reverse 1..32}

Embora isso , ao contrário do Postscript, possa ser facilmente jogado:

sub f{sort{j($b)-j($a)}@_}sub j{$_=sprintf'%b',@_;()=/1/g}

C - 124 111

Implementado como um método e usando a biblioteca padrão para a classificação. Um ponteiro para a matriz e o tamanho devem ser passados ​​como parâmetros. Isso funcionará apenas em sistemas com ponteiros de 32 bits. Em sistemas de 64 bits, alguns caracteres precisam ser gastos especificando definições de ponteiro.

Recuo para facilitar a leitura

c(int*a,int*b){
    int d,e,i;
    for(d=e=i=0;i-32;){
        d+=*a>>i&1;e+=*b>>i++&1;
    }
    return d>e?-1:d<e;
}
o(r,s){qsort(r,s,4,c);}

Exemplo de chamada:

main() {
    static int a[] ={1, 2, 3, 4, 5, 6, 7, 8, 9};
    o(a, 9);
}

Java 8: 144

static void main(String[]a){System.out.print(Stream.of(a).mapToInt(Integer::decode).sorted(Comparable.comparing(Integer::bitCount)).toArray());}

Em forma expandida:

static void main(String[] args){
    System.out.print(
        Stream.of(args).mapToInt(Integer::decode)
              .sorted(Comparable.comparing(Integer::bitCount))
              .toArray()
        );
}

Como você pode ver, isso funciona convertendo argspara para Stream<String>e depois para Stream<Integer>com a Integer::decodereferência de função (menor queparseInt ou valueOf) e, em seguida, classificando porInteger::bitCount , colocando-o em uma matriz e imprimindo-o.

Os fluxos tornam tudo mais fácil.