<?php
function hsum($a, $b, $p) {
    $hs = $a ^ $b;
    $hp = $a & $b;
    $p <<= 1;
    return [$hs ^ $p, $hp | ($hs & $p)];
}
 
function hsum_rec($a, $b, $p) {
    list($s, $newp) = hsum($a, $b, $p);
    if ($newp == $p) {
        return [$s, $newp];
    } else {
        return hsum_rec($a, $b, $newp);
    }
}
 
function sum2($a, $b) {
    list($s, $p) = hsum_rec($a, $b, 0);
    return $s;
}
 
for($i = 0; $i < 1000; $i++) {
    for($j = 0; $j < 1000; $j++) {
        if(sum2($i,$j) != $i + $j) {
            $k = sum2($i,$j);
            echo "Error: $i, $j, $k\n";
        }
    }
}

PD9waHAKZnVuY3Rpb24gaHN1bSgkYSwgJGIsICRwKSB7CiAgICAkaHMgPSAkYSBeICRiOwogICAgJGhwID0gJGEgJiAkYjsKICAgICRwIDw8PSAxOwogICAgcmV0dXJuIFskaHMgXiAkcCwgJGhwIHwgKCRocyAmICRwKV07Cn0KCmZ1bmN0aW9uIGhzdW1fcmVjKCRhLCAkYiwgJHApIHsKICAgIGxpc3QoJHMsICRuZXdwKSA9IGhzdW0oJGEsICRiLCAkcCk7CiAgICBpZiAoJG5ld3AgPT0gJHApIHsKICAgICAgICByZXR1cm4gWyRzLCAkbmV3cF07CiAgICB9IGVsc2UgewogICAgICAgIHJldHVybiBoc3VtX3JlYygkYSwgJGIsICRuZXdwKTsKICAgIH0KfQoKZnVuY3Rpb24gc3VtMigkYSwgJGIpIHsKICAgIGxpc3QoJHMsICRwKSA9IGhzdW1fcmVjKCRhLCAkYiwgMCk7CiAgICByZXR1cm4gJHM7Cn0KCmZvcigkaSA9IDA7ICRpIDwgMTAwMDsgJGkrKykgewogICAgZm9yKCRqID0gMDsgJGogPCAxMDAwOyAkaisrKSB7CiAgICAgICAgaWYoc3VtMigkaSwkaikgIT0gJGkgKyAkaikgewogICAgICAgICAgICAkayA9IHN1bTIoJGksJGopOwogICAgICAgICAgICBlY2hvICJFcnJvcjogJGksICRqLCAka1xuIjsKICAgICAgICB9CiAgICB9Cn0=