Carrying Is a 2-Cocycle [pdf]

Carry is also a monoid. Consider addition of two binary numbers. If the two digits are zero, then the output carry is zero no matter the input carry. If the two digits are one, then the output carry is one no matter the input carry. And if one is a zero and the other a one, then the output carry is the input carry. Call these values 0, 1, and X respectively.

Now consider a binary operator combining two such values. It is associative and has X as an identity element, thus is a monoid:

    \   0 1 X
      +------
    0 | 0 0 0
    1 | 1 1 1
    X | 0 1 X

Now you can express the carry output of bit i as the inclusive scan (prefix sum) of these values from 0 to i. Because it's a monoid, you can implement it efficiently in parallel. There's a nontrivial literature in digital electronics exploiting this basic fact.

Of course, to me everything is a monoid (including rendering vector graphics paths), so it should come as no surprise that I see things this way.

Wish I saw this write-up in like 2009. The terminology in Cohomology was pretty opaque to me until I (much later) learned the concepts via a backwards mapping from learning deeper applications of algebraic geometry. I would have learned that much easier if I understood this easier.

cf https://news.ycombinator.com/item?id=34884628