Cel

Napisz funkcję lub program posortuj tablicę liczb całkowitych w porządku malejącym według liczby 1 obecnych w ich reprezentacji binarnej. Nie jest wymagany żaden warunek sortowania wtórnego.

Przykład posortowanej listy

(przy użyciu 16-bitowych liczb całkowitych)

  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

Wkład

Tablica 32-bitowych liczb całkowitych.

Wydajność

Tablica tych samych liczb całkowitych posortowana zgodnie z opisem.

Punktacja

Jest to kod golfowy dla najmniejszej liczby bajtów do wyboru w ciągu tygodnia.

J (11)

(\:+/"1@#:)

Ta funkcja pobiera listę:

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

Jeśli chcesz nadać mu nazwę, kosztuje to jedną dodatkową postać:

     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

Wyjaśnienie:

• \:: sortuj w dół na
• +/: suma
• "1: każdy rząd
• #:: reprezentacja binarna

JavaScript, 39

Aktualizacja: teraz krótsza niż 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)

Wyjaśnienie:

q jest funkcją rekurencyjną. Jeśli x lub y są x-yrówne 0, zwraca (liczba ujemna, jeśli x jest równa zero, lub liczba dodatnia, jeśli y wynosi zero). W przeciwnym razie usuwa najniższy bit ( x&x-1) zxiy i powtarza się.

Poprzednia wersja (42)

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

Rubinowy 41

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

Test:

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'))

Common Lisp, 35

logcountzwraca liczbę bitów „on” w liczbie. Do listy lmamy:

(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)

Jako samodzielna funkcja, na której liczę bajt, liczę:

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

Python 3, 90 77 72 67 znaków.

Nasze rozwiązanie pobiera dane z wiersza poleceń i wypisuje liczbę w porządku malejącym (67 znaków) lub rosnąco (66).

Kolejność malejąca

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

Dzięki @daniero za sugestię użycia minus w liczeniu 1 do odwrócenia go, zamiast używania wycinka do odwrócenia tablicy na końcu! To skutecznie uratowało 5 znaków.

Tylko w celu opublikowania go, rosnąca wersja zamówienia (która była pierwszą, którą stworzyliśmy) zabrałaby jedną postać mniej.

Porządek rosnący :

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

Dzięki @Bakuriu na klucz = lambda X ... sugestii. ;RE

JavaScript [76 bajtów]

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

gdzie ajest tablicą wprowadzania liczb.

Test:

[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]&]&

Stosowanie:

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 znaków]

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

Przykład 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

Przykład 2 (wszystkie liczby to 2 ^ n -1)

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

127 63 31 15 7 3

Mathematica 39

IntegerDigits[#,2] konwertuje liczbę podstawową 10 na listę 1 i 0.

Tr sumuje cyfry.

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

Przypadek testowy

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 znaków

To nie jest kompletny program Java, to tylko funkcja (a dokładniej metoda).

Zakłada, że java.util.Listi java.lang.Long.bitCountsą importowane, i ma 60 znaków:

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

Jeśli nie są dozwolone żadne elementy wcześniej zaimportowane, tutaj są 74 znaki:

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

Dodaj więcej 7 znaków, jeśli byłoby to konieczne static.

[4 lata później] Lub jeśli wolisz, może to być lambda (dzięki @KevinCruijssen za sugestię), z 48 bajtami:

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

Python 2.x - 65 znaków (bajtów)

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

To właściwie 66 znaków, 65 jeśli sprawimy, że będzie to funkcja (wtedy potrzebujesz czegoś, co można nazwać lamerem).

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

Demo w 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

Wpisz „a”

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

Działa dla liczb nieujemnych.

C - 85 bajtów (108 106 bajtów)

Wersja przenośna na GCC / Clang / gdziekolwiek __builtin_popcountjest dostępna (106 bajtów):

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

Ultra-skondensowana, nieprzenośna, ledwo funkcjonalna wersja tylko dla MSVC (85 bajtów):

#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 */

• Pierwsza nowa linia zawarta w liczbie bajtów z powodu #defineinnych nie jest konieczna.

• Funkcja wywoływania jest s(array, length)zgodna ze specyfikacjami.

• Można sizeofzapisać kod w wersji przenośnej, aby zapisać kolejne 7 znaków, podobnie jak kilka innych odpowiedzi w języku C. Nie jestem pewien, który z nich jest najbardziej wart pod względem stosunku długości do użyteczności, decydujesz.

PowerShell v3, 61 58 53

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

ScriptBlock dla polecenia Sort-Objectcmdlet zwraca tablicę 1 dla każdego 1 w binarnej reprezentacji liczby. Sort-Objectsortuje listę na podstawie długości tablicy zwracanej dla każdej liczby.

Wykonać:

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

ECMAScript 6, 61

Zakłada zsię, że dane wejściowe

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

Dane testowe

[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]

Dzięki, szczoteczka do zębów za krótsze rozwiązanie.

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

-20 thanks to J.Doe's implementation -2 more thanks to Giuseppe

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

My original post:

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

Try it online!

I tried several different methods before I got down to this result.

Matrix Method: Created a two column matrix, one column with the input vector, one of the sum of the binary representation, then I sorted on the sum of binary.

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),]}

Non-Matrix: Realized I could toss out the matrix function and instead create a vector of binary values, sum them, order them, then use the ordered values to reorder the input vector.

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

Minor Changes

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

More Minor Changes Converting entire thing to one line of code instead of two separated by a semicolon.

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

Sum Method Instead of adding the columns with colSums of the binary matrix created by sapply, I added the elements in the column before sapply "finished."

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

Decreasing to Rev I really wanted to shorten decreasing, but R squawks at me if I try to shorten decreasing in the order function, which was necessary to get the order desired as order defaults to increasing, then I remembered the rev function to reverse a vector. EUREKA!!! The last change in the final solution was function to pryr::f to save 2 more 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)

This is the first way I thought of solving this, but I bet there's a better way to do it. Also, if anyone knows of a way of golfing Haskell imports, I would be very interested to hear it.

Example

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

Ungolfed version (with explanations)

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)

Readable code (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]

Optimized (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

Obfuscating (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

Ternary operators are excessively long (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))

Too long yet, stop casting (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 (or maybe 24)

input in a; destructively sorts in a:

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

functional version: returns a new sorted array:

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

there is even a shorter variant (passing the name or the function as argument) in 24 chars. But (sigh) it will sort highest last. As I understood, this was not asked for, so I don't take that as golf score:

a sortBySelector:#bitCount

PHP 5.4+ 131

I don't even know why I bother with PHP, in this case:

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

Usage:

> 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 (IBM Mainframe sorting product) 288 (each source line is 72 characters, must have space in position one)

 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)

Just for fun, and no mathematics.

Takes a file (could be executed from a program which used an "array") with the integers. Before sorting, it translates the integers to bits (in a 16-character field). Then changes the 0s in the bits to nothing. SORT Descending on the result of the changed bits. Creates the sorted file with just the integers.

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();}

Edit: descending order adds a character.

Javascript 84

Inspired by other javascript answers, but without eval and 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

Because list of values by which we sort is known beforehand and very limited (32), this task can be easily done even if there's no built-in for sorting, by picking matching values for 1..32. (Is it O(32n)? Probably).

Procedure expects array on stack and returns 'sorted' array.

/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

Or, ritually stripped of white space and readability:

/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

Then, if saved to bits.ps it can be used like this:

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]

I think it effectively is the same as this Perl (there's yet no Perl here, too):

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

Though that, unlike Postscript, can be easily golfed:

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

C - 124 111

Implemented as a method and using the standard library for the sorting. A pointer to the array and the size should be passed as parameters. This will only work on systems with 32-bit pointers. On 64-bit systems, some characters have to be spent specifying pointer definitions.

Indentation for readability

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

Sample call:

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());}

In expanded form:

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

As you can see, this works by converting the args to a Stream<String>, then converting to a Stream<Integer> with the Integer::decode function reference (shorter than parseInt or valueOf), and then sorting by Integer::bitCount, then putting it in an array, and printing it out.

Streams make everything easier.