7

我需要将一个整数a与整数数组q（最多 100,000）进行异或。即，如果我在循环，我会

异或 q[0]

异或 q[1]

......

异或 q[100000]

（十万次）

我将有一系列这样a的异或。

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

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

将整数转换为字节数组，然后对每个位进行异或运算并找出最终结果是个好主意吗？

输入（不要保留两行之间的空格）

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

4 回答 4

16

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

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

正如您在反汇编中看到的：

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

所以如果你想让你的代码运行得更快，你应该改变算法/方法（正如 Marc Gravell 所建议的那样），而不是 xor 方法。

于 2012-05-12T23:04:12.127 回答
5

我什至会尝试的唯一方法（如果有理由认为 int 方法太慢）是使用unsafe代码将每个int[]视为 a long*，并使用 64 位算术（再次使用^）而不是 32，一半迭代，以及更少的间接性。IIRC 这几乎就是我为一些 Web 套接字代码所做的（为客户端到服务器的消息应用 Web 套接字掩码是批量 XOR）。显然，您需要小心最后几个字节。

于 2012-05-12T23:05:01.717 回答
0

如果您必须对数组 xor 更多称为 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
于 2012-05-12T23:44:57.020 回答
0

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

如果您只是在它们可用时对它们进行异或，则无论使用哪种方法，异或时间都将是可以忽略的。

例如，如果您从文本文件中读取整数。磁盘 io + 解析时间将比 xor 时间大几个数量级。操作系统也将使用read-aheadwhich 实际上意味着它会在您处理当前批次时获取下一批整数。这意味着除了最后一批之外，解析 + xor 不会为整体处理时间增加额外的时间。

于 2012-05-13T17:55:00.123 回答