<?php

/**
 * negBin to decimal
 * for tests
 */
function toDec($subBin = []) {
  $res = 0;
  foreach ($subBin as $k => $val) {
    $res += $val * pow(-2, $k);
  }

  return $res;
}

/**
 * main solution
 * negBin addition
 */
function solution($A, $B) {
  $len = max(count($A), count($B));
  $res = [];

  for ($i=0; $i < $len + 2; $i++) {
    if (empty($res[$i])) $res[$i] = 0;
    if (empty($res[$i+1])) $res[$i+1] = 0;
    if (empty($res[$i+2])) $res[$i+2] = 0;

    if (empty($A[$i])) $A[$i] = 0;
    if (empty($B[$i])) $B[$i] = 0;

    $res[$i] += $A[$i] + $B[$i];

    if ($res[$i] >= 2) {
      if ($res[$i + 1] && $res[$i] / $res[$i + 1] == 2) {
        $res[$i] = $res[$i + 1] = 0;
      } else {
        $res[$i + 1] += floor($res[$i] / 2);
        $res[$i + 2] += floor($res[$i] / 2);
        $res[$i] = $res[$i] % 2;
      }
    }
  }

  $cnt = count($res);
  for ($c = $cnt - 1; $c >= 0; $c--) {
    if ($res[$c] == 0) {
      unset($res[$c]);
    } else {
      break;
    }
  }

  $cnt = count($res);
  if($res[$cnt - 1] != 0 && $res[$cnt - 2]/$res[$cnt - 1] == 2) {
    array_pop($res);
    array_pop($res);
  }

  return $res;
}


// tests
$tests = [
  [
    'n1' => [0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1],
    'n2' => [0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
    'res' => [0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1]
  ],
  [
    'n1' => [1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1],
    'n2' => [0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
    'res' => [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1]
  ],
  [
    'n1' => [0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1],
    'n2' => [0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1],
    'res' => [0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1]
  ],
  [
    'n1' => [0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1],
    'n2' => [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
    'res' => [0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1]
  ],
];

foreach ($tests as $k => $test) {
  $res = solution($test['n1'], $test['n2']);

  if ($res == $test['res']) {
    echo 'test case ' . $k . " - Passed!\n";
  } else {
    echo 'test case ' . $k . " - ERROR!\n";
  }

  echo toDec($test['n1']) . ' + ' . toDec($test['n2']) . '  (Expected:' . toDec($res) . ")\n" .
    'solution result: ' . implode('', $res) . "\n" .
    'test result:     ' . implode('', $test['res']) . "\n\n";
}