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\$
    – Nick T
    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\$
    – Hand-E-Food
    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\$
    – Hand-E-Food
    Feb 19, 2014 at 22:02
  • \$\begingroup\$ Solution using assembly and popcount instruction? \$\endgroup\$
    – eiennohito
    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\$
    – Simd
    Feb 19 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\$
    – roblogic
    Mar 6 at 20:21
  • 1
    \$\begingroup\$ Never too old to make a fuss :) \$\endgroup\$
    – Simd
    Mar 7 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\$
    – 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!

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\$
    – Jack Brounstein
    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\$
      – 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
    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

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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