2

I have a list of integers, that can have any number of items. Now, I want to calculate the BITWISE XOR of all these numbers. If the numbers are already known, this can be done as follows:

int xor = 10 ^ 25 ^ 40 ^ 55......and so on

But when number of elements is unknown, I am not able to achieve it dynamically at the runtime, for each element of the list. I want to apply bitwise XOR to all the times at once, not two at a time.

founderio
  • 407
  • 1
  • 3
  • 15
Brijesh Ahuja
  • 43
  • 4
  • Is there any reason you want to XOR all at once? – Vignesh Jul 31 '20 at 23:43
  • If you don't know how many, how could you do them all at once, even if there was a way. When you do a XOR, you are doing it two at a time. For example, your `10^25^40^55` is actually evaluated as `((10^25)^40)^55`. C# has a XOR *Compound assignment* operator `^=` that you can use in a loop https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/operators/bitwise-and-shift-operators#compound-assignment – Flydog57 Jul 31 '20 at 23:49

2 Answers2

6

You can use the Aggregate extension method (from System.Linq) to apply an accumulator function over each item in the array. It works by taking a starting value (we can use 0 in this case, since 0 ^ n == n), and applying the accumulator function for each item in the list.

In our case the accumulator is just adding the XOR of the number with the next value back to the number again:

int[] numbers = {10, 25, 40, 55};
int result = numbers.Aggregate(0, (accumulation, next) => accumulation ^ next);
// result = 12
Rufus L
  • 36,127
  • 5
  • 30
  • 43
  • Good alternative solution if there is e.g. an IEnumerable and not an array or list, i.e. true "unknown amount of elements". – founderio Aug 01 '20 at 00:02
  • @founderio Not sure what you mean - it works fine with any `IEnumerable`, including arrays and lists; it doesn't matter if the number of elements is known or not. – Rufus L Aug 04 '20 at 22:49
  • Yes, it works with anything. The currently accepted answer (mine) does not. I have to mention here that looping over an array compared to doing a Linq call may have differences in runtime performance. – founderio Aug 05 '20 at 23:12
  • Ah, I see. The source code is [here](https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,ac261011ebd4a616,references), not sure if there's a perf concern there or not? – Rufus L Aug 05 '20 at 23:59
  • Unless the compiler optimizes the Linq call away, directly looping is *probably* faster than Linq due to overhead when calling methods, and plainly more logic being executed. However it always depends on what you do. See e.g. https://stackoverflow.com/questions/4044400/linq-performance-faq – founderio Aug 06 '20 at 22:15
3

You can loop over the elements and apply the xor to a result variable, like this:

int[] values = new int[] { 10, 25, 40, 55 };
int xor = values[0];
for(int i = 1; i < values.Length; i++) {
    xor ^= values[i];
}

Due to the interchangable nature of xor, these two approaches have the same result:

// In one line
int xor1 = 10 ^ 25 ^ 40;

// In separate lines
int xor2 = 10 ^ 25;
xor2 ^= 40;

See here: https://dotnetfiddle.net/zqSVad
The actual calculation happening here is exactly the same. You can expand this concept to a loop and have the desired effect.

founderio
  • 407
  • 1
  • 3
  • 15