Throughout this post, the variables `A`, `B`, and `R` are used, with R defined as `R = A + B`, and `A ≤ B`. Arithmetic in this post is unsigned and modulo 2^{k}. Note that `A ≤ B` is not a restriction on the input, it is a choice to label the smaller input as `A` and the larger input as `B`. Addition is commutative, so this choice can be made without loss of generality.

`R < A || R ≥ B`

The sum is less than A *iff* the addition wraps (1), otherwise it has to be at least B (2).

`B`cannot be so high that the addition can wrap all the way up to or past`A`. To make`A + B`add up to`A`,`B`would have had to be 2^{k}, which is one beyond the maximum value it can be.`R = A`is possible only if`B`is zero, in which case`R ≥ B`holds instead.- Since
`A`is at least zero, in the absence of wrapping there is no way to reduce the value below the inputs.

Perhaps that all looks obvious, but this has a useful application: if the carry-out of the addition is not available, it can be computed via `carry = (x + y) < x`, which is a relatively well-known trick. It does not matter which of `x` or `y` is the smaller or larger input, the sum cannot fall within the "forbidden zone" between them. The occasionally seen `carry = (x + y) < max(x, y)` adds an unnecessary complication.

`R < (A & B) || R ≥ (A | B)`

This is a stronger statement, because `A & B` is usually smaller than `A` and `A | B` is usually greater than `B`.

If no wrapping occurs, then `R ≥ (A | B)`. This can be seen for example by splitting the addition into a XOR and adding the carries separately, `(A + B) = (A ^ B) + (A & B) * 2`, while bitwise OR can be decomposed similarly into `(A | B) = (A ^ B) + (A & B)`^{(see below)}. Since there is no wrapping (by assumption), `(A & B) * 2 ≥ (A & B)` and therefore `(A + B) ≥ (A | B)`. Or, with less algebra: addition sometimes produces a zero where the bitwise OR produces a one, but then addition compensates doubly for it by carrying into the next position.

For the case in which wrapping occurs I will take a bit-by-bit view. In order to wrap, the carry out of bit `k-1` must be 1. In order for the sum to be greater than or equal to `A & B`, bit `k-1` of the sum must be greater than or equal to bit `k-1` of `A & B`. That combination means that the carry *into* bit `k-1` of the sum must have been 1 as well. Furthermore, bit `k-1` of the sum can't be greater than bit `k-1` of `A & B`, at most it can be equal, which means bit `k-2` must be examined as well. The same argument applies to bit `k-2` and so on, until finally for the least-significant bit it becomes impossible for it to be carried into, so the whole thing falls down: by contradiction, `A + B` must be less than `A & B` when the sum wraps.

## What about `(A | B) = (A ^ B) + (A & B)` though?

The more obvious version is `(A | B) = (A ^ B) | (A & B)`, compensating for the bits reset by the XOR by ORing exactly those bits back in. Adding them back in also works, because the set bits in `A ^ B` and `A & B` are *disjoint*: a bit being set in the XOR means that exactly one of the input bits was set, which makes their AND zero.