5

已经有关于计算1一个数字中有多少个s的问题，但是这个问题是关于判断1是偶数还是奇数。

不允许使用任何循环或条件（包括 switch）语句。此外，应避免除法、乘法或取模运算符。更具体地说，我们可以假设它是一个 32 位无符号整数。

实际上我已经有了一个实现，但我无法弄清楚它工作的原因。任何证明其正确性或任何新想法的证据都会非常有帮助。

int even_ones(unsigned x)
{
    x ^= x>>16;
    x ^= x>>8;
    x ^= x>>4;
    x ^= x>>2;
    x ^= x>>1;

    return !(x & 1);
}
4

4 回答 4

11

我假设您知道异或^运算的作用-如果将两个位设置为相同的值，则结果为0-否则为1. 因此，当我有两个一位数 A 和 B 时，A^B如果 A 和 B 都是0，或者两者都是 ，那么将是零1。换句话说 - 和中的A和B是偶数...

现在让我们一次做这两位：C 和 D 是两位数。以下是可能的组合：

C    D    C^D
00   00   00   even
01   00   01    odd
10   00   10    odd
11   00   11   even
00   01   01    odd
01   01   00   even
10   01   11   even
11   01   10    odd
00   10   10    odd
01   10   11   even
10   10   00   even
11   10   01    odd
00   11   11   even
01   11   10    odd
10   11   01    odd
11   11   00   even

如您所见 - 每个实例中的操作将位数减少一半，1如果您从奇数开始，则生成的位数是奇数（因为1s 对抵消，但所有其他人都没有改变） .

现在应该很明显了，为什么当您从较大的数字（4 位、8 位、16 位）开始时，同样的事情仍然是正确的。本质上，您的算法从 32 位数字开始，并将其拆分为两个 16 位数字。通过摆脱“双1”，它将位数减少了一半；然后对剩下的一半进行操作，并重复直到只剩下一个位。通过测试该位是 1（奇数）还是 0（偶数），您将得到答案。

如果不清楚，类似的操作x ^= x>>16实际上将前 16 位移动到后 16 位并在那里产生异或。它实际上并没有清除最高位，所以“留下了一个烂摊子”。但是该算法忽略了接下来的混乱。请参阅以下内容（为简单起见，从 8 位开始）：

x =      abcdefgh 
x >> 4 = 0000abcd
new x  = abcdijkl
x >> 2 = 00abcdij
new x  = abmnopqr
x >> 1 = 0abmnopq
new x  = astuvwxy

在此，最后一位数字y是 和 的异或，r而q后者又是和 的异l,j或k,i；h,d它们分别是、f,b、g,c和的 XOR e,a。如您所见，您最终得到了所有位的异或；正如我上面解释的那样，这意味着“全偶数”或“全奇数”，具体取决于最低有效位现在是 a1还是 a 0。

我希望这会有所帮助。

于 2013-10-15T04:25:45.977 回答
5

这里有几个变体可以快速计算一个字节或一个字的奇偶校验。究竟哪种方法最快取决于您的 CPU 以及不同的基本操作相对于彼此的速度。因此，如果这在某种程度上是您的应用程序的瓶颈，您应该对每一个进行分析，以找出哪一个在您的目标机器上运行得最好。

您的解决方案与“并行计算奇偶校验”实现非常相似，只是最后没有巧妙的优化。这里发生的情况是，在每一步中，您将一半位与另一半位进行异或运算，直到只剩下一位。如果有偶数个 1，则单词的奇偶性为 0，如果有奇数个 1，则奇偶性为 1；或者等价地，一个字的奇偶校验只是字中所有位的异或。

由于 XOR 运算符是可交换的和关联的，我们可以重新排序单词中的所有位是如何异或在一起的。因此，我们不是通过将每个位单独异或到结果中来计算所有位的异或，而是将高半位与低半位进行异或，将我们关心的位数减少一半；当剩下一点时，我们就完成了。

于 2013-10-15T04:07:58.790 回答
2

请注意，此 XOR 最高有效 16 位与最低有效 16 位。：

x ^= x>>16;

然后该系列继续对第二个最低有效 8 位与最低有效 4 位进行异或运算，请注意，最高有效 16 位现在只是垃圾，无论发生什么都可以忽略：

x ^= x>>8;

依此类推，我们继续对第二个最低有效 4 位与最低有效 4 位进行异或运算，直到达到 1 位；现在除了最低有效位之外的每一位都是垃圾，最后一行只使用按位和 1 来获得最低有效位并将其翻转以进行均匀性测试。

如果你这样写，也许更容易理解：

int even_ones(unsigned x)
{
    a = (x ^ x>>16) & 0x0000FFFF;
    b = (a ^ a>>8)  & 0x000000FF;
    c = (b ^ b>>4)  & 0x0000000F;
    d = (c ^ c>>2)  & 0x00000003;
    e = (d ^ d>>1)  & 0x00000001;
    return !(e&1);
}

为什么这行得通？因为 XOR 相当于没有进位的按位加法。

于 2013-10-15T04:25:47.930 回答
-3

希望这可以帮助 ：：

   enum {
      EVEN,
      ODD
    } even_odd;

unsigned int check_even_odd_no_of_ones(unsigned int num)
{
  if(num_of_ones(num) & 1)
    return ODD;
  else
    return EVEN;
}

谢谢

于 2013-10-15T05:42:36.180 回答