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

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

    Python-40 bytes

    l.sorted(key=lambda x:bin(x).count('1'))
    

    second to K!! Thwarted by K once again.......

    \$\endgroup\$
    • \$\begingroup\$ If l is a Python list, it has no sorted method. Perhaps you meant sort? Otherwise, your answer is practically a duplicate of another. Your sort delivers its results in ascending order, whereas descending was specified. Finally, you claim that your answer is second only to K, which is false. Too many problems to ignore. -1. \$\endgroup\$ – Steven Rumbalski Feb 26 '14 at 4:32

    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.