Bitwise less-than

Here and after we denote as $[a]_B$ the bitstring representation (i.e. sequence of shared bits correspondings to the binary decomposition of $a$). Our purpose is, for two bitstrings, to compute the bit $[a <_B b]$.

1. $[c_i] = [a_i] \oplus [b_i] = [a_i] + [b_i] - 2[a_i b_i]$
2. $[d_i] = \underset{s=i}{\overset{l-1}{\vee}}c_s$ // using prefix OR.
3. $[e_i] = [d_i] - [d_{i+1}]$ for $i < l$, $[e_{l-1}] = [d_{l-1}]$
4. $[a <_B b] = \underset{i=0}{\overset{l-1}\sum} [e_i b_i]$

It is easy to see by direct inspection: $d_i = 0$ up to (counting from the most significant bit, $l-1$) the first different bit, and from it equals $1$. Therefore, $e_i$ equals $1$ exactly in the the most significant different bit, and, hence, $\underset{i=0}{\overset{l-1}\sum} [e_i b_i]$ computes $0$ if this bit is $0$ in $b$, and $1$ if this bit is $1$ in $b$. The only remaining case is if $a = b$, in which case all the variables in these equations are $0$, as it should be.