Sort numbers by binary 1's count

Question

Goal

Write a function or program sort an array of integers in descending order by the number of 1's present in their binary representation. No secondary sort condition is necessary.

Example sorted list

(using 16-bit integers)

  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

Input

An array of 32-bit integers.

Output

An array of the same integers sorted as described.

Scoring

This is code golf for the least number of bytes to be selected in one week's time.

Answer 1

J (11)

(\:+/"1@#:)

This is a function that takes a list:

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

If you want to give it a name, it costs one extra character:

     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

Explanation:

• \:: downwards sort on
• +/: sum of
• "1: each row of
• #:: binary representation

Answer 2

JavaScript, 39

Update: Now shorter than 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)

Explanation:

q is a recursive function. If x or y are 0, it returns x-y (a negative number if x is zero or a positive number if y is zero). Otherwise it removes the lowest bit (x&x-1) from x and y and repeats.

Previous version (42)

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

Answer 3

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

Answer 4

Python 3 (44):

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

Answer 5

Common Lisp, 35

logcount returns the number of ‘on’-bits in a number. For a list l, we have:

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

As a standalone function, and what I'll base the byte count on:

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

Answer 6

Python 3, 90 77 72 67 characters.

Our solution takes an input from the command-line, and prints the number in descending order (67 chars), or ascending (66).

Descending order

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

Thanks to @daniero, for the suggestion of using a minus in the 1's count to reverse it, instead of using a slice to reverse the array at the end! This effectively saved 5 characters.

Just for the sake of posting it, the ascending order version (which was the first we made) would take one character less.

Ascending order:

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

Thanks to @Bakuriu for the key=lambda x… suggestion. ;D

Answer 7

JavaScript [76 bytes]

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

where a is an input array of numbers.

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]

Answer 8

Mathematica 30

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

Usage:

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}

Answer 9

k [15 Chars]

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

Example 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

Example 2 (all numbers are 2^n -1)

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

127 63 31 15 7 3

Answer 10

Mathematica 39

IntegerDigits[#,2] converts a base 10 number to list of 1's and 0's.

Tr sums the digits.

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

Test Case

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

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

Answer 11

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

This is not a complete java program, it is just a function (a method, to be exact).

It assumes that java.util.List and java.lang.Long.bitCount are imported, and has 60 characters:

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

If no pre-imported stuff are allowed, here it is with 74 characters:

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

Add more 7 characters if it would be required that it should be static.

[4 years later] Or if you prefer, it could be a lambda (thanks @KevinCruijssen for the suggestion), with 48 bytes:

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

Answer 12

Python 2.x - 65 characters (bytes)

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

That's actually 66 characters, 65 if we make it a function (then you need something to call it which is lamer to present).

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

Demo in 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:]))"

Answer 13

Matlab, 34

Input in 'a'

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

Works for nonnegative numbers.

Answer 14

C - 85 bytes (108 106 bytes)

Portable version on GCC/Clang/wherever __builtin_popcount is available (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);}

Ultra-condensed, non-portable, barely functional MSVC-only version (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 */

---

• First newline included in byte count because of the #define, the others are not necessary.

• Function to call is s(array, length) according to specifications.

• Can hardcode the sizeof in the portable version to save another 7 characters, like a few other C answers did. I'm not sure which one is worth the most in terms of length-usability ratio, you decide.

Answer 15

PowerShell v3, 61 58 53

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

The ScriptBlock for the Sort-Object cmdlet returns an array of 1's for each 1 in the binary representation of the number. Sort-Object sorts the list based on the length of the array returned for each number.

To execute:

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

Answer 16

ECMAScript 6, 61

Assumes z is the input

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

Test data

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

Thanks, toothbrush for the shorter solution.

Answer 17

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

Answer 18

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)

Answer 19

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

Answer 20

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

Answer 21

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
)

Answer 22

Scala, 58

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

Answer 23

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.

Answer 24

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

Answer 25

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.

Answer 26

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

Answer 27

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

Answer 28

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}

Answer 29

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

Answer 30

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.