39
\$\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.

Improve this question
\$\endgroup\$
11
  • 3
    \$\begingroup\$ You didn't explicitly mention, but does it need to be in descending order? \$\endgroup\$ Commented Feb 19, 2014 at 4:12
  • 4
    \$\begingroup\$ You're right, I missed that. Everyone else has gone with descending, so we'll stick with that. \$\endgroup\$ Commented Feb 19, 2014 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\$ Commented Feb 19, 2014 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\$ Commented Feb 19, 2014 at 22:02
  • \$\begingroup\$ Solution using assembly and popcount instruction? \$\endgroup\$ Commented Feb 20, 2014 at 5:57

77 Answers 77

Reset to default
1 2
3
1
\$\begingroup\$

Pyth, 12 bytes

o_/.BsN"1"cw

Try it online!

explanation:

 print( o sorted( w input() c .split() , key = lambda N: _ - .B bin( s int( N N ) ) / .count( "1" "1" ) ) )

i'm aware there already is a Pyth answer, i just wanted to take a crack at it myself

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 6 4 bytes

µb∑⌐

Try it Online!

Explained

µb∑⌐ µ # lambda b # binary ∑ # sum (basically adds everything inside the binary, which is equivalent to the number of 1's ⌐ # reverse
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Zsh, 72 bytes

(for i;<<<${#${(M)${(s::)$((i<0?[##2]2**32+i:[##2]i))}#1}}\ $i)|sort -rn

Try it online!

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Whoa, I had no idea zsh could do this. \$\endgroup\$ Commented Feb 19, 2023 at 10:50
  • \$\begingroup\$ This solution also does two's complement arithmetic to handle negative integers. Most other solutions don't handle -4 correctly!!! (But this challenge is too old to make too much fuss about it) \$\endgroup\$ Commented Mar 6, 2023 at 20:21
  • 1
    \$\begingroup\$ Never too old to make a fuss :) \$\endgroup\$ Commented Mar 7, 2023 at 1:42
1
\$\begingroup\$

Thunno 2, 4 bytes

Þḃ1c

Attempt This Online!

Alternatively:

Þ2BS

Attempt This Online!

Explanation

Þḃ1c # Implicit input Þ # Sort the input by the following: ḃ # Convert the number to binary 1c # Count the number of 1s # Implicit output 
Þ2BS # Implicit input Þ # Sort the input by the following: 2B # Convert the number to a binary list S # Sum the resulting list # Implicit output
Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
1
  • \$\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\$ Commented May 17, 2018 at 15:38
0
\$\begingroup\$

Perl 5, 51 bytes

sub j{(sprintf'%b',@_)=~y/1//}say sort{j($b)-j$a}<>

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python 2, 59 bytes

def f(l):l.sort(key=lambda x:`bin(x)`.count('1'),reverse=1)

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Save 7 bytes by replacing reverse=1 with *-1 to get descending order. Try it online! \$\endgroup\$ Commented Sep 3, 2018 at 19:36
0
\$\begingroup\$

Pyt, 19 bytes

ĐĐ↑Ḷ⌊⁺ᴇĐ3ȘĦ*⇹↔+Ş⇹%Ɩ

Try it online!

Explanation

 Implicit input (as a list of integers) ĐĐ Triplicate the list ↑ Get the maximum value of the list (X_m) Ḷ⌊⁺ᴇĐ Push Y=10^(floor(log_10(X_m))+1) twice 3Ș Swap the top three elements on the list [puts the input on top] Ħ Get the Hamming weight of each element of the input * Multiply the Hamming weight by Y ⇹ Swap the top two elements on the stack ↔ Flip the stack [Puts the list on top, followed by Hamming weights multiplied by Y] + Add the two lists element-wise [resulting in Z=[Z_0,Z_1,...]] Ş Sort the resulting list in descending order ⇹ Swap the top two elements on the stack % Take Z mod Y Ɩ Convert Z mod Y to integers Implicit print

This is as long as it is because Pyt doesn't allow sorting by anything other than the values in the array; this means that a workaround had to be devised to allow the proper sorting

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

K (oK), 19 bytes

{t@>+/'(99#2)\'t:x}

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Dart, 102 99 84 bytes

F(a)=>'1'.allMatches(a.toRadixString(2)).length;f(List l)=>l.sort((a,b)=>F(a)-F(b));

Try it online!

  • -3 bytes by using allMatches instead of replaceAll
  • -15 bytes by using - instead of compareTo and replacing List< int > by List

    • Improve this answer
    \$\endgroup\$
    0
    \$\begingroup\$

    Perl 6, 36 bytes

    @a.sort({sum .base(2).comb}).reverse

    Try it online!

    Improve this answer
    \$\endgroup\$
    2
    • 1
      \$\begingroup\$ Taking input through a predefined variable is not allowed as it turns the submission into a snippet. Turning it into an anonymous code block is valid and the same length anyway \$\endgroup\$ Commented Nov 2, 2018 at 12:27
    • 1
      \$\begingroup\$ Some golfing tips: It's always shorter to use [R,] instead of reverse, though in this case, you can sprt be the negative of the sum instead. The sum can go on the end instead, like .sum and then you can turn it into an anonymous Whatever code object like -*.base(2).comb.sum. Of course, all this would make it a duplicate of nwellnhof's existing answer though don't let this discourage you! It's nice to see a new Perl 6 golfer! \$\endgroup\$ Commented Nov 2, 2018 at 12:39
    0
    \$\begingroup\$

    APL(NARS), 27 chars, 54 bytes

    {⍵[⍒{+/(2⍴⍨⌊1+2⍟1+⍵)⊤⍵}¨⍵]}

    test

     f←{⍵[⍒{+/(2⍴⍨⌊1+2⍟1+⍵)⊤⍵}¨⍵]} f 825 32425 15342 11746 28943 28436 21826 16375 15752 19944 3944 16375 15342 32425 11746 28943 28436 19944 15752 3944 825 21826
    Improve this answer
    \$\endgroup\$
    0
    \$\begingroup\$

    Jelly, 5 bytes

    BS$ÞṚ

    Try it online!

    Improve this answer
    \$\endgroup\$
    0
    \$\begingroup\$

    J-uby, 33 bytes

    :sort_by+(:%&"%b"|~:count&?1|:-@)

    Attempt This Online!

    Improve this answer
    \$\endgroup\$
    0
    \$\begingroup\$

    Pyth, 8 6 bytes

    _osjN2

    Try it online!

    Explanation
    _osjN2 | Full code _osjN2Q | with implicit variables --------+------------------------ o Q | Sort the input by jN2 | convert to binary list s | sum _ | Reverse
    Improve this answer
    \$\endgroup\$
    0
    \$\begingroup\$

    Pyt, 16 bytes

    ĐĦ⇹Đ↑⁺Đ3Ș⇹↔*+Ş⇹%

    Try it online!

    Pyt only allows for sorting on the values themselves, so a kludge had to be done.

    Đ implicit input (v); Đuplicate Ħ get Ħamming weight of each element (H) ⇹Đ↑ get maximum of input (m) ⁺ increment m Đ Đuplicate m 3Ș⇹↔ Stack manipulation * multiply H by m+1 + Add v to H*(m+1) Ş Şort in descending order ⇹% modulo m+1; implicit print
    Improve this answer
    \$\endgroup\$
    0
    \$\begingroup\$

    Thunno, \$ 14 \log_{256}(96) \approx \$ 11.52 bytes

    DebdiSEZZz;.AK

    Attempt This Online!

    Unfortunately Thunno lacks a "sort by" built-in.

    Explanation

    DebdiSEZZz;.AK # Implicit input De E # Duplicate and map: bd # Convert to binary iS # And sum the digits ZZ # Zip with input z; # Reverse-sort .AK # Last element of each # Implicit output
    Improve this answer
    \$\endgroup\$
    1 2
    3

    Start asking to get answers

    Find the answer to your question by asking.

    Ask question

    Explore related questions

    See similar questions with these tags.