The weekly challenge 271 - Task 2: Sort by 1 bits

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-271/#TASK2
 3 #
 4 # Task 2: Sort by 1 bits
 5 # ======================
 6 #
 7 # You are give an array of integers, @ints.
 8 #
 9 # Write a script to sort the integers in ascending order by the number of 1
10 # bits in their binary representation. In case more than one integers have the
11 # same number of 1 bits then sort them in ascending order.
12 #
13 ## Example 1
14 ##
15 ## Input: @ints = (0, 1, 2, 3, 4, 5, 6, 7, 8)
16 ## Output: (0, 1, 2, 4, 8, 3, 5, 6, 7)
17 ##
18 ## 0 = 0 one bits
19 ## 1 = 1 one bits
20 ## 2 = 1 one bits
21 ## 4 = 1 one bits
22 ## 8 = 1 one bits
23 ## 3 = 2 one bits
24 ## 5 = 2 one bits
25 ## 6 = 2 one bits
26 ## 7 = 3 one bits
27 #
28 ## Example 2
29 ##
30 ## Input: @ints = (1024, 512, 256, 128, 64)
31 ## Output: (64, 128, 256, 512, 1024)
32 ##
33 ## All integers in the given array have one 1-bits, so just sort them in ascending order.
34 #
35 ############################################################
36 ##
37 ## discussion
38 ##
39 ############################################################
40 #
41 # This one comes down to a slightly complex sort.
42 # We calculate the bit sum of a number (number of 1 bits) and sort
43 # by that - if the same, we sort by the numbers themselves.
44 
45 use strict;
46 use warnings;
47 
48 sort_by_one_bits(0, 1, 2, 3, 4, 5, 6, 7, 8);
49 sort_by_one_bits(1024, 512, 256, 128, 64);
50 
51 sub sort_by_one_bits {
52    my @ints = @_;
53    print "Input: (", join(", ", @ints), ")\n";
54    print "Output: (", join(", ", sort { bit_sum($a) <=> bit_sum($b) || $a <=> $b } @ints), ")\n";
55 }
56 
57 sub bit_sum {
58    my $i = shift;
59    my $bits = sprintf("%b", $i);
60    my $sum = 0;
61    foreach my $bit (split //, $bits) {
62       $sum += $bit;
63    }
64    return $sum;
65 }