StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Since two adjacent numbers differ by a single binary bit, the result of XOR'ing two adjacent numbers together is very predictable:</p> <p><code>x</code> represents a bit whose value doesn't matter, but is the same as the corresponding <code>x</code> below/above it.</p> <pre><code> xxxxxxxxxxxxx1xxxxxxxxxxxx xor: xxxxxxxxxxxxx0xxxxxxxxxxxx __________________________________ 00000000000001000000000000 </code></pre> <p>This is true for ANY two adjacent numbers in the set you described.</p> <p>If you can find another pair of adjacent numbers, that differ by the same bit, they will ALSO XOR-out to the same value: <code>00000000000001000000000000</code></p> <p>And finally, XOR'ing those two values together will DEFINITELY give you a final answer of zero.</p> <hr> <p>So the algorithm you want looks like:</p> <ul> <li>Identify which bit is different between a number and its successor (bit 0-63)</li> <li>Find another pair of numbers that also differ by the same bit identified in step 1.</li> </ul> <p>Those are your 4 values.</p> <p>Note that if N > 64, then by the <a href="http://en.wikipedia.org/wiki/Pigeonhole_principle" rel="nofollow">pigeonhole priniciple</a>, there MUST be a solution like this.<br> If <code>N <= 64</code>, there <em>may</em> be a solution of this form, or a solution of another form, I didn't describe here.</p> <p><em>There are other constraints that could also find 4 numbers that xor together to 0.<br> But this is probably the simplest way to search for a solution.<br> Failing to find a solution this way does not guarantee that there is <strong>no</strong> solution, however.</em> </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