Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><em>I'm taking the same assumptions: <code>+</code> and <code>*</code> are addition and multiplication with overflow ignored.</em></p> <h2>Look-up Table</h2> <p>This would probably be the fastest solution: Precompute the results, and store them in a look-up table. It would require 2<sup>16</sup> bytes of memory, or 64 kB.</p> <h2>Guess, Check, Refine Method</h2> <p>Presented in C-family-like pseudocode:</p> <pre><code>byte Solve(byte a, byte c){ byte guess = lastGuess = result = lastResult = 0; do { guess = lastGuess ^ lastResult ^ c; //see explanation below result = a^guess + (2*a)^guess + (4*a)^guess; lastGuess = guess; lastResult = result; } while (result != c); return guess; } </code></pre> <p>The idea of this algorithm is that it makes a guess at what <code>b</code> is, then plugs it into the formula for a tentative result, and checks it against <code>c</code>. Whatever bits in the guess caused the result to differ from <code>c</code> are changed. This corresponds to the XOR of the last guess, last result, and <code>c</code> (if this statement is a little bit of a jump, I encourage you draw a truth table, and not just take my word for it!).</p> <h2>Explanation</h2> <p>It works because changing a bit can only affect the results of that bit, and the more significant bits, but not lower bits (since when you do addition with pen and paper, the carries can propagate to the left). So in the worst case the algorithm takes 2 guesses to get the least significant bit correct, another guess for the 2nd lsb, another for the 3rd, etc. for a <strong>maximum of 9 guesses</strong> given any combination of <code>a</code> and <code>c</code>.</p> <p>Here's an example trace from my test program: </p> <pre><code>a: 00001100 c: 01100111 Guess: 01100111 Result: 01000001 Guess: 01000001 Result: 00010111 Guess: 00110001 Result: 01100111 b: 00110001 </code></pre>
    singulars
    1. This table or related slice is empty.
    1. PObitxor, solve equation, boolean logic
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDPenner1
    1. USDPenner1
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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