StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>EDIT: The constraints make the simple approach at the bottom invalid. I am adding the binary search function and the final comparison to detect the greater value:</p> <pre><code>unsigned long greater(unsigned long a, unsigned long b) { unsigned long x = a; unsigned long y = b; unsigned long t = a ^ b; if (t & 0xFFFF0000) { x >>= 16; y >>= 16; t >>= 16; } if (t & 0xFF00) { x >>= 8; y >>= 8; t >>= 8; } if (t & 0xf0) { x >>= 4; y >>= 4; t >>= 4; } if ( t & 0xc) { x >>= 2; y >>= 2; t >>= 2; } if ( t & 0x2) { x >>= 1; y >>= 1; t >>= 1; } return (x & 1) ? a : b; } </code></pre> <p>The idea is to start off with the most significant half of the word we are interested in and see if there are any set bits in there. If there are, then we don't need the least significant half, so we shift the unwanted bits away. If not, we do nothing (the half is zero anyway, so it won't get in the way). Since we cannot keep track of the shifted amount (it would require addition), we also shift the original values so that we can do the final <code>and</code> to determine the larger number. We repeat this process with half the size of the previous mask until we collapse the interesting bits into bit position 0.</p> <p>I didn't add the equal case in here on purpose.</p> <hr> <p>Old answer:</p> <p>The simplest method is probably the best for a homework. Once you've got the mismatching bit value, you start off with another mask at 0x80000000 (or whatever suitable max bit position for your word size), and keep right shifting this until you hit a bit that is set in your mismatch value. If your right shift ends up with 0, then the mismatch value is 0.</p> <p>I assume you already know the final step required to determine the larger number.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload