识别奇数,偶数 - 二进制与mod

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编译器会生成尝试对符号位进行智能化的代码.不必要的.