Content deleted Content added
m →Why (u | v) & 1 == 0 is the correct test: using & | not && || |
→Why (u | v) & 1 == 0 is the correct test: math for de Morgan |
||
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>. Notice the Boolean negation <tt>!</tt> inserted at the front:
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:
for (shift = 0; !((u & 1) | (v & 1)); ++shift) {
<tt>&</tt> is [[Distributive property|distributive]] over <tt>|</tt> so the two <tt>& 1</tt> operations can be combined:
for (shift = 0; !(((u) | (v)) & 1); ++shift) {
Comparing with zero is equivalent to the Boolean negation. After removing redundant parentheses we obtain the test as originally written:
for (shift = 0; ((u | v) & 1) == 0; ++shift) {
As a further test, the code fragment as it stood (comprising <tt>((u & v) & 1) == 0</tt>) was compiled, and <tt>gcd(1,2)</tt> was called. As ''u'' and ''v'' have no two bits set in the same column, the test never became false and the code hung in a loop between lines 12–15. ''u'' <tt>|</tt> ''v'' also corresponds to the ARM code (<tt>ORRS</tt>) which has been tested. – [[User:Regregex|Regregex]] ([[User talk:Regregex|talk]]) 16:28, 11 July 2011 (UTC)
| |||