Task — Sort by 1 bits

You are give an array of integers, @ints. Write a script to sort the integers in ascending order by the number of 1 bits in their binary representation. In case more than one integer has the same number of 1 bits then sort them in ascending order.

Examples

Example 1
Input: @ints = (0, 1, 2, 3, 4, 5, 6, 7, 8)
Output: (0, 1, 2, 4, 8, 3, 5, 6, 7)
0 = 0 one bits
1 = 1 one bits
2 = 1 one bits
4 = 1 one bits
8 = 1 one bits
3 = 2 one bits
5 = 2 one bits
6 = 2 one bits
7 = 3 one bits

Example 2
Input: @ints = (1024, 512, 256, 128, 64)
Output: (64, 128, 256, 512, 1024)
All integers in the given array have one 1-bits, so just 
sort them in ascending order.

Analysis

This task breaks down into two parts: determine the number of 1-bits in each of the supplied @ints, and sort them (a) by the number of bits and within that (b) in ascending order.

I counted the bits by bitwise ANDing each number with 1, 2, 4, 8 ... and stopping when that sequence exceeded the number being examined.

Perl doesn't have a built-in multi-key sort so the next step could be two nested sorts: the outer one over number of 1-bits and the inner over the number in question. However, I often find it convenient to combine two sorts into one by concatenating the sort keys and using the result as the index of a hash. The overall result can then simply be obtained by a sort keys loop over the hash.

However, there is a slight complication here in that the statement of the task doesn't exclude the possibility of repeats among the numbers in @ints, and though the examples show only lists of unique integers we should probably allow for repeats. That's a slight problem for my hash solution, because both instances of the repeated number would give rise to the same hash key, so that only the unique values would be shown in the result.

So what I have done is to add a third elemnet to the hash key, which is the index of the integer within @ints. Its value is immaterial, but what matters is that it is unique to each element of @ints.

Hash keys sort as strings, so I constructed the hash key as:

• number of bits, formatted as a 2-digit zero-padded string
• the original number, formatted as a 15-digit zero-padded string
• the index of the number within @ints formatted as a 3-digit zero-padded string

For example, the 7 in example 1 will generate a hash key of 03000000000000007007, because it contains 3 1-bits, its value is 7 and it is $ints[7]. And you will see, in particular in my 4th example output, that this does indeed give the desired result when values - eg 1, 2 and 16 - are duplicated in @ints.

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2022-07-07
# PWC 172 task 2

use v5.28;
use strict;
use warnings;
use utf8;
binmode(STDOUT, ':utf8');

my (@tests, $test, @random, @sorted, $count, $median, $first_quartile, $third_quartile);

@tests = ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
    [8, 42, -3, 0, 99, 66, 21, 100], 
    [1, 1, 1, 1, 1, 1, 1],
    [1, 2, 3, 4, 5, 6, 7, 8, 1000]);
push @random, int(rand(101)) for 0 .. 99;
push @tests, \@random;

# loop over tests
for $test (@tests) {
    
    # sort numerically and count
    @sorted = sort  {$a <=> $b} @$test;
    $count = scalar @sorted;

    # determine value at a position (which might not be integral)
    $median = value(($count - 1) / 2);
    $first_quartile = value(($count - 1) / 4);
    $third_quartile = value(3 * ($count - 1) / 4);
    
    printf(qq[\nInput: \@array = (%s)\n], join(', ', @$test));
    say qq[Output: minimum: $sorted[0], first quartile: $first_quartile, median: $median, ] .
        qq[third quartile: $third_quartile, maximum: $sorted[-1]];  
}

sub value {
    
    my ($position, $lower, $upper, $fraction);
    
    # returns the value at the given position
    # if position is non-integral returns the weighted intermediate value
    $position = shift;
    
    # integral position
    return $sorted[$position] if $position == int($position);
    
    # find intergral position below and above given position and 
    # calculate weighted intermediate value
    $lower = int($position);
    $upper = $lower + 1;
    $fraction = $position - $lower;
    return $sorted[$lower] * (1 - $fraction) + $sorted[$upper] * $fraction;
}   

Output

Input:  @ints = (0, 1, 2, 3, 4, 5, 6, 7, 8)
Output:         (0, 1, 2, 4, 8, 3, 5, 6, 7)

Input:  @ints = (1024, 512, 256, 128, 64)
Output:         (64, 128, 256, 512, 1024)

Input:  @ints = (1, 3, 7, 15, 31, 63, 127, 255, 511, 1023,
1048575, 987654321)
Output:         (1, 3, 7, 15, 31, 63, 127, 255, 511, 1023,
987654321, 1048575)

Input:  @ints = (48, 19, 14, 26, 18, 39, 32, 18, 45, 42,
16, 36, 11, 38, 39, 30, 16, 45, 1, 44, 42, 0, 2, 16, 49,
48, 29, 12, 22, 31, 26, 5, 25, 36, 13, 9, 43, 35, 20, 17,
27, 29, 26, 37, 22, 39, 47, 17, 1, 37, 2)
Output:         (0, 1, 1, 2, 2, 16, 16, 16, 32, 5, 9, 12,
17, 17, 18, 18, 20, 36, 36, 48, 48, 11, 13, 14, 19, 22,
22, 25, 26, 26, 26, 35, 37, 37, 38, 42, 42, 44, 49, 27,
29, 29, 30, 39, 39, 39, 43, 45, 45, 31, 47)