在C#中，XOR两个整数的最快方法是什么？

Question

我需要将一个整数 a 和一个整数数组 q (最大长度为 100,000) 进行异或操作。例如，如果我循环进行操作：

a XOR q[0]

a XOR q[1]

.....

a XOR q[100000]

(重复执行 100,000 次)

然后我就会得到一系列被异或过的 a。

我正在编写一个控制台应用程序，它将传递所需的输入。

我使用内置的 C# ^ 运算符执行异或操作。还有其他方法吗？

将整数转换为字节数组，然后对每个位执行异或操作并计算出最终结果是否是一个好主意？

输入（请勿保留两行之间的空格）

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; }
    }
}

- Miral

---

没有什么比内置运算符更快了。 - Peter C

你想要实现什么目标？根据目标可能有更快的方法。 - BrokenGlass

你想要做一个加密功能是吗？ - Marc B

C#有内置的数组边界检查，不是吗？那会使程序变得非常慢。你需要用汇编语言编写它，或者至少使用C或C++。 - TonyK

不正确：JIT可以消除经典向量“for”循环中的边界检查，或者使用unsafe代码并在第一次避免边界检查。 - Marc Gravell

Answer 1

使用位运算符^是异或整数最快的方法。

该操作会被转换为单个原子处理器操作。

从反汇编结果可以看到：

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

如果你希望让你的代码运行更快，你应该改变算法/方法（如Marc Gravell所建议的），而不是改变异或方法。

- SimpleVar

Answer 2

如果有理由认为int方法太慢，我唯一尝试的方式将是使用unsafe代码将每个int[]作为long*处理，使用64位算术（再次使用^）而不是32位，减少一半迭代和一些指针操作。回想一下，这就是我为某些WebSocket代码所做的事情（将WebSocket掩码应用于客户端发送到服务器的消息是批量异或）。当然，你需要小心最后几个字节。

- Marc Gravell

---

Marc，你知道用“@”符号提及你的名字有问题吗？我怀疑这是因为你昵称中的特殊字符所致。 - SimpleVar

我发布的代码中有一个小错误。现在已经修复了：http://pastebin.com/iXmTHS51 顺便说一下，我已经测试了这种方法与使用int*的不安全方法的速度，long通常需要的时间只有int的65%。所以为此点赞！ - SimpleVar

Answer 3

XOR是一种快速操作，因此您的应用程序将受到您生成整数的速率的限制。

如果您只是在它们变得可用时对它们进行异或运算，无论使用何种方法，异或时间都将可以忽略不计。

例如，如果您从文本文件中读取整数。磁盘IO和解析时间将比异或时间大几个数量级。操作系统还会使用“read-ahead”技术，在实际操作中，这意味着它在您处理当前批次的同时获取下一个批次的整数。这意味着解析+异或运算除了最后一批之外，不会给总体处理时间增加额外的时间负担。

- adrianm

Answer 4

如果你需要对更多的元素（如你所说）进行异或运算，可以通过以下方式加速处理数组：

如果您需要对称呼为a的更多元素与数组进行异或运算，则可以通过以下方式加快处理速度：

int x = q[0]
for(int i = 1; i < q.Length; i++)
   x ^= q[i]

a1 ^= x
a2 ^= x
...

编辑： 抱歉，基本上是相反的情况

int x = a1 ^ a2 ^ ... an
for(int i = 0; i < q.Length; i++)
     q[i] ^= x

- raisyn

---

这并没有解决楼主的问题。注意细节。 - SimpleVar

仍然没有解决。x是一个简单的掩码，已经给定了。而且，你不会期望他硬编码a1 ^ a2 ^ ... an，对吧？！假设第一行实际上是用循环来执行那个逻辑，你所实现的是将每个元素与所有元素的异或进行异或运算。 - SimpleVar

即使您修复了算法，它仍然无法解决OP的问题，因为他已经有了那个解决方案。他正在寻找比简单循环更快的方法。 - SimpleVar

只有当仅有很少几个时才进行硬编码 ;）。 如果a有n个元素，q的长度为100000，则我的算法需要n + 100000次迭代，而他描述的算法需要n * 100000次。 - raisyn

假设第一行实际上是用循环来执行该逻辑，对每个元素进行异或运算，与所有元素的异或结果进行异或运算是相同的。将一个元素与所有元素进行异或运算等同于将一个元素与所有元素的异或结果进行异或运算。 - raisyn

你在这里误解的是，OP想要将一个整数(a)与一个元素列表进行异或运算。for (i:0...n) { list[i] ^= mask; } 或者 mask ^= list[i]（取决于你想要进行异或运算的对象）- 这就是所需的逻辑，其中mask是一个给定的数字，例如41623。 - SimpleVar