Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Think of the numbers arranged in a Nx32 matrix, where each row represents a number in array and each column represents i'th bits of all the numbers. Now, effects of XOR operation are confined within a column. Therefore, we can separate each column, calculate the XOR-sum for that column and add it to the result.</p> <p><strong>I have separated a column. How to calculate XOR-sum within this column?</strong></p> <p>For this purpose, we count the number of 1 in this column. Let <code>c</code> denote the number of 1 in a column. Then, number of 0 will be <code>N - c</code>. To produce 1 in column result (0s have no effect on final result), for each 1 from <code>c</code>, we can take a 0 from <code>N - c</code>, or take no 0 at all. Therefore, there are <code>N - c + 1</code> ways for each 1 to produce 1 after XOR operation. As there are <code>c</code> 1s, Total number of 1 after XOR operation is <code>c * (N - c + 1)</code>.</p> <p>Each column contributes differently to the final result with respect to there position <code>i</code>. Therefore, multiply column-result with <code>2^i</code> (<code>1 &lt;&lt; i</code>) and add this to final result.</p> <ul> <li><code>for (int i=0, p=1; i&lt;30; i++, p&lt;&lt;=1)</code><br> This loop separates the columns. It also makes <code>p = 1 &lt;&lt; i</code>.</li> <li><code>if (A[j]&amp;p) c++;</code><br> This line counts number of 1 in a column.</li> <li><code>ret+=(long long)c*(N-c+1)*p;</code><br> This elevates the column-result with respect to column position and add this to final result. Remember that, <code>p = 1 &lt;&lt; i</code> (= 2^i).</li> </ul> <p><em>CONFESSION: I only explained what is done in the code. I have no proof that this will cover all the sub-arrays.</em></p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm to add sum of every possible xor-sum sub-array
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USasif
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POAlgorithm to add sum of every possible xor-sum sub-array
      singulars
      1. PTQuestion
    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