35
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You didn't explicitly mention, but does it need to be in descending order? \$\endgroup\$ – Nick T Feb 19 '14 at 4:12
  • 3
    \$\begingroup\$ You're right, I missed that. Everyone else has gone with descending, so we'll stick with that. \$\endgroup\$ – Hand-E-Food Feb 19 '14 at 7:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Nzall Feb 19 '14 at 9:04
  • \$\begingroup\$ 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. \$\endgroup\$ – Hand-E-Food Feb 19 '14 at 22:02
  • \$\begingroup\$ Solution using assembly and popcount instruction? \$\endgroup\$ – eiennohito Feb 20 '14 at 5:57

69 Answers 69

2
\$\begingroup\$

ECMAScript 6 (61 characters):

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

Expects the input array to be in x.

\$\endgroup\$
2
\$\begingroup\$

PowerShell v2 or later, 44

sort{[convert]::ToString($_,2)-replace0}-des

The long version:

Sort-Object -Property {[convert]::ToString($_, 2) -replace '0', ''} -Descending

"sort" is a default alias for the Sort-Object cmdlet.
Sort-Object allows sorting the incoming list by evaluating an expression on the fly, which is the script block inside the curly braces.
The .NET class "Convert" is used to convert the incoming integer ("$_") into its binary string representation.
The "-replace" Operator will then remove all zeros, so that only a string of ones remains (the string "Replace()" method would have worked, too, but would have been longer).
Since these strings all consist of the same character, they'll be sorted by length, ascending by default. The switch argument "Descending" will reverse the order, and since there's another argument 'Debug', the first three characters are required for PowerShell to identify the switch.

The list to sort is expected in the pipeline/stdin, for example:

$l = 15342, 28943, 16375, 3944, 11746, 825, 32425, 28436, 21826, 15752, 19944
$l | sort{[convert]::ToString($_,2)-replace0}-des

Sort-Object
https://docs.microsoft.com/en-us/powershell/module/microsoft.powershell.utility/sort-object?view=powershell-6

Convert Class
https://msdn.microsoft.com/en-us/library/system.convert(v=vs.110).aspx

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Feb 20 '18 at 19:57
  • \$\begingroup\$ It's a code snippet, not function or program. Sorry. \$\endgroup\$ – mazzy Nov 2 '18 at 8:38
2
\$\begingroup\$

05AB1E, 4 bytes

ΣbSO

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 4-byte alternative which is a literal translation of the title: Σb1¢ (Σort numbers by binary 1s ¢ount) :) (Bit of a weird s in sort though.. ;p) \$\endgroup\$ – Kevin Cruijssen Sep 4 '18 at 8:54
2
\$\begingroup\$

Perl 6, 27 bytes

*.sort(-*.base(2).comb.sum)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Alternatively, .comb(~1) \$\endgroup\$ – Jo King Oct 31 '18 at 3:04
2
\$\begingroup\$

Julia 1.0, 41 bytes

a->sort(a,by=x->sum((x>>n)&1 for n=0:63))

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Firstly, you can use two argument sum, like this: sum(n->x>>n&1,0:63). Secondly, by=count_ones is even shorter \$\endgroup\$ – H.PWiz Jan 6 at 13:36
  • 1
    \$\begingroup\$ Also, shorter than two argument sum is: sum(x.>>(0:63).&1)) \$\endgroup\$ – H.PWiz Jan 6 at 13:43
1
\$\begingroup\$

GolfScript, 14 chars

~{2base 0-,}$`

Example input (sorted in numerical order):

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

Example output (sorted by bit count) for the input above:

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

Note that the program above sorts the input in ascending order by bit count. If you insist on descending order, that'll cost one extra char:

~{2base 0-,~}$`

Explanation:

  • ~ evals the input. Since you didn't specify the input format, I took the liberty of assuming that the input is provided as a GolfScript array literal (i.e. a series of whitespace-separated numbers wrapped in [ ]).

  • { }$ applies the code inside the braces to each element of the array, and sorts them according to the resulting sort keys.

    • Inside the braces, 2base uses the built-in base conversion operator to turn the number into an array of bits (e.g. 19[1 0 0 1 1]). The 0- then removes all the zero bits from the array (the space before it is needed to keep base0 from being parsed as a single token) and the , counts the length of the remaining array.

    • (In the descending order version, the ~ then bitwise negates the count, effectively applying the map x ↦ −(x + 1) and thus inverting the sort order.)

  • Finally, the ` un-evals the sorted array, converting it back into the input format for output.

\$\endgroup\$
1
\$\begingroup\$

C++ and QT

template<typename T>

//Compars the number of ones in the binary representation of some numbers 
bool onesCountSort()(Const T* a, const T* b) const
{
   int aCount = getOnesCount(&a);
   int bCount = getOnesCount(&b);
   return aCount < bCount;
}

//Returns the number of ones in a number
int getOnesCount(T value) const
{
    int rVal = 0;
    while(value > 0)
    {
       rVal++;
       value = value >> 1;
    } 
    return rVal;
}    

int main(int argc, char *argv[])
{
   QList<int> listTest;
   listTest << 16375;
   listTest << 15342; 
   listTest << 32425; 
   listTest << 11746; 
   listTest << 28436;
   //...

   qSort(list.begin(); list.end(), onesCountSort<int>());//Sort by binary ones count
   qSort(list.end(); list.begin(), onesCountSort<int>());//Reverse the sort
}

Edit:

template<typename T>

//Compars the number of ones in the binary representation of some numbers 
bool onesCountSort()(Const T* a, const T* b) const
{
   return getOnesCount(a) < getOnesCount(b);
}

int getOnesCount(const T* value, int count = 0) const
{
    return &value ? count : getOnesCount(value >> 1, count + 1);
}        
\$\endgroup\$
1
\$\begingroup\$

C, 95 chars

Call s(array, size) to sort an array.
The framework is based on AShelly's answer, with a different bit count function.
Only works on 32bit platforms.

c(unsigned a){return a?a%2+c(a/2):0;}
f(int*a,int*b){return c(*b)-c(*a);}
s(a,n){qsort(a,n,4,f);}

The bit count function treats the numbers as unsigned, so division will discard the low bit.

\$\endgroup\$
1
\$\begingroup\$

**

C++(Visual Studio 2013), 112

**

#define n int
#define s __popcnt
n* d(n i[], n l){sort(i, i+l, [](n a, n b){return  s(a) > s(b); });return i;}

Unobfuscated:

#define n int
#define s __popcnt
n* d(n i[], n l){
    std::sort(i, i+l, [](n a, n b){return  s(a) > s(b); });
    return i;
}

haven't touched C++ for a while. While not the shortest, it PROBABLY is the fastest, by far, though it depends highly if the __popcnt is implemented as single CPU instruction, or set.

I might fire up mathbrain later and see if it's possible to compare two numbers by bits and see which one has more bits set(without any string conversions or bit counting). I think there is some kind of bit-hack that can be used, but it's probably longer.

\$\endgroup\$
1
\$\begingroup\$

K, 14

{x@>+/'0b\:'x}

.

k){x@>+/'0b\:'x} 28943 16375 15342
16375 15342 28943
\$\endgroup\$
1
\$\begingroup\$

php 5.3, 117 109

Thank to @mniip to point out some more char save. So New One are

usort($a,function($u,$v){return $u==$v?0:(substr_count(decbin($u),'1')<substr_count(decbin($v),'1')?1:-1);});

Older One

usort($a,function($u,$v){if($u==$v)return 0;return substr_count(decbin($u),'1')<substr_count(decbin($v),'1')?1:-1;});
\$\endgroup\$
  • \$\begingroup\$ I'm pretty sure you can save a few chars if you combine your return statements into one using ternary operator \$\endgroup\$ – mniip Feb 20 '14 at 10:42
1
\$\begingroup\$

C : 112

C(a){int c=a!=0;while(a&=a-1)c++;return c;}
B(int*a,int*b){return C(*b)-C(*a);}
S(int*a,int n){qsort(a,n,4,B);}

works on gcc with Target: x86_64-linux-gnu

usage: S(array, size);

\$\endgroup\$
  • \$\begingroup\$ similar to @albeert's answer, which I only saw after I completed this... \$\endgroup\$ – AShelly Feb 20 '14 at 4:15
  • \$\begingroup\$ S(n,int*a) doesn't compile. Even when fixed, doesn't work on by 64bit Linux with gcc. Omitting return from C is very fragile. \$\endgroup\$ – ugoren Feb 20 '14 at 9:38
  • \$\begingroup\$ Ah, you're right. I missed the compiler error among the warnings and got the same output as the previous run, so I assumed it was good. I went back to my last working version: +12 char. \$\endgroup\$ – AShelly Feb 20 '14 at 12:05
1
\$\begingroup\$

Javascript (ECMAScript 6) - 41 Characters

Takes an array a as input:

a.sort(ພ=(ຟ,ຝ)=>ຟ*ຝ?ພ(ຟ&ຟ-1,ຝ&ຝ-1):(ຝ-ຟ))

Testing (with less obfuscated code):

JSFIDDLE

a=[19944, 11746, 15342, 21826, 825, 28943, 32425, 16375, 28436, 3944, 15752];
a.sort(_=(b,c)=>b*c?_(b&b-1,c&c-1):(c-b))
console.log(a.toString());

Gives this output:

16375,15342,32425,19944,11746,28943,28436,3944,15752,21826,825
\$\endgroup\$
1
\$\begingroup\$

C#, 191 183 172 thanks to Rik

 using System.Linq;class P{static void Main(string[]a){System.Console.WriteLine(string.Join(" ",a.Select(int.Parse).OrderBy(v=>{int c=0;for(;v>0;c++,v&=v-1);return-c;})));}}

Formatted:

using System.Linq;
class P
{
    static void Main(string[] a)
    {
        System.Console.WriteLine(string.Join(" ", a.Select(int.Parse)
            .OrderBy(v => { 
                int c = 0; 
                for (; v > 0; c++, v &= v - 1);
                return -c; 
            })
        ));
    }
}

When run as foo.exe 32425 28943 28436 21826 19944 16375 15752 15342 11746 3944 825 the output is:

16375 15342 32425 28943 28436 19944 11746 15752 3944 21826 825

Including the bitcount:

16375   13
15342   11
32425   10
28943   8
28436   8
19944   8
11746   8
15752   7
3944    7
21826   6
825     5

As function only: 100 89 chars

...Which some seem to regard as correct too:

int[] v(int[]a){return a.OrderBy(v=>{int c=0;for(;v>0;c++,v&=v-1);return-c;}).ToArray();}

To use, call v() with an array of ints to be sorted by binary 1's count.

\$\endgroup\$
  • \$\begingroup\$ instead of OrderByDescending you can use OrderBy and return -c in your lambda and save 9 chars. \$\endgroup\$ – Rik Feb 19 '14 at 14:59
  • \$\begingroup\$ D'oh! Thanks! Why didn't I think of that?! :D Actually, it saves 10 since I don't need a space between return and -c :D \$\endgroup\$ – RobIII Feb 19 '14 at 15:08
1
\$\begingroup\$

C# - 98

C# can't really compete in "the smallest" category. Still fun, though :)

x.Select(i=>new{v=i,c=Convert.ToString(i,2).Count(c=>c=='1')}).OrderByDescending(a=>a.c);

Used:

var y = new [] {28943, 825, 11746, 16375, 32425, 19944, 21826, 15752, 15342, 3944, 28436}.Select(i=>new{v=i,c=Convert.ToString(i,2).Count(c=>c=='1')}).OrderByDescending(a=>a.c);
Console.WriteLine(y.Select(a => a.v.ToString()).Aggregate((s1,s2)=>s1+","+s2));

Result:

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

EDIT: .NetFiddle - http://dotnetfiddle.net/ahMMbq

\$\endgroup\$
1
\$\begingroup\$

C# 95

int[]o(int[]d){return d.OrderByDescending(v =>Convert.ToString(v,2).Sum(c =>c-'0')).ToArray();}
\$\endgroup\$
1
\$\begingroup\$

Haskell - 107100 (including sample list and main call) else 100-22=78

import Data.List
b 0=0
b n=mod n 2+b(div n 2)
c q=map snd$ sort$ zip(map b q)q
main=print$ c [1..100]

Result:

[1,2,4,8,16,32,64,3,5,6,9,10,12,17,18,20,24,33,34,36,40,48,65,66,68,72,80,96,7,11,13,14,19,21,22,25,26,28,35,37,38,41,42,44,49,50,52,56,67,69,70,73,74,76,81,82,84,88,97,98,100,15,23,27,29,30,39,43,45,46,51,53,54,57,58,60,71,75,77,78,83,85,86,89,90,92,99,31,47,55,59,61,62,79,87,91,93,94,63,95]
\$\endgroup\$
1
\$\begingroup\$

PHP - 89 bytes

Here is the best I have been able to do so far.

function f($a){usort($a,function($a,$b){$c=gmp_popcount;return$c($a)<$c($b);});return$a;}

If I am allowed to sort the array in-place (which is idiomatic for PHP), then it is only 81:

function f(&$a){usort($a,function($a,$b){$c=gmp_popcount;return$c($a)<$c($b);});}
\$\endgroup\$
1
\$\begingroup\$

Perl, 56 bytes

sub x{$_=sprintf'%b',@_;s/1//g}print sort{x($b)<=>x$a}<>

Input is expected in STDIN, one integer per line. Output is in descending order.

sprintf '%b' converts the number into binary representation. s/1// replaces the 1, the return value is the number of replacements. Thus function x returns the number of 1 in the binary representation of the number. The sorting function sorts the number according to their binary 1's count. By exchanging $a and $b the sorting order is reversed to ascending.

\$\endgroup\$
1
\$\begingroup\$

Longwinded C#:

using System;

namespace P
{
    class P
    {
        static int T(int v) { int i = 0; while (v != 0) { i += (v & 1); v >>= 1; } return i; }
        static int[] S(int[] a)
        { Array.Sort<int>(a, (x, y) => { return (T(x) > T(y)) ? -1 : (T(x) < T(y)) ? 0 : 1; }); return a; }
        static void Main(string[] args)
        {
            foreach (var i in S(new int[]{ 28943, 825, 11746, 16375, 32425, 19944, 21826, 15752, 15342, 3944, 28436 }))
                Console.WriteLine("{0}\t{1}\t{2}", i, Convert.ToString(i, 2), T(i));
            Console.ReadKey();
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

Japt, 7 bytes

ñ_¤è1Ãw

Test it


Explanation

Implicit input of array U.

ñ_   Ã

Sort (ñ) by passing each element through a function.

¤

Convert to base 2 string.

è1

Count the number of 1s.

w

Reverse and implicitly output the resulting array.


Alternatives

ñ_¤o1Ãw
ñ_¤kTÃw
\$\endgroup\$
  • \$\begingroup\$ You need descending sort, not ascending. \$\endgroup\$ – Erik the Outgolfer Jul 28 '17 at 14:26
  • \$\begingroup\$ Another alternative I believe would be ñ_¤è1 n. Don't think that'd be shorter combined with the other alternative, but you never know... \$\endgroup\$ – ETHproductions Jul 28 '17 at 22:42
1
\$\begingroup\$

Javascript - Lengthy but result is according to my expectation - sorting numbers in ascending order according to number of binary 1s in them. If binary 1s are equal then sorting done on the base of decimal ascending order.

Thumbs up if anybody can improve or give shorter solution in javascript

  function sortNumberByBinary1s(numbers){
      //sort numbers first
      numbers=numbers.sort();
      console.log(numbers,'numbers');

      //2dimenstional array to store original number and its binary 1s
      var binNumArr = [];
      //loop to count binary 1s in each number
      for(i=0;i<numbers.length;i++){
        var num = numbers[i];
        // var binNum = Number(num.toString(2));

        let binary1 = 0;
        do if(num&1) binary1++;
        while(num>>=1);

        //store original number and its binary 1s in 2dimenstional array
        binNumArr[numbers[i]]={'number':numbers[i],'binary1':binary1};

      }

    //sort binNumArr (22dimenstional array by Number value)
    //filter(() => true) to remove empty values
      var byNumSortedArray=binNumArr.sort(function(a, b){return a.number - b.number}).filter(() => true);

      //sort byNumberSorted array by binary1 value
      var byBinary1SortedArray=byNumSortedArray.sort(function(a, b){return a.binary1 - b.binary1});

      console.log(byBinary1SortedArray,'byBinary1SortedArray');

    //get only sortedNumbers from array and return result
      var sortedNumbers=[]
      for(i=0;i<byBinary1SortedArray.length;i++){
        try{
          var number = byBinary1SortedArray[i].number;
        }catch(e){
          console.log(e,'error');
        }
        console.log(number,'number');
        sortedNumbers[i]=number;

      }
      console.log(sortedNumbers,'sortedNumbers array');
      return sortedNumbers;

    }

Input: [3,4,5,6,7,8]

  sortNumberByBinary1s([3,4,5,6,7,8]);
  • {number: 4, binary1: 1}
  • {number: 8, binary1: 1}
  • {number: 3, binary1: 2}
  • {number: 5, binary1: 2}
  • {number: 6, binary1: 2}
  • {number: 7, binary1: 3}

Output: [4, 8, 3, 5, 6, 7]

\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to the site! This is a code golf challenge, so you should aim to minimise your code as much as possible, starting with removing all comments and changing variable names to a single letter \$\endgroup\$ – caird coinheringaahing Apr 5 '18 at 21:59
1
\$\begingroup\$

Stax, 6 bytes

╖a☻║B⌡

Run and debug it at staxlang.xyz!

This will output the Unicode characters in a string. Add $ at the end (or step through execution) to see decimal.

Unpacked (7 bytes) and Explanation

{:B|+or
{          Begin block.
 :B          Convert to binary array. Ex: 11746 -> [1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0]
   |+        Sum.
     o     Terminate block and use it to sort array (ascending).
      r    Reverse. Implicit print.

Before descending order was specified in the question, there was a 6-byte unpacked solution. This is short enough that packing (into ÇÄì¬♥#) changed nothing:

{:B|+o

Run and debug it at staxlang.xyz!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 57 54 bytes

-3 bytes thanks to Laikoni! (making the counting function pointfree by using the fact that we only need to support 32bit ints)

sortOn$sum.(mapM(pure[0,1])[1..32]!!)
import Data.List

Try it online!

Explanation

The function call sortOn f xs returns xs :: [x] sorted by comparing ys = map (f :: x -> y) xs where the type y has to be an instance of Ord, so we just need to feed it a function that counts the number of 1-bits:

(sum . mapM (const [0,1]) [1..32] !!)

The expression mapM (const [0,1]) [1..n] generates all the sequences of [0,1] with length n (n = 32 is sufficient since we only need to handle 32bit ints) in the right order, so we just need to index into these and take it's sum.

Example: mapM (const [0,1]) [1..2] !! 1 ≡ [[0,0],[0,1],[1,0],[1,1]] !! 2 ≡ [0,1]

\$\endgroup\$
  • \$\begingroup\$ As the challenge only requires 32-bit integers, this could be shortened to sortOn$sum.(mapM(pure[0,1])[1..32]!!) while losing higher number support. Btw. nice workaround with #define on TIO. \$\endgroup\$ – Laikoni May 16 '18 at 13:39
1
\$\begingroup\$

K (ngn/k), 11 10 bytes

{x@>+/2\x}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

MathGolf, 5 bytes

á{âΣ~

Try it online!

Explanation:

á{âΣ~
á{     Sort by the
    ~  Negative
   Σ   Digit sum
  â    Of the number converted to binary
\$\endgroup\$
1
\$\begingroup\$

Kotlin, 57 44 bytes

{it.sortedBy{-it.toString(2).sumBy{it-'0'}}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Powershell, 40 45 bytes

$args|sort{for(;$_;$_=$_-shr1){$s+=$_%2}$s}-d

Explanation:

Sort all arguments from the predefined $args in a descendant order by sum of bits $s.

Note: The script uses -shr1 instead /2 because a Powershell does not provide integer div.

Test script:

$f = {

$args|sort{for(;$_;$_=$_-shr1){$s+=$_%2}$s}-d

}

&$f 0 1 3 4
&$f 16375 15342 32425 11746 28436 19944 28943 3944 15752 825 21826

Output:

3
0
4
1
16375
15342
32425
19944
28943
11746
28436
15752
3944
21826
825
\$\endgroup\$
0
\$\begingroup\$

Jelly, 5 bytes (non-competing?)

BS$ÞṚ

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PHP, 71

usort($a,function($a,$b){for(;$a&&$b;$a&=$a-1,$b&=$b-1);return$b-$a;});

If we assume there will be no dulicates, 69

foreach($a as$v)$b[$v]=gmp_popcount($v);arsort($b);$a=array_keys($b);

If we accept ascending sort, 68

foreach($a as$v)$b[$v]=gmp_popcount($v);asort($b);$a=array_keys($b);

That is, given $a. So, I'm unclear on whether we can assume the input, as various solutions go to various lengths to get it.

\$\endgroup\$
  • \$\begingroup\$ Actually, you´d habe to use $argv and print_r the result or add the 23 bytes function overhead: function($a){return$a;}. gmp is not in the default config and actually you´d had to add the bytecount of installation or at least the necessary config line. Nice ones nonetheless. \$\endgroup\$ – Titus May 17 '18 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.