title: All pair Bitwise OR sum
body: <p>Is there an algorithm to find Bit-wise OR sum or an array in linear time complexity?  </p>
  
  <p>Suppose if the array is {1,2,3} then all pair sum id 1|2 + 2|3 + 1|3 = 9.</p>
  
  <p>I can find all pair AND sum in O(n) using following algorithm.... How can I change this to get all pair OR sum. </p>
  
  <pre><code>int ans = 0;  // Initialize result
  
  // Traverse over all bits
  for (int i = 0; i &lt; 32; i++)
  {
      // Count number of elements with i'th bit set
      int k = 0;  // Initialize the count
      for (int j = 0; j &lt; n; j++)
          if ( (arr[j] &amp; (1 &lt;&lt; i)) )
              k++;
  
      // There are k set bits, means k(k-1)/2 pairs.
      // Every pair adds 2^i to the answer. Therefore,
      // we add "2^i * [k*(k-1)/2]" to the answer.
      ans += (1&lt;&lt;i) * (k*(k-1)/2);
  }
  </code></pre>
  
  <p>From here: <a href="http://www.geeksforgeeks.org/calculate-sum-of-bitwise-and-of-all-pairs/" rel="nofollow">http://www.geeksforgeeks.org/calculate-sum-of-bitwise-and-of-all-pairs/</a> </p>