The algorithm for computing the average of two signed binary streams
(section 4.3.1) theoretically requires (*n*+1) input digits to
generate *n* output digits, although in certain cases (when the
combination of input and carry digits allow the algorithm to determine
the required output digit without examining further input), only *n*
input digits will be required to generate *n* output digits. The
algorithm does not branch as it proceeds.