Sort numbers by binary 1's count

35

3

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.

Hand-E-Food

Posted 11 years ago

Reputation: 7 912

formatted test cases please? – FantaC – 7 years ago

2You didn't explicitly mention, but does it need to be in descending order? – Nick T – 11 years ago

3You're right, I missed that. Everyone else has gone with descending, so we'll stick with that. – Hand-E-Food – 11 years ago

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. – Nzall – 11 years ago

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. – Hand-E-Food – 11 years ago

Solution using assembly and popcount instruction? – eiennohito – 11 years ago

Some CPUs have efficient opcodes for doing this, but I suspect assembly language to be a bit too verbose to win code golf. (I think Motorola 68040 had it.) – hippietrail – 11 years ago

Does the sort have to be stable or not? – Tim Seguine – 11 years ago

Am I allowed to sort the input array in-place? It is a difference of 8 characters for my solution. – Tim Seguine – 11 years ago

Stability is not required. I never said the input had to remain unchanged, so in-place sorting is fine. – Hand-E-Food – 11 years ago

Answers

27

J (11)

(\:+/"1@#:)

This is a function that takes a list:

     (\:+/"1@#:) 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
16375 15342 32425 28943 11746 28436 19944 3944 15752 825 21826

If you want to give it a name, it costs one extra character:

     f=:\:+/"1@#:
     f 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
16375 15342 32425 28943 11746 28436 19944 3944 15752 825 21826

Explanation:

  • \:: downwards sort on
  • +/: sum of
  • "1: each row of
  • #:: binary representation

marinus

Posted 11 years ago

Reputation: 30 224

3There's also \:1#.#: which saves a few bytes. – miles – 8 years ago

5@ak82 it's the ASCII version of APL – John Dvorak – 11 years ago

3

@JanDvorak of sorts; there have been quite a few changes: http://www.jsoftware.com/papers/j4apl.htm (see Language section).

– James Wood – 11 years ago

17

JavaScript, 39

Update: Now shorter than Ruby.

x.sort(q=(x,y)=>!x|-!y||q(x&x-1,y&y-1))

40

x.sort(q=(x,y)=>x&&y?q(x&x-1,y&y-1):x-y)

Explanation:

q is a recursive function. If x or y are 0, it returns x-y (a negative number if x is zero or a positive number if y is zero). Otherwise it removes the lowest bit (x&x-1) from x and y and repeats.

Previous version (42)

x.sort(q=(x,y)=>x^y&&!x-!y+q(x&x-1,y&y-1))

copy

Posted 11 years ago

Reputation: 6 466

Can anyone help me in case a secondary sorting is required, please?

– Manubhargav – 7 years ago

This is really clever! I'm still trying to wrap my mind around it. – mowwwalker – 11 years ago

Shouldn't ~y work instead of -!y? – Toothbrush – 11 years ago

@toothbrush The ending condition is that x or y are 0, in which case the expression !x|-!y becomes non-zero. ~ doesn't really fit in since it's non-zero for many inputs (including zero) – copy – 11 years ago

15

Ruby 41

f=->a{a.sort_by{|n|-n.to_s(2).count(?1)}}

Test:

a = [28943, 825, 11746, 16375, 32425, 19944, 21826, 15752, 15342, 3944, 28436];
f[a]
=> [16375, 15342, 32425, 11746, 28436, 28943, 19944, 15752, 3944, 21826, 825]

daniero

Posted 11 years ago

Reputation: 17 193

2Simple. Understandable. Short. Kudos for this solution. – Pierre Arlaud – 11 years ago

8

Python 3 (44):

def f(l):l.sort(lambda n:-bin(n).count('1'))

Blender

Posted 11 years ago

Reputation: 665

8

Common Lisp, 35

logcount returns the number of ‘on’-bits in a number. For a list l, we have:

(sort l '> :key 'logcount)
CL-USER> (sort (list 16375 15342 32425 11746 28436 19944 28943 3944 15752 825 21826) '> :key 'logcount)
;=> (16375 15342 32425 11746 28436 19944 28943 3944 15752 825 21826)

As a standalone function, and what I'll base the byte count on:

(lambda(l)(sort l'> :key'logcount))

Joshua Taylor

Posted 11 years ago

Reputation: 660

7

Python 3, 90 77 72 67 characters.

Our solution takes an input from the command-line, and prints the number in descending order (67 chars), or ascending (66).

Descending order

print(sorted(input().split(),key=lambda x:-bin(int(x)).count("1"))) # 67

Thanks to @daniero, for the suggestion of using a minus in the 1's count to reverse it, instead of using a slice to reverse the array at the end! This effectively saved 5 characters.

Just for the sake of posting it, the ascending order version (which was the first we made) would take one character less.

Ascending order:

print(sorted(input().split(),key=lambda x:bin(int(x)).count("1"))) # 66

Thanks to @Bakuriu for the key=lambda x… suggestion. ;D

Jetlef

Posted 11 years ago

Reputation: 121

So 0 will always be a part of your output then; That's not correct. – daniero – 11 years ago

I don't see anything in the question that prohibits me from inserting a value. – Jetlef – 11 years ago

I do: "An array of the same integers sorted as described." ;) Besides, why not just use raw_input() and drop some characters? – daniero – 11 years ago

1@daniero fixed it. Switching to Python 3 (a Python 2 answer was already present, gotta be creative!) allows me to use input(), saving two characters (two are to be added because of the brackets required by print()). – Jetlef – 11 years ago

You can drop the [] inside sorted. Also the output of this program is the number of 1s in the numbers in input sorted, but you should output the number you received in input, sorted using the number of 1s. Something like: print(sorted(input().split(), key=lambda x:bin(int(x)).count('1'))) would be correct. – Bakuriu – 11 years ago

@Bakuriu awesome! Thank you. Your suggestion prints values in ascending order, though, which may or may not be what the OP wants. – Jetlef – 11 years ago

You can use lambda x:-bin(... insted of [::-1], sort of like I did :) – daniero – 11 years ago

@daniero Clever… StackOverflow teaches you how to do things properly, CodeGolf teaches you the best proper hacks. I'm glad I found this site. ;D -- For a moment I though we could use the fact that binaries contain only 0's and 1's to our advantage (if we sort by ascending order, and by the number of 0's, we get the number with the least 0's (and thus, the most 1's) first) -- but then I recalled that Python doesn't pad binary numbers with 0's… – Jetlef – 11 years ago

The second argument to sorted is key, so there's no need for key= either. – Blender – 11 years ago

Question defines input and output as an array. So it seems there is no need parse input and print output. – Steven Rumbalski – 11 years ago

7

JavaScript [76 bytes]

a.sort(function(x,y){r='..toString(2).split(1).length';return eval(y+r+-x+r)})

where a is an input array of numbers.

Test:

[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort(function(x, y) {
    r = '..toString(2).split(1).length';
    return eval(y + r + -x + r);
});

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

VisioN

Posted 11 years ago

Reputation: 4 490

Can anyone help me in case a secondary sorting is required, please?

– Manubhargav – 7 years ago

1a.sort(function(x,y){r='..toString(2).match(/1/g).length';return eval(y+r+-x+r)}) – l4m2 – 7 years ago

69 Bytes a.sort((x,y)=>{f=z=>z.toString(2).replace(/0/g,"");return f(x)<f(y)}) Correct me if i'm wrong but length isn't needed if you use < instead of - – Adyrem – 6 years ago

Could you please tell how the .. works? My understanding is that if x = 5 then eval(x + r) becomes eval(5..toString(2).match(/1/g).length) which is, I suppose, invalid. Thanks. – Gaurang Tandon – 11 years ago

1@GaurangTandon It is not. As you know, in JS everything except literals is an object. And numbers. So theoretically (and practically) you may get properties or call methods of any non-literal via dot notation, as you do 'string'.length or [1,2,3].pop(). In case of numbers you may do the same but you should keep in mind that after a single dot the parser will look for a fractional part of the number expecting a float value (as in 123.45). If you use an integer you should "tell" the parser that a fractional part is empty, setting an extra dot before addressing a property: 123..method(). – VisioN – 11 years ago

1You can save two bytes by stripping the zeros and treating the rest as a decimal number. Replace match(/1/g).length with replace(/0/g,""). – DocMax – 11 years ago

@VisioN Thanks! Learnt a new thing. – Gaurang Tandon – 11 years ago

6

Mathematica 30

SortBy[#,-DigitCount[#,2,1]&]&

Usage:

SortBy[#,-DigitCount[#,2,1]&]&@
                           {19944,11746,15342,21826,825,28943,32425,16375,28436,3944,15752}

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

Dr. belisarius

Posted 11 years ago

Reputation: 5 345

6

k [15 Chars]

{x@|<+/'0b\:'x}

Example 1

{x@|<+/'0b\:'x}19944, 11746, 15342, 21826, 825, 28943, 32425, 16375, 28436, 3944, 15752

16375 15342 32425 28436 28943 11746 19944 15752 3944 825 21826

Example 2 (all numbers are 2^n -1)

{x@|<{+/0b\:x}'x}3 7 15 31 63 127

127 63 31 15 7 3

nyi

Posted 11 years ago

Reputation: 448

5

Java 8 - 87/113 81/111 60/80 60/74/48 characters

This is not a complete java program, it is just a function (a method, to be exact).

It assumes that java.util.List and java.lang.Long.bitCount are imported, and has 60 characters:

void s(List<Long>a){a.sort((x,y)->bitCount(x)-bitCount(y));}

If no pre-imported stuff are allowed, here it is with 74 characters:

void s(java.util.List<Long>a){a.sort((x,y)->x.bitCount(x)-x.bitCount(y));}

Add more 7 characters if it would be required that it should be static.

[4 years later] Or if you prefer, it could be a lambda (thanks @KevinCruijssen for the suggestion), with 48 bytes:

a->{a.sort((x,y)->x.bitCount(x)-x.bitCount(y));}

Victor Stafusa

Posted 11 years ago

Reputation: 8 612

I know it's been 4 years, but you can golf Long.bitCount to x.bitCount in your version without pre-imported stuff (not sure how it was four years ago, but imports are counted towards the byte-count these days). Also, since you've specified Java 8, you can change void s(java.util.List<Long>a) to a->. Try it online - 48 bytes Nice answer though, +1 from me.

– Kevin Cruijssen – 7 years ago

@KevinCruijssen I don't remember this puzzle, since as you already said, it was 4 years since then. However, I'm not sure if a lambda expression with a inferred parameter type depending on an ommited context would be acceptable. Anyway, I added it to the answer, thanks. – Victor Stafusa – 7 years ago

@VictorStafusa Well, it is acceptable these days, but I also don't know about four years ago when this challenge was posted. Btw, in the 80-byte version you can still golf Long.bitCount to x.bitCount, since you've already specified x is a Long in the java.util.List<Long>a parameter. – Kevin Cruijssen – 7 years ago

1@KevinCruijssen Thanks. I'm so used that using a variable instance to call a static method is a bad practice that I ever forgot that the compiler accepts that. – Victor Stafusa – 7 years ago

Any reason why you can't do Integer.bitCount(x)<Integer.bitCount(y)?-1:1;? Do you need the -1,0,1 behavior? – Justin – 11 years ago

Also, is it possible to replace the <Integer> with space? – Justin – 11 years ago

You can also use Long, that save some space :) – RobAu – 11 years ago

Also a.sort((x,y)->Long.bitCount(x)-Long.bitCount(y)); – RobAu – 11 years ago

@Quincunx comparator needs to return 0 when bitcounts are the same (by contract) – ratchet freak – 11 years ago

@Quincunx. Yes, I needed the -1,0,1 behaviour, but by using - as suggested by RobAu, it gets smaller. And really need the <Long> (was <Integer>). Otherwise I screw the compiler type inference and get a compile error. – Victor Stafusa – 11 years ago

@RobAu Thanks, I should have seen those obvious shortcuts. – Victor Stafusa – 11 years ago

Realistically, this is a function because it doesn't leverage the this reference or any of this's variables. So while technically a method because it -could-, it doesn't; I would personally call this a function. (This is reinforced by the fact that you could, as you state, make it static. Static method === function.) – corsiKa – 11 years ago

I have a complete 150 char java 8 solution. http://codegolf.stackexchange.com/a/22064/7981

– AJMansfield – 11 years ago

5

Mathematica 39

IntegerDigits[#,2] converts a base 10 number to list of 1's and 0's.

Tr sums the digits.

f@n_:=SortBy[n,-Tr@IntegerDigits[#,2]&]

Test Case

f[{19944, 11746, 15342, 21826, 825, 28943, 32425, 16375, 28436, 3944, 15752}]

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

DavidC

Posted 11 years ago

Reputation: 24 524

I've grown fond of that (ab?)use of Tr[] in golfing code. – Michael Stern – 11 years ago

4

Python 2.x - 65 characters (bytes)

print sorted(input(),key=lambda x:-sum(int(d)for d in bin(x)[2:]))

That's actually 66 characters, 65 if we make it a function (then you need something to call it which is lamer to present).

f=lambda a:sorted(a,key=lambda x:-sum(int(d)for d in bin(x)[2:]))

Demo in Bash/CMD:

echo [16, 10, 7, 255, 65536, 5] | python -c "print sorted(input(),key=lambda x:-sum(int(d)for d in bin(x)[2:]))"

Nick T

Posted 11 years ago

Reputation: 3 197

you can change sum(int(d)for d in bin(x)[2:]) to sum(map(int,bin(x)[2:])) – Elisha – 11 years ago

1or even: print sorted(input(),key=lambda x:-bin(x).count('1')) – Elisha – 11 years ago

4

Matlab, 34

Input in 'a'

[~,i]=sort(-sum(dec2bin(a)'));a(i)

Works for nonnegative numbers.

fraktal

Posted 11 years ago

Reputation: 41

4

C - 85 bytes (108 106 bytes)

Portable version on GCC/Clang/wherever __builtin_popcount is available (106 bytes):

#define p-__builtin_popcount(
c(int*a,int*b){return p*b)-p*a);}
void s(int*n,int l){qsort(n,l,sizeof l,c);}

Ultra-condensed, non-portable, barely functional MSVC-only version (85 bytes):

#define p __popcnt
c(int*a,int*b){return p(*b)-p(*a);}
s(int*n,int l){qsort(n,l,4,c);}         /* or 8 as needed */

  • First newline included in byte count because of the #define, the others are not necessary.

  • Function to call is s(array, length) according to specifications.

  • Can hardcode the sizeof in the portable version to save another 7 characters, like a few other C answers did. I'm not sure which one is worth the most in terms of length-usability ratio, you decide.

Thomas

Posted 11 years ago

Reputation: 191

2sizeof l saves a byte. The horribly ugly #define p-__builtin_popcount( can help save another one. – ugoren – 11 years ago

@ugoren Thanks for the tips! The preprocessor one is such a hack, I had no idea such a thing was possible. Sadly it does not work on MSVC, but every byte counts! – Thomas – 11 years ago

4

PowerShell v3, 61 58 53

$args|sort{while($_){if($_-band1){1};$_=$_-shr1}}-des

The ScriptBlock for the Sort-Object cmdlet returns an array of 1's for each 1 in the binary representation of the number. Sort-Object sorts the list based on the length of the array returned for each number.

To execute:

script.ps1 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944

Rynant

Posted 11 years ago

Reputation: 2 353

it's work. How it work? How the magic '.' comes to 'based on the length of the array'? – mazzy – 6 years ago

The '.' executes the scriptblock that comes after it. The sort command sorts based on the output of the outer scriptblock. I realize now that the inner scriptblock is not needed. see edit – Rynant – 6 years ago

$f={ is redundant, while -> for, -band1-> %2, -des->-d and other golf tricks. It's clear. Can you explain how to work $args|sort{@(1,1,...,1)}? It's work! How the sort compares arrays without explicit .Count? where to read about it? Thanks! – mazzy – 6 years ago

1@mazzy, you're right, I removed the redundant bits now. It's the default sorting of the Sort-Object cmdlet. See: help Sort-Object -Parameter property I don't know where the default sorting property for types is defined, but for arrays it is Count or Length. – Rynant – 6 years ago

Good guess. But $args|sort{while($_){if($_-band1){$_};$_=$_-shr1}}-des gives a wrong result. Therefore, it is not Count. It's very interesting. Thanks again. – mazzy – 6 years ago

3

R, 132 96 94 88 84 75 73 53 51 bytes

-20 thanks to J.Doe's implementation -2 more thanks to Giuseppe

function(x)x[order(colSums(sapply(x,intToBits)<1))]

My original post:

pryr::f(rev(x[order(sapply(x,function(y)sum(as.double(intToBits(y)))))]))

Try it online!

I tried several different methods before I got down to this result.

Matrix Method: Created a two column matrix, one column with the input vector, one of the sum of the binary representation, then I sorted on the sum of binary.

function(x){m=matrix(c(x,colSums(sapply(x,function(y){as.integer(intToBits(y))}))),nc=2,nr=length(x));m[order(m[,2],decreasing=T),]}

Non-Matrix: Realized I could toss out the matrix function and instead create a vector of binary values, sum them, order them, then use the ordered values to reorder the input vector.

function(x){m=colSums(sapply(x,function(y){as.integer(intToBits(y))}));x[order(m,decreasing=T)]}

Minor Changes

function(x){m=colSums(sapply(x,function(y)as.double(intToBits(y))));x[order(m,decreasing=T)]}

More Minor Changes Converting entire thing to one line of code instead of two separated by a semicolon.

function(x)x[order(colSums(sapply(x,function(y)as.double(intToBits(y)))),decreasing=T)]

Sum Method Instead of adding the columns with colSums of the binary matrix created by sapply, I added the elements in the column before sapply "finished."

function(x)x[order(sapply(x,function(y)sum(as.double(intToBits(y)))),decreasing=T)]

Decreasing to Rev I really wanted to shorten decreasing, but R squawks at me if I try to shorten decreasing in the order function, which was necessary to get the order desired as order defaults to increasing, then I remembered the rev function to reverse a vector. EUREKA!!! The last change in the final solution was function to pryr::f to save 2 more bytes

function(x)rev(x[order(sapply(x,function(y)sum(as.double(intToBits(y)))))])

Sumner18

Posted 11 years ago

Reputation: 1 334

153 bytes – J.Doe – 6 years ago

151 bytes improving on @J.Doe 's excellent golf! – Giuseppe – 6 years ago

3

ECMAScript 6, 61

Assumes z is the input

z.sort((a,b)=>{c=d=e=0;while(++c<32)d+=a>>c&1,e+=b>>c&1},e-d)

Test data

[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort(
    (a,b)=>{
        c=d=e=0;
        while(++c<32)
            d+=a>>c&1,e+=b>>c&1
    },e-d
)

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

Thanks, toothbrush for the shorter solution.

Danny

Posted 11 years ago

Reputation: 1 563

1I've just tried your solution, but it didn't work. It doesn't sort the numbers. – Toothbrush – 11 years ago

@toothbrush woops. Thanks for catching that, should work now. – Danny – 11 years ago

Great work! I like it. – Toothbrush – 11 years ago

1Only 61 bytes: z.sort((a,b)=>{c=d=e=0;while(++c<32)d+=a>>c&1,e+=b>>c&1},e-d) (and thanks for the up-vote). – Toothbrush – 11 years ago

1My solution is now the same size as yours! – Toothbrush – 11 years ago

2

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

Manuel

Posted 11 years ago

Reputation: 21

Welcome to PPCG! – Martin Ender – 7 years ago

It's a code snippet, not function or program. Sorry. – mazzy – 6 years ago

2

05AB1E, 4 bytes

ΣbSO

Try it online!

Magic Octopus Urn

Posted 11 years ago

Reputation: 19 422

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) – Kevin Cruijssen – 6 years ago

2

Perl 6, 27 bytes

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

Try it online!

nwellnhof

Posted 11 years ago

Reputation: 10 037

Alternatively, .comb(~1) – Jo King – 6 years ago

2

Haskell, 123C

import Data.List
import Data.Ord
b 0=[]
b n=mod n 2:b(div n 2)
c n=(n,(sum.b)n)
q x=map fst$sortBy(comparing snd)(map c x)

This is the first way I thought of solving this, but I bet there's a better way to do it. Also, if anyone knows of a way of golfing Haskell imports, I would be very interested to hear it.

Example

*Main> q [4,2,15,5,3]
[4,2,5,3,15]
*Main> q [7,0,2]
[0,2,7]

Ungolfed version (with explanations)

import Data.List
import Data.Ord

-- Converts an integer into a list of its bits
binary 0 = []
binary n = mod n 2 : binary (div n 2)

-- Creates a tuple where the first element is the number and the second element
-- is the sum of its bits.
createTuple n = (n, (sum.binary) n)

-- 1) Turns the list x into tuples
-- 2) Sorts the list of tuples by its second element (bit sum)
-- 3) Pulls the original number out of each tuple
question x = map fst $ sortBy (comparing snd) (map createTuple x)

danmcardle

Posted 11 years ago

Reputation: 695

would it be helpful to use the infix notation for mod, n`mod`2? It has the same precedence as multiplication and division. – John Dvorak – 11 years ago

That wouldn't be too helpful for golfing reasons as far as I can see. I'd lose two spaces, but gain two backticks, right? – danmcardle – 11 years ago

import Data.List;import Data.Ord;import Data.Bits;q=sortBy(comparing popCount) - 80C - or using your approach, import Data.List;import Data.Ord;b 0=0;b n=(mod n 2)+b(div n 2);q=sortBy(comparing b) - 86C – bazzargh – 11 years ago

I tried avoiding imports entirely, best I could manage was 87C by golfing quicksort: b 0=0;b n=mod n 2+b(div n 2);q[]=[];q(a:c)=f((b a>).b)c++a:f((b a<=).b)c;f=(q.).filter – bazzargh – 11 years ago

2

Julia 1.0, 41 bytes

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

Try it online!

gggg

Posted 11 years ago

Reputation: 1 715

1Firstly, you can use two argument sum, like this: sum(n->x>>n&1,0:63). Secondly, by=count_ones is even shorter – H.PWiz – 6 years ago

1Also, shorter than two argument sum is: sum(x.>>(0:63).&1)) – H.PWiz – 6 years ago

2

DFSORT (IBM Mainframe sorting product) 288 (each source line is 72 characters, must have space in position one)

 INREC IFTHEN=(WHEN=INIT,BUILD=(1,2,1,2,TRAN=BIT)), 
       IFTHEN=(WHEN=INIT,FINDREP=(STARTPOS=3,INOUT=(C'0',C'')))
 SORT FIELDS=(3,16,CH,D) 
 OUTREC BUILD=(1,2)

Just for fun, and no mathematics.

Takes a file (could be executed from a program which used an "array") with the integers. Before sorting, it translates the integers to bits (in a 16-character field). Then changes the 0s in the bits to nothing. SORT Descending on the result of the changed bits. Creates the sorted file with just the integers.

Bill Woodger

Posted 11 years ago

Reputation: 1 391

2

Smalltalk (Smalltalk/X), 36 (or maybe 24)

input in a; destructively sorts in a:

a sort:[:a :b|a bitCount>b bitCount]

functional version: returns a new sorted array:

a sorted:[:a :b|a bitCount>b bitCount]

there is even a shorter variant (passing the name or the function as argument) in 24 chars. But (sigh) it will sort highest last. As I understood, this was not asked for, so I don't take that as golf score:

a sortBySelector:#bitCount

blabla999

Posted 11 years ago

Reputation: 1 869

2

CoffeeScript (94)

Readable code (212):

sort_by_ones_count = (numbers) ->
  numbers.sort (a, b) ->
    a1 = a.toString(2).match(/1/g).length
    b1 = b.toString(2).match(/1/g).length
    if a1 == b1
      0
    else if a1 > b1
      1
    else
      -1

console.log sort_by_ones_count [825, 3944, 11746, 15342, 15752, 16375, 19944, 21826, 28436, 28943, 32425]

Optimized (213):

count_ones = (number) -> number.toString(2).match(/1/g).length
sort_by_ones_count = (numbers) -> numbers.sort (a, b) ->
  a1 = count_ones(a)
  b1 = count_ones(b)
  if a1 == b1 then 0 else if a1 > b1 then 1 else -1

Obfuscating (147):

c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  if a1 == b1 then 0 else if a1 > b1 then 1 else -1

Ternary operators are excessively long (129):

c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  (0+(a1!=b1))*(-1)**(0+(a1>=b1))

Too long yet, stop casting (121):

c = (n) -> n.toString(2).match(/1/g).length
s = (n) -> n.sort (a, b) ->
  a1 = c(a)
  b1 = c(b)
  (-1)**(a1>=b1)*(a1!=b1)

Final (94):

c=(n)->n.toString(2).match(/1/g).length
s=(n)->n.sort((a, b)->(-1)**(c(a)>=c(b))*(c(a)!=c(b)))

Aaron J

Posted 11 years ago

Reputation: 21

2

Scala, 58

def c(l:List[Int])=l.sortBy(-_.toBinaryString.count(_>48))

ValarDohaeris

Posted 11 years ago

Reputation: 231

2

PHP 5.4+ 131

I don't even know why I bother with PHP, in this case:

<?unset($argv[0]);usort($argv,function($a,$b){return strcmp(strtr(decbin($b),[0=>'']),strtr(decbin($a),[0=>'']));});print_r($argv);

Usage:

> php -f sortbybinaryones.php 15342 28943 16375 3944 11746 825 32425 28436 21826 15752 19944
Array
(
    [0] => 16375
    [1] => 15342
    [2] => 32425
    [3] => 28436
    [4] => 19944
    [5] => 11746
    [6] => 28943
    [7] => 3944
    [8] => 15752
    [9] => 825
    [10] => 21826
)

Decent Dabbler

Posted 11 years ago

Reputation: 605

well, someone has to bother with PHP – Einacio – 11 years ago

2

C

void main()
{
 int a[]={7,6,15,16};
 int b,i,n=0;
 for(i=0;i<4;i++)
 {  for(b=0,n=0;b<=sizeof(int);b++)
      (a[i]&(1<<b))?n++:n;   
    a[i]=n;
 }
 for (i = 1; i < 4; i++) 
  {   int tmp = a[i];
      for (n = i; n >= 1 && tmp < a[n-1]; n--)
         a[n] = a[n-1];
      a[n] = tmp;
  }    
}

Venkatesh K

Posted 11 years ago

Reputation: 219

4Since this is a code golf competition, you should try to shorten your code. – Timtech – 11 years ago

2

C#, 88 89

int[] b(int[] a){return a.OrderBy(i=>-Convert.ToString(i,2).Count(c=>c=='1')).ToArray();}

Edit: descending order adds a character.

Rik

Posted 11 years ago

Reputation: 781

2

ECMAScript 6 (61 characters):

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

Expects the input array to be in x.

Toothbrush

Posted 11 years ago

Reputation: 3 197

2

Javascript 84

Inspired by other javascript answers, but without eval and regex.

var r=(x)=>(+x).toString(2).split('').reduce((p,c)=>p+ +c)
[28943,825,11746,16375,32425,19944,21826,15752,15342,3944,28436].sort((x,y)=>r(x)-r(y));

vittore

Posted 11 years ago

Reputation: 121

The question is code golf, please try to 'golf' your code: remove unnecessary whitespace and try to make your code as small as possible. Also, include a character count in your answer. – ProgramFOX – 11 years ago

2

C - 124 111

Implemented as a method and using the standard library for the sorting. A pointer to the array and the size should be passed as parameters. This will only work on systems with 32-bit pointers. On 64-bit systems, some characters have to be spent specifying pointer definitions.

Indentation for readability

c(int*a,int*b){
    int d,e,i;
    for(d=e=i=0;i-32;){
        d+=*a>>i&1;e+=*b>>i++&1;
    }
    return d>e?-1:d<e;
}
o(r,s){qsort(r,s,4,c);}

Sample call:

main() {
    static int a[] ={1, 2, 3, 4, 5, 6, 7, 8, 9};
    o(a, 9);
}

Allbeert

Posted 11 years ago

Reputation: 489

2

Javascript (82)

a.sort(function(b,c){q=0;while(b|c){b%2?c%2?0:q++:c%2?q--:0;b>>=1;c>>=1}return q})

mowwwalker

Posted 11 years ago

Reputation: 161

2

Postscript, 126

Because list of values by which we sort is known beforehand and very limited (32), this task can be easily done even if there's no built-in for sorting, by picking matching values for 1..32. (Is it O(32n)? Probably).

Procedure expects array on stack and returns 'sorted' array.

/sort_by_bit_count {
    [ exch
    32 -1 1 {
        1 index
        {
            dup 2 32 string cvrs
            0 exch
            {48 sub add} forall
            2 index eq 
            {3 1 roll} {pop} ifelse
        } forall
        pop
    } for
    pop ]
} def

Or, ritually stripped of white space and readability:

/s{[exch 32 -1 1{1 index{dup 2 32 string cvrs 0 exch{48 sub add}forall 2 index eq{3 1 roll}{pop}ifelse}forall pop}for pop]}def

Then, if saved to bits.ps it can be used like this:

gs -q -dBATCH bits.ps -c '[(%stdin)(r)file 1000 string readline pop cvx exec] s =='
825 3944 11746 15342 15752 16375 19944 21826 28436 28943 32425
[16375 15342 32425 11746 19944 28436 28943 3944 15752 825 21826]

I think it effectively is the same as this Perl (there's yet no Perl here, too):

sub f{map{$i=$_;grep{$i==(()=(sprintf'%b',$_)=~/1/g)}@_}reverse 1..32}

Though that, unlike Postscript, can be easily golfed:

sub f{sort{j($b)-j($a)}@_}sub j{$_=sprintf'%b',@_;()=/1/g}

user2846289

Posted 11 years ago

Reputation: 1 541

Postscript! My first love, my favorite language of all time! It is nice to see another believer in the One True Programming Language. – AJMansfield – 11 years ago

2

Java 8: 144

static void main(String[]a){System.out.print(Stream.of(a).mapToInt(Integer::decode).sorted(Comparable.comparing(Integer::bitCount)).toArray());}

In expanded form:

static void main(String[] args){
    System.out.print(
        Stream.of(args).mapToInt(Integer::decode)
              .sorted(Comparable.comparing(Integer::bitCount))
              .toArray()
        );
}

As you can see, this works by converting the args to a Stream<String>, then converting to a Stream<Integer> with the Integer::decode function reference (shorter than parseInt or valueOf), and then sorting by Integer::bitCount, then putting it in an array, and printing it out.

Streams make everything easier.

AJMansfield

Posted 11 years ago

Reputation: 2 758

1

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

Shaggy

Posted 11 years ago

Reputation: 24 623

You need descending sort, not ascending. – Erik the Outgolfer – 8 years ago

Another alternative I believe would be ñ_¤è1 n. Don't think that'd be shorter combined with the other alternative, but you never know... – ETHproductions – 8 years ago

1

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]

Mohsin Raza

Posted 11 years ago

Reputation: 11

4Welcome 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 – caird coinheringaahing – 7 years ago

1

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!

Khuldraeseth na'Barya

Posted 11 years ago

Reputation: 2 608

1

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]

ბიმო

Posted 11 years ago

Reputation: 15 345

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. – Laikoni – 7 years ago

1

Kotlin, 57 44 bytes

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

Try it online!

snail_

Posted 11 years ago

Reputation: 1 982

1

K (ngn/k), 11 10 bytes

{x@>+/2\x}

Try it online!

ngn

Posted 11 years ago

Reputation: 11 449

1

MathGolf, 5 bytes

á{âΣ~

Try it online!

Explanation:

á{âΣ~
á{     Sort by the
    ~  Negative
   Σ   Digit sum
  â    Of the number converted to binary

Jo King

Posted 11 years ago

Reputation: 38 234

1

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

mazzy

Posted 11 years ago

Reputation: 4 832

1

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.

RobIII

Posted 11 years ago

Reputation: 397

instead of OrderByDescending you can use OrderBy and return -c in your lambda and save 9 chars. – Rik – 11 years ago

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 – RobIII – 11 years ago

1

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);
}        

Burnt Toast

Posted 11 years ago

Reputation: 111

1

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.

Ilmari Karonen

Posted 11 years ago

Reputation: 19 513

1

**

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.

Erti-Chris Eelmaa

Posted 11 years ago

Reputation: 111

1

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);

AShelly

Posted 11 years ago

Reputation: 4 281

similar to @albeert's answer, which I only saw after I completed this... – AShelly – 11 years ago

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. – ugoren – 11 years ago

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. – AShelly – 11 years ago

1

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]

RobAu

Posted 11 years ago

Reputation: 641

1

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.

ugoren

Posted 11 years ago

Reputation: 16 527

1

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;});

kuldeep.kamboj

Posted 11 years ago

Reputation: 625

I'm pretty sure you can save a few chars if you combine your return statements into one using ternary operator – mniip – 11 years ago

1

K, 14

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

.

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

tmartin

Posted 11 years ago

Reputation: 3 917

1

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

MT0

Posted 11 years ago

Reputation: 3 373

1

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

TalsMonkey

Posted 11 years ago

Reputation: 11

1

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();
        }
    }
}

Pharap

Posted 11 years ago

Reputation: 195

1

C# 95

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

PauloHDSousa

Posted 11 years ago

Reputation: 119

1

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);});}

Tim Seguine

Posted 11 years ago

Reputation: 824

requires gmp library, which is neither in the default built nor activated by default. (see http://php.net/manual/gmp.installation.php)

– Titus – 7 years ago

1

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.

Heiko Oberdiek

Posted 11 years ago

Reputation: 3 841

0

Jelly, 5 bytes (non-competing?)

BS$ÞṚ

Try it online!

Erik the Outgolfer

Posted 11 years ago

Reputation: 38 134

0

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.

Umbrella

Posted 11 years ago

Reputation: 867

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. – Titus – 7 years ago

0

Perl 5, 51 bytes

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

Try it online!

Xcali

Posted 11 years ago

Reputation: 7 671

0

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

hakr14

Posted 11 years ago

Reputation: 1 295

0

Python 2, 59 bytes

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

Try it online!

Khalil

Posted 11 years ago

Reputation: 49

Save 7 bytes by replacing reverse=1 with *-1 to get descending order. Try it online!

– Jack Brounstein – 6 years ago

0

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

mudkip201

Posted 11 years ago

Reputation: 833

0

K (oK), 19 bytes

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

Try it online!

Thaufeki

Posted 11 years ago

Reputation: 421

0

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
  • Elcan

    Posted 11 years ago

    Reputation: 913

    0

    Perl 6, 36 bytes

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

    Try it online!

    donaldh

    Posted 11 years ago

    Reputation: 131

    1Taking 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 – Jo King – 6 years ago

    1

    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!

    – Jo King – 6 years ago

    0

    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 
    

    RosLuP

    Posted 11 years ago

    Reputation: 3 036

    -1

    Python-40 bytes

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

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

    Maltysen

    Posted 11 years ago

    Reputation: 59

    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. – Steven Rumbalski – 11 years ago