Task — Hamming distance

You are given an array of integers, @ints. Write a script to return the sum of Hamming distances between all the pairs of the integers in the given array of integers. The Hamming distance between two integers is the number of places in which their binary representations differ.

Examples

Example 1
Input: @ints = (4, 14, 2)
Output: 6
Binary representation:
4  => 0100
14 => 1110
2  => 0010
HammingDistance(4, 14) + HammingDistance(4, 2) + 
   HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2
Input: @ints = (4, 14, 4)
Output: 4

Analysis

This boils down to two operations:

• Generate the pairs of @ints;
• Caculate the Hamming difference between each pair.

The first step is simply two nested loops over all the pairs from the set of @ints, and the second compares successive bits by and-ing the numbers with powers of 2.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-12-23
use utf8;     # Week 301 - task 2 - Hamming distance
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

hamming_distance(4, 14, 2);
hamming_distance(12, 13, 14);
hamming_distance(999, 999, 999);
hamming_distance(1023, 1024);
hamming_distance(7, 15);

sub hamming_distance {
    
    my (@ints, $from, $to, $b, $hamming);
    
    @ints = @_;
    
    # loop over pairs
    $hamming = 0;
    for $from (0 .. $#ints - 1) {
        for $to ($from + 1 .. $#ints) {
            
            # test for bit difference
            for ($b = 0; (2 ** $b <= $ints[$from]) or (2 ** $b <= $ints[$to]); $b ++) {
                $hamming ++ if (($ints[$from] & 2 ** $b) != ($ints[$to] & 2 ** $b));
            }       
        }
    }
    
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    say qq[Output: $hamming];
}

Output

Input:  @ints = (4, 14, 2)
Output: 6

Input:  @ints = (12, 13, 14)
Output: 4

Input:  @ints = (999, 999, 999)
Output: 0

Input:  @ints = (1023, 1024)
Output: 11

Input:  @ints = (7, 15)
Output: 1