Task — Total xor

You are given an array of integers. Write a script to return the sum of total XOR for every subset of given array.

Examples

Example 1
Input: @ints = (1, 3)
Output: 6
Subset [1],    total XOR = 1
Subset [3],    total XOR = 3
Subset [1, 3], total XOR => 1 XOR 3 => 2
Sum of total XOR => 1 + 3 + 2 => 6

Example 2
Input: @ints = (5, 1, 6)
Output: 28
Subset [5],       total XOR = 5
Subset [1],       total XOR = 1
Subset [6],       total XOR = 6
Subset [5, 1],    total XOR => 5 XOR 1 => 4
Subset [5, 6],    total XOR => 5 XOR 6 => 3
Subset [1, 6],    total XOR => 1 XOR 6 => 7
Subset [5, 1, 6], total XOR => 5 XOR 1 XOR 6 => 2
Sum of total XOR => 5 + 1 + 6 + 4 + 3 + 7 + 2 => 28

Example 3
Input: @ints = (3, 4, 5, 6, 7, 8)
Output: 480

Analysis

Rather than reinvent the wheel, I have use my favourite perms and combs module, Algorithm::Combinatorics, to generate the subsets. All that is needed then is two nested loops, the outer one over all the subsets and the inner one doing the XOR operation using Perl's ^ operator.

On my computer this gives an answer within a few seconds for an array of up to about 18 elements.

For any array of n random elements in a range of 1 to 2**n - 1, the result of sum has a maximum value, and that maximum value will be met by a large proportion of such arrays. For example, if n == 6 and the elements are in the range 1 .. 15 the maximum is 480 and you can see from my choice of examples that this is achieved for a range of input values. Only when I deliberately chose only even numbers did the total reduce by 32 to 448.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2025-06-02
use utf8;     # Week 324 - task 2 - Total xor
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;
use Algorithm::Combinatorics 'subsets';

total_xor(5, 1, 6);
total_xor(3, 4, 5, 6, 7, 8);
total_xor(1, 3, 6, 8, 9, 15);
total_xor(7, 8, 9, 10, 11, 12);
total_xor(2, 4, 6, 8, 10, 12);

# bigger example
my @array;
push @array, int(rand(2000)) for 0 .. 16;
total_xor(@array);

sub total_xor {
    
    my (@array, $total, $iter, $subtotal, $s, $i);
    
    # initialise
    @array = @_;
    $total = 0;
    $iter = subsets(\@array);
    
    # iterate over subsets
    while ($s = $iter->next) {
        $subtotal = 0;
        $subtotal = $subtotal ^ $_ for @$s;
        $total += $subtotal;
    }
    
    # report
    say qq[\nInput:  \@array = (] . join(', ', @array) . ')';
    say qq[Output: $total];
}

Output

Input:  @array = (5, 1, 6)
Output: 28

Input:  @array = (3, 4, 5, 6, 7, 8)
Output: 480

Input:  @array = (1, 3, 6, 8, 9, 15)
Output: 480

Input:  @array = (7, 8, 9, 10, 11, 12)
Output: 480

Input:  @array = (2, 4, 6, 8, 10, 12)
Output: 448

Input:  @array = (1284, 851, 1990, 513, 453, 1738, 1882, 1133, 1250, 839, 815, 749, 924, 1669, 60, 1555, 215)
Output: 134152192