CODEWITHSUNDEEP
bit-manipulationbitbitwise-or
Rezwan Arefin
Rezwan Arefin

Reputation: 176

All pair Bitwise OR sum

Is there an algorithm to find Bit-wise OR sum or an array in linear time complexity?

Suppose if the array is {1,2,3} then all pair sum id 1|2 + 2|3 + 1|3 = 9.

I can find all pair AND sum in O(n) using following algorithm.... How can I change this to get all pair OR sum. 

int ans = 0;  // Initialize result

// Traverse over all bits
for (int i = 0; i < 32; i++)
{
    // Count number of elements with i'th bit set
    int k = 0;  // Initialize the count
    for (int j = 0; j < n; j++)
        if ( (arr[j] & (1 << 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<<i) * (k*(k-1)/2);
}

From here: http://www.geeksforgeeks.org/calculate-sum-of-bitwise-and-of-all-pairs/

Upvotes: 2

Views: 5007

Answers (1)

bpachev
bpachev

Reputation: 2212

You can do it in linear time. The idea is as follows:

  1. For each bit position, record the number of entries in your array that have that bit set to 1. In your example, you have 2 entries (1 and 3) with the ones bit set, and 2 entries with the two's bit set (2 and 3).

  2. For each number, compute the sum of the number's bitwise OR with all other numbers in the array by looking at each bit individually and using your cached sums. For example, consider the sum 1|1 + 1|2 + 1|3 = 1 + 3 + 3 = 7.

    Because 1's last bit is 1, the result of a bitwise or with 1 will have the last bit set to 1. Thus, all three of the numbers 1|1, 1|2, and 1|3 will have last bit equal to 1. Two of those numbers have the two's bit set to 1, which is precisely the number of elements which have the two's bit set to 1. By grouping the bits together, we can obtain the sum 3*1 (three ones bits) + 2*2 (two two's bits) = 7.

  3. Repeating this procedure for each element lets you compute the sum of all bitwise ors for all ordered pairs of elements in the array. So in your example, 1|2 and 2|1 will be computed, as will 1|1. So you'll have to subtract off all cases like 1|1 and then divide by 2 to account for double counting.

Let's try this algorithm out for your example.

  1. Writing the numbers in binary, {1,2,3} = {01, 10, 11}. There are 2 numbers with the one's bit set, and 2 with the two's bit set.

  2. For 01 we get 3*1 + 2*2 = 7 for the sum of ors.

  3. For 10 we get 2*1 + 3*2 = 8 for the sum of ors.
  4. For 11 we get 3*1 + 3*2 = 9 for the sum of ors.
  5. Summing these, 7+8+9 = 24. We need to subtract off 1|1 = 1, 2|2 = 2 and 3|3 = 3, as we counted these in the sum. 24-1-2-3 = 18.
  6. Finally, as we counted things like 1|3 twice, we need to divide by 2. 18/2 = 9, the correct sum.

This algorithm is O(n * max number of bits in any array element).

Edit: We can modify your posted algorithm by simply subtracting the count of all 0-0 pairs from all pairs to get all 0-1 or 1-1 pairs for each bit position. Like so:

int ans = 0;  // Initialize result

// Traverse over all bits
for (int i = 0; i < 32; i++)
{
    // Count number of elements with i'th bit not set
    int k = 0;  // Initialize the count
    for (int j = 0; j < n; j++)
        if ( !(arr[j] & (1 << i)) )
            k++;

    // There are k not set bits, means k(k-1)/2 pairs that don't contribute to the total sum, out of n*(n-1)/2 pairs.
    // So we subtract the ones from don't contribute from the ones that do.

    ans += (1<<i) * (n*(n-1)/2 - k*(k-1)/2);
}

Upvotes: 7

Related Questions