Task — Decode xor

You are given an encoded array and an initial integer. Write a script to find the original array that produced the given encoded array. It was encoded such that encoded[i] = orig[i] XOR orig[i + 1].

Examples

Example 1
Input: @encoded = (1, 2, 3), $initial = 1
Output: (1, 0, 2, 1)
Encoded array created like below, if the original array 
   was (1, 0, 2, 1)
$encoded[0] = (1 xor 0) = 1
$encoded[1] = (0 xor 2) = 2
$encoded[2] = (2 xor 1) = 3

Example 2
Input: @encoded = (6, 2, 7, 3), $initial = 4
Output: (4, 2, 0, 7, 4)

Analysis

Oh dear, I thought, caculations involving bitwise operations are always a bit tricky in Perl (and other languages) because the 'not' operator often doesn't do what you want. For example, we might think:

6 decimal is 110 binary
so not 6 is 001 binary
which is 1 decimal

... but Perl doesn't work like that. It thinks:

6 decimal is 00000000000000000000000000000110 binary
so not 6 is 11111111111111111111111111111001 binary
which is a humongous decimal number.

So to the challenge. The essence of this is that we have an equation
$a xor $b = $e where we know $a and $e and need to calculate $b.

My first thought was simply to loop $b over say 1 to 1000 and find the $a xor $b which equals $e. For even quite large values of $a and $e that works in a fraction of a second and - of course - gives the correct answer.

But there is a better way. If, as we know, $a xor $b = $e then it is also true that $a xor $e = $b, or to put it differently
$b = $a xor $e. So all we need to do is apply this to each encoded number $e, setting $a = $b after each one.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2025-02-10
use utf8;     # Week 308 - task 2 - Decode xor
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

decode_xor([1, 2, 3], 1);
decode_xor([6, 2, 7, 3], 4);
decode_xor([47, 21, 33, 8], 4);

sub decode_xor {
    
    my (@e, $a, $b, $e, @result);
    
    # inputs
    @e = @{$_[0]};
    $a = $_[1];
    $result[0] = $a;
    
    # loop over values of @encoded
    for $e (@e) {
        $b = $e ^ $a;
        push @result, $b;
        $a = $b;
    }
    
    say qq[\nInput:  \@encoded = (] . join(', ', @e) . qq[), \$integer = $_[1]];
    say qq[Output: (] . join(', ', @result) . ')';
}

Output

Input:  @encoded = (1, 2, 3), $integer = 1
Output: (1, 0, 2, 1)

Input:  @encoded = (6, 2, 7, 3), $integer = 4
Output: (4, 2, 0, 7, 4)

Input:  @encoded = (47, 21, 33, 8), $integer = 4
Output: (4, 43, 62, 31, 23)