Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Let's first search for an abstract problem definition: You have a bitvector type with a length of 8 bit, which represents a combination of your 8 input signals. For each signal, you have a bitvector value like <code>10000000</code> (first signal) or <code>00100000</code> (third signal). These values are given. You want to generate the following values (I left out the trivial ones):</p> <pre><code>r[0] = 10100000 r[1] = 01010000 r[2] = 00101000 r[5] = 00010100 r[8] = 01011010 r[9] = 00111010 r[10] = 00011100 r[11] = 00001101 r[12] = 00100100 r[14] = 01111110 r[15] = 00111100 </code></pre> <p>We now want to search for the minimum of combinations (executions of <code>XOR</code>) to generate these values. This is an optimization problem. I won't do a complete proof for the lowest amount of <code>XOR</code> executions here, but this is what I get:</p> <pre><code>int i1 = s02 ^ s04; // 01010000 int i2 = s03 ^ s05; // 00101000 int i3 = s04 ^ s06; // 00010100 int i4 = s05 ^ s07; // 00001010 int i5 = s03 ^ s06; // 00100100 int i6 = i1 ^ i4; // 01011010 int i7 = i2 ^ i3; // 00111100 int i8 = s06 ^ s07; // 00000110 r[0] = s01 ^ s03; r[1] = i1; r[2] = i2; r[5] = i3; r[8] = i6; r[9] = i7 ^ i8; r[10] = i3 ^ s05; r[11] = i4 ^ i8 ^ s08; r[12] = i5; r[14] = i6 ^ i5; r[15] = i7; </code></pre> <p>14 <code>XOR</code>s.</p> <p>To formulate a general algorithm: You start with a Set <code>S={10000000, 01000000, ... , 00000001}</code>. You need a weighting function that tells you the value of your set. Define this as: The number of <code>XOR</code>s needed to calculate all goal values from values in <code>S</code> without storing additional temporary values <strong>plus</strong> the number of values in <code>S</code> <strong>minus</strong> 8 (initial values). The first part of the weighting function can be implemented with brute force (find all possible combinations for a goal value that use each value in <code>S</code> at most once, choose the one with the least <code>XOR</code> executions).</p> <p>To optimize the value of your weighting function, you combine two values from <code>S</code> with <code>XOR</code> and add them to <code>S</code>, giving <code>S1</code>. Choose those two values which grant the lowest new value of the weighting function (again, this can be determined by brute force). S1 now has one more value (which will be a temporary value like the <code>i</code> values in my solution). To create this value, one <code>XOR</code> is needed (therefore, the weighting function counts the number of values in <code>S</code>).</p> <p>Continue this step until you don't find any new value to add to <code>S</code> that reduces the value of the weighting function. The resulting set contains the initial values plus all temporary values you have to calculate. The steps you took will tell you how to calculate the immediate values.</p> <p>This is a greedy algorithm. It doesn't necessarily find the minimum number of <code>XOR</code>s, but shows you an easy way to at least get a <em>good</em> solution. It might be that the algorithm actually always finds the best solution, but this would have to be proven. If you want to be absolutely sure, you can do a complete traversal of all possible steps that reduce the value of the weighting function, starting with the initial <code>S</code> values. This would be a tree traversal, and the tree will be finite - as the value cannot drop below 0 - so it's definitely solvable.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind the lowest combination of XOR
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USflyx
    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. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis inspired me :-) I will now try out something. Thanks!
      singulars
      1. PO
      1. USatom
 

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