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

71 Answers 71

1 2
3
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\$
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\$
    – Titus
    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!

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

Pyth, 8 bytes

_o/.BN\1

Try it online!

Explanation:
_o/.BN\1Q #Code with implicit variables
 o      Q #  Input list sorted by
  /   \1  #   How many "1"s are in
   .BN    #    The binary string of each number
_         # Reversed
\$\endgroup\$
0
\$\begingroup\$

Python 2, 59 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Save 7 bytes by replacing reverse=1 with *-1 to get descending order. Try it online! \$\endgroup\$ 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

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

K (oK), 19 bytes

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

Try it online!

\$\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
  • \$\endgroup\$
    0
    \$\begingroup\$

    Perl 6, 36 bytes

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

    Try it online!

    \$\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\$
      – Jo King
      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\$
      – Jo King
      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 
    
    \$\endgroup\$
    0
    \$\begingroup\$

    Factor, 31 bytes

    [ [ bit-count ] inv-sort-with ]
    

    Try it online!

    \$\endgroup\$
    1 2
    3

    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.