所有对异或值的总和 [英] sum of xor values of all pairs

问题描述

我们有一个数组 A（比如[1,2,3]），。我们需要找到的的 XOR（^）SUM 的所有对阵列中的整数的。 虽然这可以很容易地在完成为O（n ^ 2）但我怎么能提高解决方案的复杂性？ 例如，对于上述排列，A，答案应该是（1 ^ 2）+（1 ^ 3）+（2 ^ 3）= 6 谢谢。

We have an array A (say [1,2,3]) . We need to find the XOR(^)SUM of all pairs of integers in the array. Though this can easily be done in O(n^2) but how can i improve the complexity of the solution ? E.g for the above array , A, the answer would be (1^2)+(1^3)+(2^3) = 6 Thanks.

推荐答案

您可以单独计算做一个位的时间。

You can separate the calculation to do one bit at a time.

例如，看一下在阵列中的所有数字的最右边位。假设 A 数字有一个最右边的0位，而 B 数字有1位。接着出来的是对的， A * B 其中将有1在异或的最右边位。这是因为有 A * B 方法来选择一个号码，有一个0位和一个具有1位。因此，这些位将有助于 A * B 对所有的异或的总和。

For example, look at the rightmost bit of all the numbers in the array. Suppose that a numbers have a rightmost 0-bit, and b numbers have a 1-bit. Then out of the pairs, a*b of them will have 1 in the rightmost bit of the XOR. This is because there are a*b ways to choose one number that has a 0-bit and one that has a 1-bit. These bits will therefore contribute a*b towards the total of all the XORs.

在一般情况下，当看 N 个位（其中最右边的位是0号），看看有多少人数0（称之为<子>ñ ），以及有多少1（称这家B <子> N ）。对最后一笔的贡献将是一个<子> N * B <子> N * 2 ^N 。你需要做这对于每一位总结所有这些捐款。

In general, when looking at the nth bit (where the rightmost bit is the 0th), count how many numbers have 0 (call this a_n) and how many have 1 (call this b_n). The contribution towards the final sum will be a_n*b_n*2ⁿ. You need to do this for each bit and sum all these contributions together.

这可以在O（KN）的时间，其中<​​code> K 是在给定值的位数来完成。

This can be done in O(kn) time, where k is the number of bits in the given values.

这篇关于所有对异或值的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！