c# - 识别奇数、偶数——二进制与模数

Question

最近我不得不为大量整数确定一个数是奇数还是偶数。我想到了一个想法，通过将数字与 1 进行 AND 运算并将结果与​​ 1 进行比较来将数字识别为奇数或偶数

x & 1 == 1 // even or odd 

我从未在实践中见过这种实现。您经常看到的最常见方式是:

x % 2 == 0

我决定对这两种方法进行一些性能检查，二进制方法在我的机器上似乎稍快一些。

int size = 60000000;
List<int> numberList = new List<int>();
Random rnd = new Random();

for (int index = 0; index < size; index++)
{
    numberList.Add(rnd.Next(size));
}

DateTime start;
bool even;

// regular mod
start = DateTime.Now;
for (int index = 0; index < size; index++)
{
    even = (numberList[index] % 2 == 0);
}
Console.WriteLine("Regualr mod : {0}", DateTime.Now.Subtract(start).Ticks);

// binary 
start = DateTime.Now;
for (int index = 0; index < size; index++)
{
    even = ((numberList[index] & 1) != 1);
}
Console.WriteLine("Binary operation: {0}", DateTime.Now.Subtract(start).Ticks);

Console.ReadKey();

有没有人看过二进制方法的实现？有什么缺点吗？

Answer 1

嗯，是的，这是一个轻微的优化。此代码段:

        uint ix = 3; // uint.Parse(Console.ReadLine());
        bool even = ix % 2 == 0;

在发布版本中生成此机器码:

            uint ix = 3;
0000003c  mov         dword ptr [ebp-40h],3 
            bool even = ix % 2 == 0;
00000043  mov         eax,dword ptr [ebp-40h] 
00000046  and         eax,1 
00000049  test        eax,eax 
0000004b  sete        al   
0000004e  movzx       eax,al 
00000051  mov         dword ptr [ebp-44h],eax 

请注意，JIT 编译器足够智能，可以使用 AND 处理器指令。它不像 % 运算符通常执行的那样进行除法。那里的荣誉。

但是您的自定义测试会生成此代码:

        uint ix = uint.Parse(Console.ReadLine());
// Bunch of machine code
        bool even = (ix & 1) == 0;
00000024  test        eax,1 
00000029  sete        al   
0000002c  movzx       eax,al 
0000002f  mov         esi,eax 

我不得不更改赋值语句，因为 JIT 编译器突然变得聪明并在编译时计算表达式。代码非常相似，但 AND 指令被 TEST 指令取代。在此过程中保存一条指令。颇具讽刺意味的是，它这次如何选择不使用 AND :)

这些是做出假设的陷阱。然而，您最初的直觉是正确的，它应该节省大约半纳秒。 非常很难看到它回来，除非这段代码存在于一个非常紧密的循环中。当您将变量从 uint 更改为 int 时，它会变得截然不同，然后 JIT 编译器生成的代码会尝试对符号位进行智能处理。不必要的。