This OR That

Consider for a moment that all the inputs were just of 1 bit. Then, the OR of any two values is 0 iff both of them are 0. Otherwise, the OR is 1. So, the sum of the ORs is basically $\frac{n(n-1)}{2} - \frac{c(c-1)}{2}$ where $c$ is the number of 0s in the input.

Using this idea, we can solve the original problem bitwise. Consider the $i^{th}$ bit of all the inputs. Every pair whose bitwise OR produces a 1 adds $2^i$ to the total sum. So, in essence, our answer is $\sum_{i}{2^i \left ( \frac{n(n-1)}{2} - \frac{c[i](c[i]-1)}{2} \right )}$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>

int count[30]; //count[i] elements have the ith bit unset

int main(){
    const int N = 100000;


    for (int iii=0; iii < N; iii++)
    {
        int x;
        std::cin >> x;
        for (int i = 0; i < 30; i++)
            if (! (x & (1 << i))) // if the ith bit of the current number is unset
                count[i]++;
    }

    long long ans = 0;
    long long possible_pairs = static_cast<long long>(N)*(N-1)/2; //this is the maximum number of pairs that could produce all trues
    for (int i = 0; i < 30; i++)
        ans += ((1LL) << (i)) * (possible_pairs - (count[i]*static_cast<long long>(count[i]-1))/2);

    std::cout << ans;

    return 0;

}

Inspiration

Here is my solution in Java. It is similar to Agnishom's solution. If $n$ is the total number of integers, and $a_i$ is the number of these integers for which bit $\#i$ is set, then we have

• $\tfrac12 a_i\cdot (a_i-1)$ pairs in which both integers have this bit = 1;

• $n - a_i$ pairs in which only one integer has this bit = 1.

Adding these together gives the number of terms (in my code called pairs ) where this bit contributes to the sum.

Note: ipf is a BufferedReader opened to read the input file.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

final int nB = 30;
long a[] = new long[nB];
for (int i = 0; i < nB; i++) a[i] = 0;

String data[] = ipf.readLine().split(" ");
int nI = data.length;

for (int j = 0; j < nI; j++) {
    long val = Long.parseLong(data[j]);

    long bit = 1;
    for (int i = 0; i < nB; i++, bit <<= 1)
        if ((val & bit) != 0) a[i]++;       
}

long bit = 1;
long result = 0;

for (int i = 0; i < nB; i++, bit <<= 1)
{
    long pairs = a[i]*(a[i]-1)/2 + a[i]*(nI-a[i]);    
    result += bit * pairs;
}

System.out.println(result);

In the bitwise OR each bit is independent.
So we count how many numbers have the bit set in position 1, 2, ... and so on.
The same logic of Arjen Vreugdenhil solution,but in python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Happy Birthday
f=open('or.txt')
content=f.read()
data = [int(x) for x in content.split()]
bitscount = [sum((x >> k)&1 for x in data) for k in range(32)]

result = sum(2**k*(bitscount[k]*(200000 - 1 - bitscount[k]))//2 for k in range(32))

print(result)

# Output 
# 3828434936185820379