Content deleted Content added
→Why (u | v) & 1 == 0 is the correct test: in other words. ↯ |
|||
Line 252:
Therefore, before ''u'' and ''v'' may both be halved and ''shift'' incremented, the [[Least significant bit|LSB]] of ''u'' must be zero, '''and''' the LSB of ''v'' must be zero. The test (in line 12 of the C code fragment) would look like this (avoiding the short-circuit operators for simplicity):
for (shift = 0; (u & 1) == 0 & (v & 1) == 0; ++shift) {
This is an expression of the form <math>\overline {A} \cdot \overline {B}</math>, which by [[de Morgan's laws]] can be rewritten as <math>\overline{A + B}</math>. In other words, ''Halve ''u'' and ''v'' and increment ''shift'' if
for (shift = 0; !((u & 1) == 1 | (v & 1) == 1); ++shift) {
As the only non-zero result of ''x'' <tt>& 1</tt> is 1, the equalities disappear:
| |||