сумма значений xor всех пар

Question

У нас есть массив A (say [1,2,3]). Мы должны найти XOR (^) SUM всех пар целых чисел в массиве. Хотя это можно легко сделать в O(n^2), но как я могу улучшить сложность решения? Например, для вышеупомянутого массива, A, ответ будет (1^2)+(1^3)+(2^3) = 6 Спасибо.

Answer 1

Вы можете отделить расчет, чтобы сделать один бит за раз.

Например, посмотрите на самый правый бит всех чисел в массиве. Предположим, что номера a имеют самый правый 0-разрядный номер, а b - 1 бит. Затем из пар, a*b из них будет иметь 1 в крайнем правом углу XOR. Это связано с тем, что есть a*b способов выбрать одно число с 0-битным и одно, которое имеет 1 бит. Таким образом, эти биты будут вносить a*b в общую сумму всех XOR.

В общем, при взгляде на n-й бит (где крайний правый бит равен 0-я), подсчитать, сколько числа имеют 0 (назовем это _п) и сколько есть 1 (назовем Это B _п). Вклад в окончательную сумму составит _n * b _n * 2 ⁿ. Вы должны сделать это для каждого бита и суммировать все эти вклады вместе.

Это может быть сделано в O (kn), где k - это количество бит в данных значениях.

Answer 2

Вот ответить на jsFiddle подтверждающая interjay, который делает вычисления, используя оба метода O (N^2) против O (Nk):

var list = [1,2,2,3,4,5] 

function xorsum_on2(a) 
{ 
    var sum = 0 
    for(var i=0 ; i<a.length ; ++i) 
     for(var j=i+1 ; j<a.length ; ++j) 
      sum += a[i]^a[j] 
    return sum 
} 

// This sets all elements of a to 0 
function xorsum_onk(a) 
{ 
    var allzeroes; 
    var sum = 0; 
    var power = 0; 
    do { 
     allzeroes = true; 
     var bitcount = [0,0]; 
     for(var i=0 ; i<a.length ; ++i) 
     { 
      bitcount[a[i]&1]++; 
      a[i] >>= 1; 
      if(a[i]) allzeroes = false; 
     } 
     sum += (bitcount[0]*bitcount[1]) << power++; 
    } while(!allzeroes); 
    return sum; 
} 


var onk = document.getElementById("onk") 
var on2 = document.getElementById("on2") 

on2.innerHTML = xorsum_on2(list) 
onk.innerHTML = xorsum_onk(list) 

Answer 3

#include <iostream> 
using namespace std; 

int main() { 
    long long int n,i,j,k; 

    cin>>n; // number of elements in array 
    long long int arr[n],ans=0; 

    for(i=0;i<n;i++) 
     cin>>arr[i]; 

    // iterate through all the bits 
    for(i=0;i<32;i++) 
    { 
     k=0; // k is the number of set bits in the array at ith psotion 
     for(j=0;j<n;j++) 
      if((arr[j] & (1<<i))) 
       k++; 
     /* there are k set bits and n-k unset bits. 
      therefore number of pairs with one set bit and one unset bit is kC1 and n-kC1 
      Every pair adds 2^i in the answer. 
     */ 
     ans+= (1<<i)*(k*(n-k));  
    } 
    cout<<ans<<endl; 
    return 0; 
}