Maximum xor

You are given an array of integers. Write a script to find the highest value obtained by XORing any two distinct members of the array.

Examples

Example 1
Input: @array = (1,2,3,4,5,6,7)
Output: 7
The maximum result of 1 xor 6 = 7.

Example 2
Input: @array = (2,4,1,3)
Output: 7
The maximum result of 4 xor 3 = 7.

Example 3
Input: @array = (10,5,7,12,8)
Output: 15
The maximum result of 10 xor 5 = 15.

Analysis

The first thing to note - and I had to look it up - is that Perl does have an xor operator - ^ - so the obvious way to do the task is by using two nested loops:

for $i (0 .. $count - 2) {
	for $j ($i + 1 .. $count - 1) {
		... calculate $array[$i] ^ $array[$j] 
		    and keep track of the maximum value

But is this the best way? Suppose we look for the largest number in @array and count its binary digits. For example, if the largest number is 25, that's 11001 in binary, which is 5 binary digits. Clearly the xor of any two numbers in @array cannot exceed 11111, which is 31 or 2**5 - 1, because if the largest number in the array has 5 binary digits, no other number can have a sixth. So in the inner loop we can stop as soon as we hit a pair of numbers which xor to 31: we know no other pair can exceed that.

In an arbitrary array there may of course be several pairs which xor to the maximum. In Mohammad's third example - 10, 5, 7, 12, 8 - he shows 10 ^ 5 = 15, but equally 7 ^ 8 = 15, so I think we can take it that showing a single pair meets the conditions stated.

This saving is significant unless the numbers in @array are quite sparse. For example, with an array of 20 random numbers in the range 0 to 63 (6 binary digits) a pair which xor to 63 occurs in about 90% of trials. Increasing the range to 0 to 127 still finds a pair that xors to 127 in ~70% of cases.

In fact, it can easily be shown that if the largest number in @array consists of n binary digits, then any @array containing at least n/2 + 1 unique numbers will contain a pair which xor to the maximum, ie 2**n - 1. So, for example, any 9 numbers in the range 0..15 will contain a pair which xors to 15.

Task analysis of both tasks is well drafted, specially the second one. Just loved it. Thanks.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith - 2023-02-20

use v5.28;
use utf8;
use warnings;
use List::Uniq ':all';

# Task: You are given an array of integers. Write a script to find the highest value obtained 
# by XORing any two distinct members of the array.

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

my ($j, @test);

max_xor(1, 2, 3, 4, 5, 6, 7);
max_xor(2, 4, 1, 3);
max_xor(10, 5, 7, 12, 8);
max_xor(21, 25);
max_xor(32, 32, 32, 32);

for $j (1 .. 20) {
    @test[$j - 1] = int(rand(126)) + 1;
}
max_xor(@test);

sub max_xor {
    
    my ($count, $i, $j, $max, $xor, $result, @array, $largest, $limit);
    
    @array = @_;
    $count = scalar @array;

    # find the largest number in the array
    $largest = 0;
    for $j (@array) {
        $largest = $j if $j > $largest;
    }
    
    # find the largest possible xor
    for $j (1 .. 31) {
        next unless 2 ** $j > $largest;
        $limit = 2 ** $j - 1;
        last;
    }

    # now scan for the largest xor
    $max = -1;
    if ($count >= 2) {
        SCAN: for $i (0 .. $count - 2) {
            for $j ($i + 1 .. $count - 1) {
                $xor = $_[$i] ^ $_[$j];
                if ($xor > $max) {
                    $result = qq[$array[$i] xor $array[$j] = $xor];
                    $max = $xor;
                    last SCAN if $max == $limit;
                }
            }
        }
        say qq[\nInput:  \@array = (] . join(', ', @_) . ')' . qq[\nOutput: $result];
    } else {
        say 'Array must contan at least 2 elements.'
    }
}

23 lines of code

Output from script

Input:  @array = (1, 2, 3, 4, 5, 6, 7)
Output: 1 xor 6 = 7

Input:  @array = (2, 4, 1, 3)
Output: 4 xor 3 = 7

Input:  @array = (10, 5, 7, 12, 8)
Output: 10 xor 5 = 15

Input:  @array = (21, 25)
Output: 21 xor 25 = 12

Input:  @array = (32, 32, 32, 32)
Output: 32 xor 32 = 0

Input:  @array = (75, 71, 95, 36, 76, 54, 51, 74, 93, 72, 27, 89, 120, 98, 96, 21, 13, 60, 104, 43)
Output: 76 xor 51 = 127