Sort numbers by binary 1's count

Goal

Write a function or program sort an array of integers 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.

-
`825` only has 6 bits set. – marinus Feb 19 '14 at 0:00
You didn't explicitly mention, but does it need to be in descending order? – Nick T Feb 19 '14 at 4:12
You're right, I missed that. Everyone else has gone with descending, so we'll stick with that. – Hand-E-Food Feb 19 '14 at 7:19
I think the final number (21826) has been converted wrong. according to my Windows calculator, it's 0101 0101 0100 0010, not 0010 1010 1100 0010. – Nzall Feb 19 '14 at 9:04
Thanks for those corrections. That's weird about 21826 because I used Excel to convert the numbers to binary. I wonder about the rest now. – Hand-E-Food Feb 19 '14 at 22:02

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
-
Is J a combination of APL & Functional programing? – ak82 Feb 19 '14 at 8:24
@ak82 it's the ASCII version of APL – Jan Dvorak Feb 19 '14 at 14:59
@JanDvorak of sorts; there have been quite a few changes: jsoftware.com/papers/j4apl.htm (see Language section). – James Wood Feb 24 '14 at 20:22

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]
``````
-
Simple. Understandable. Short. Kudos for this solution. – Pierre Arlaud Feb 19 '14 at 9:14

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))
``````
-
This is really clever! I'm still trying to wrap my mind around it. – mowwwalker Feb 20 '14 at 21:35
Shouldn't `~y` work instead of `-!y`? – Toothbrush Feb 21 '14 at 15:42
@toothbrush The ending condition is that x or y are 0, in which case the expression `!x|-!y` becomes non-zero. `~` doesn't really fit in since it's non-zero for many inputs (including zero) – copy Feb 21 '14 at 16:13

Python 3 (44):

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

JavaScript [86 bytes]

``````a.sort(function(x,y){r='..toString(2).match(/1/g).length';return eval(y+r)-eval(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).match(/1/g).length';
return eval(y + r) - eval(x + r);
});

[16375, 15342, 32425, 19944, 11746, 28943, 28436, 15752, 3944, 21826, 825]
``````
-
Could you please tell how the `..` works? My understanding is that if `x = 5` then `eval(x + r)` becomes `eval(5..toString(2).match(/1/g).length)` which is, I suppose, invalid. Thanks. – Gaurang Tandon Feb 19 '14 at 12:03
@GaurangTandon It is not. As you know, in JS everything except literals is an object. And numbers. So theoretically (and practically) you may get properties or call methods of any non-literal via dot notation, as you do `'string'.length` or `[1,2,3].pop()`. In case of numbers you may do the same but you should keep in mind that after a single dot the parser will look for a fractional part of the number expecting a float value (as in `123.45`). If you use an integer you should "tell" the parser that a fractional part is empty, setting an extra dot before addressing a property: `123..method()`. – VisioN Feb 19 '14 at 12:17
You can save two bytes by stripping the zeros and treating the rest as a decimal number. Replace `match(/1/g).length` with `replace(/0/g,"")`. – DocMax Feb 19 '14 at 20:16
@VisioN Thanks! Learnt a new thing. – Gaurang Tandon Feb 20 '14 at 10:07

Python 3, 907772 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

-
So `0` will always be a part of your output then; That's not correct. – daniero Feb 19 '14 at 2:01
I don't see anything in the question that prohibits me from inserting a value. – Jetlef Feb 19 '14 at 2:04
I do: "An array of the same integers sorted as described." ;) Besides, why not just use `raw_input()` and drop some characters? – daniero Feb 19 '14 at 2:17
@daniero fixed it. Switching to Python 3 (a Python 2 answer was already present, gotta be creative!) allows me to use input(), saving two characters (two are to be added because of the brackets required by print()). – Jetlef Feb 19 '14 at 2:30
You can drop the `[]` inside `sorted`. Also the output of this program is the number of 1s in the numbers in input sorted, but you should output the number you received in input, sorted using the number of `1`s. Something like: `print(sorted(input().split(), key=lambda x:bin(int(x)).count('1')))` would be correct. – Bakuriu Feb 19 '14 at 9:33

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

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}

-
I've grown fond of that (ab?)use of Tr[] in golfing code. – Michael Stern Feb 19 '14 at 2:06

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}

-

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

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:]))"
``````
-
you can change `sum(int(d)for d in bin(x)[2:])` to `sum(map(int,bin(x)[2:]))` – Elisha Feb 19 '14 at 9:46
or even: `print sorted(input(),key=lambda x:-bin(x).count('1'))` – Elisha Feb 19 '14 at 9:50

Matlab, 34

Input in 'a'

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

Works for nonnegative numbers.

-

Java 8 - 87/11381/111 60/80 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 80 characters:

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

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

-
Any reason why you can't do `Integer.bitCount(x)<Integer.bitCount(y)?-1:1;`? Do you need the `-1,0,1` behavior? – Justin Feb 19 '14 at 5:02
Also, is it possible to replace the `<Integer>` with space? – Justin Feb 19 '14 at 6:38
You can also use `Long`, that save some space :) – RobAu Feb 19 '14 at 7:27
Also `a.sort((x,y)->Long.bitCount(x)-Long.bitCount(y));` – RobAu Feb 19 '14 at 7:31
@Quincunx comparator needs to return 0 when bitcounts are the same (by contract) – ratchet freak Feb 19 '14 at 10:02

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)
``````
-
would it be helpful to use the infix notation for `mod`, `n`mod`2`? It has the same precedence as multiplication and division. – Jan Dvorak Feb 19 '14 at 15:08
That wouldn't be too helpful for golfing reasons as far as I can see. I'd lose two spaces, but gain two backticks, right? – danmcardle Feb 19 '14 at 16:49
import Data.List;import Data.Ord;import Data.Bits;q=sortBy(comparing popCount) - 80C - or using your approach, import Data.List;import Data.Ord;b 0=0;b n=(mod n 2)+b(div n 2);q=sortBy(comparing b) - 86C – bazzargh Feb 20 '14 at 4:56
I tried avoiding imports entirely, best I could manage was 87C by golfing quicksort: b 0=0;b n=mod n 2+b(div n 2);q[]=[];q(a:c)=f((b a>).b)c++a:f((b a<=).b)c;f=(q.).filter – bazzargh Feb 20 '14 at 12:16

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
)
``````
-
well, someone has to bother with PHP – Einacio Feb 19 '14 at 15:13

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;
}
}
``````
-
Since this is a code golf competition, you should try to shorten your code. – Timtech Feb 19 '14 at 15:36

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.

-

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.

-
I've just tried your solution, but it didn't work. It doesn't sort the numbers. – Toothbrush Feb 19 '14 at 16:33
@toothbrush woops. Thanks for catching that, should work now. – Danny Feb 19 '14 at 16:40
Great work! I like it. – Toothbrush Feb 19 '14 at 16:48
Only 61 bytes: `z.sort((a,b)=>{c=d=e=0;while(++c<32)d+=a>>c&1,e+=b>>c&1},e-d)` (and thanks for the up-vote). – Toothbrush Feb 19 '14 at 17:08
My solution is now the same size as yours! – Toothbrush Feb 21 '14 at 17:37

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

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.

-
`sizeof l` saves a byte. The horribly ugly `#define p-__builtin_popcount(` can help save another one. – ugoren Feb 20 '14 at 12:28
@ugoren Thanks for the tips! The preprocessor one is such a hack, I had no idea such a thing was possible. Sadly it does not work on MSVC, but every byte counts! – Thomas Feb 21 '14 at 3:42

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}
``````
-
Postscript! My first love, my favorite language of all time! It is nice to see another believer in the One True Programming Language. – AJMansfield Feb 25 '14 at 2:40

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

PowerShell v3, 61

``````\$f={\$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:

``````\$l = 15342, 28943, 16375, 3944, 11746, 825, 32425, 28436, 21826, 15752, 19944
\$f.Invoke(\$l)
``````
-

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.

-

ECMAScript 6 (61 characters):

``````_=_=>_.toString(2).replace(/0/g,'');x.sort((a,b)=>_(b)-_(a))
``````

Expects the input array to be in `x`.

-

Julia, 49

``````f(a)=sortby(a,(n)->sum([c-'0' for c in bits(n)]))
``````
-
This is deprecated, the new interface is 1 more characters. – gggg Feb 19 '14 at 0:22