在 C# 中对两个整数进行 XOR 的最快方法是什么
本文关键字:XOR 是什么 方法 整数 两个 | 更新日期: 2023-09-27 18:33:55
我需要对整数数组q
(最大值为 100,000)进行 XOR 一个整数a
。 即如果我在循环,我会
异或 q[0]
异或 q[1]
.....
一个异或q[100000]
(100,000次)
我将有一系列这样的a
进行异或。
我正在编写一个控制台应用程序,该应用程序将传递所需的输入。
我正在使用内置的 C# ^
运算符来执行 XOR 操作。还有其他办法吗?
将整数转换为字节数组,然后对每个位进行异或运算并找出最终结果是一个好主意吗?
输入(不要在两行之间保留空格)
1
15 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
106 10
1023
年7 733 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; }
}
}
使用^
位异或运算符是异或整数的最快方法。
该操作将转换为单个原子处理器操作。
正如您在反汇编中看到的:
int i = 4;
00000029 mov dword ptr [ebp-3Ch],4
i ^= 3;
00000030 xor dword ptr [ebp-3Ch],3
因此,如果你想让你的代码运行得更快,你应该改变算法/方法(如Marc Gravell所建议的),而不是xor方法。
我唯一会尝试的(如果有理由认为 int 方法太慢)是使用unsafe
代码将每个int[]
视为long*
,并使用 64 位算术(再次使用 ^
)而不是 32,一半的迭代,并且间接性少一点。IIRC 这几乎就是我对一些 web-socket 代码所做的(对客户端到服务器的消息应用 web-socket 掩码是一个批量 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
XOR 是一种快速操作,因此您的应用程序将受到生成整数的速率的限制。
如果您只是在它们可用时对它们进行异或,则无论采用何种方法,异或时间都将可以忽略不计。
例如,如果您从文本文件中读取整数。磁盘 io + 解析时间将比异或时间大几个数量级。操作系统还将使用read-ahead
这实际上意味着它会在您处理当前批次时获取下一批整数。这意味着解析 + xor 不会给整体处理时间增加额外的时间,除了最后一批。