bitwise array manipulation

user_18098109 0
Viewed 286

You are given an array A containing N positive integers (1 <= A[i] <= 10^9)

Let F(i,j,k) = ( A[i] | A[j] ) & A[k]
| represents bitwise OR and & represents bitwise AND
The task is to determine the bitwise XOR of F(A,B,C) over all triplets (A,B,C) such that 1<= A,B,C <=N

for Example:
if N=2 and A=[1,4]
triplets will be:

  • F(1,1,1) = 1
  • F(1,1,2) = 0
  • F(1,2,1) = 1
  • F(1,2,2) = 4
  • F(2,1,1) = 1
  • F(2,1,2) = 4
  • F(2,2,1) = 0
  • F(2,2,2) = 4
    Bitwise XOR of all = 1^0^1^4^1^4^0^4 = 5
    so the answer is 5.

one more example:
if A=[14,9,19,18,17,11,12] answer=16

How to solve this question or how to proceed with such questions?
Code in javascript would be helpful, but other languages are also welcome.

bitwise-operators bit-manipulation arrays algorithm
2 Answers

These kinds of questions can be solved by considering each bit separately.

For each bit, let n0 be the number of array elements that have that bit set to 0, and let n1 be the number of elements that have that bit set to 1.

Then it's easy to determine whether or not that bit is set in the answer:

  • The number of pairs i,j such that the bit is set in A[i]|A[j] is n1*n1 + n1*n0*2
  • The number of triplets i,j,k with that bit set in F(i,j,k) is then n1*(n1*n1 + n1*n0*2)
  • Since all the F's are XORed together, the result will have the bit set if it's set in an odd number of triplets, i.e., if the above expression evaluates to an odd number.

At this point, we could easily solve the problem by counting the 1s and 0s for each bit, but notice that n1*(n1*n1 + n1*n0*2) evaluates to an odd number exactly when n1 is odd, i.e., when the bit appears an odd number of times in the array. To get a number with each bit set if it's set an odd number of times in the array...

just XOR all the array elements together.

user_54835260

The first solution by @Matt is quite fine. Here is another solution that uses simple math tricks.

In the following, I will use the sum notation for XOR, and product notation for &.

The problem is to calculate F = sum F(i, j, k) = sum_{i, j, k} (A[i]|A[j]).A[k].

By using the distributive property of multiplication (&) over addition (xor), we get:

F = sum_k A[k] . sum_{i, j} (A[i] | A[j])

We note that

A[i] | A[j] = A[i] + A[j] + A[i].A[j]

Then

sum_{i, j} (A[i] | A[j]) = sum_{i, j} (A[i] + A[j] + A[i].A[j])

As A + A = 0, it is clear that sum_{i, j} (A[i] + A[j] = 0

Moreover, if (i != j), A[i].A[j] + A[j].A[i] = 0. Therefore,

sum_{i, j} A[i].A[j] = sum_i A[i].A[i] = sum_i A[i]

We used here that A & A = A.

Finally,

F = sum_k A[k] . sum_k A[k] = sum_k A[k]

The solution is to take the XOR of all the elements in the array.

user_105533410
Related