What is the fastest way to XOR two integers in C#?

Question

I need to XOR one integer a against array of integers q (max of 100,000). i.e. if i am looping, I will

a XOR q[0]

a XOR q[1]

.....

a XOR q[100000]

(100,000 times)

I will have a series of such a to be XORed.

I am writing a console application which will be pass the required input.

I am using the built-in C# ^ operator to do the XOR operation. Is there any other way?

Would converting the integer to a byte array and then XORing each bit and figuring out the end result be a good idea?

Input (don't keep the spaces between the two lines)

1

15 8

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10 6 10

1023 7 7

33 5 8

182 5 10

181 1 13

5 10 15

99 8 9

33 10 14

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace XOR
{
    class Solution
    {
        static void Main(string[] args)
        {

            List<TestCase> testCases = ReadLine();
            //Console.WriteLine(DateTime.Now.ToLongTimeString());
            CalculationManager calculationManager = new CalculationManager();

            foreach (var testCase in testCases)
            {
                var ints = testCase.Queries.AsParallel().Select(query => calculationManager.Calculate(query, testCase.SequenceOfIntegers)).ToList();
                ints.ForEach(Console.WriteLine);
            }

            //Console.WriteLine(DateTime.Now.ToLongTimeString());
            //Console.ReadLine();
        }

        private static List<TestCase> ReadLine()
        {
            int noOfTestCases = Convert.ToInt32(Console.ReadLine());
            var testCases = new List<TestCase>();

            for (int i = 0; i < noOfTestCases; i++)
            {
                string firstLine = Console.ReadLine();
                string[] firstLineSplit = firstLine.Split(' ');
                int N = Convert.ToInt32(firstLineSplit[0]);
                int Q = Convert.ToInt32(firstLineSplit[1]);

                var testCase = new TestCase
                                   {
                                       Queries = new List<Query>(),
                                       SequenceOfIntegers = ReadLineAndGetSequenceOfIntegers()
                                   };

                for (int j = 0; j < Q; j++)
                {
                    var buildQuery = ReadLineAndBuildQuery();
                    testCase.Queries.Add(buildQuery);
                }

                testCases.Add(testCase);
            }

            return testCases;
        }

        private static List<int> ReadLineAndGetSequenceOfIntegers()
        {
            string secondLine = Console.ReadLine();
            List<int> sequenceOfIntegers = secondLine.Split(' ').ToArray().Select(x => Convert.ToInt32(x)).ToList();
            return sequenceOfIntegers;
        }

        private static Query ReadLineAndBuildQuery()
        {
            var query = Console.ReadLine();
            List<int> queryIntegers = query.Split(' ').ToArray().Select(x => Convert.ToInt32(x)).ToList();
            Query buildQuery = ReadLineAndBuildQuery(queryIntegers[0], queryIntegers[1], queryIntegers[2]);
            return buildQuery;
        }

        private static Query ReadLineAndBuildQuery(int a, int p, int q)
        {
            return new Query { a = a, p = p, q = q };
        }


    }

    class CalculationManager
    {
        public int Calculate(Query query, List<int> sequenceOfIntegers)
        {
            var possibleIntegersToCalculate = FindPossibleIntegersToCalculate(sequenceOfIntegers, query.p, query.q);
            int maxXorValue = possibleIntegersToCalculate.AsParallel().Max(x => x ^ query.a);
            return maxXorValue;
        }

        private IEnumerable<int> FindPossibleIntegersToCalculate(List<int> sequenceOfIntegers, int p, int q)
        {
            return sequenceOfIntegers.GetRange(p - 1, (q - p) + 1).Distinct().ToArray();
        }
    }

    class TestCase
    {
        public List<int> SequenceOfIntegers { get; set; }
        public List<Query> Queries { get; set; }
    }

    class Query
    {
        public int a { get; set; }
        public int p { get; set; }
        public int q { get; set; }
    }
}

Solution 1

Using the ^ bit-wise xor operator is the fastest way to xor integers.

The operation is translated to a single atomic processor operation.

As you can see in the disassembly:

        int i = 4;
00000029  mov         dword ptr [ebp-3Ch],4 
        i ^= 3;
00000030  xor         dword ptr [ebp-3Ch],3 

So if you wish to make your code run faster, you should change the algorithm / approach (as suggested by Marc Gravell), not the xor method.

Solution 2

The only thing I'd even try (if there was reason to think the int approach was too slow) would be to use unsafe code to treat each int[] as a long*, and use 64-bit arithmetic (again, using ^) instead of 32, half the iterations, and a bit less indirection. IIRC that is pretty much what I did for some web-socket code (applying web-socket masks for client-to-server messages is a bulk XOR). You'd need to be careful for the last few bytes, obviously.