不使用循环计算32位整数的奇偶校验位

在牛 B 的 CSAPP 一书的第二版中,有这么一道课后题,要求实现以下函数:

/* Return 1 when x contains an odd number of 1s; 0 otherwise
 * Assume w=32 */
int odd_ones(unsigned x);

图 1: odd ones() 函数原型

另外题目还要求:
(1)不能使用任何条件判断(包括 if 语句和?: 表达式),循环,switch 语句,函数调用,宏替换;
(2)不能使用乘除法以及模运算;
(3)不能使用比较运算符(<,>,<=,>=),但是可以使用相等以及不等运算(== 以及!=);
(4)不能使用显式或者隐式类型转换;
(5)假设 x为 32 位;
(6)所有操作次数只和不能超过 12
这个题实际上就是求一个 32 位整数的奇偶校验位,将整数视为一个 32 位向量,如果其中的 1 的个数为奇数则返回 1,否则返回 0(我也不知道这是奇校验还是偶校验)。拿到这个题很容易想到应该使用异或运算,将整数的 32 个位求异或即可得到结果。这里的难点在于不能使用循环,也不能使用函数调用(不能使用递归)。本文将给出两种解决的方法,第一种方法使用纯 C 的位运算来获得结果,第二种方法使用 X86 架构中的 PF 条件寄存器来获得结果,下面分别进行讨论。

一 C 位运算
在考虑如何使用 C 的位运算计算 32 个位的异或之前,我们先考虑如果在硬件领域,该操作该如何使用异或门实现?
显而易见的是,如果需要硬件实现 32 个位的异或,我们可以将 32 个位分成 16 组,每组的两个位输入到一个 2 输入异或门,将得到的 16 个输出再输入到 8 个 2 输入异或门,以此类推,经过 5 次这样的组合(第一次 16 组,第二次 8 组,第三次 4 组,第四次 2 组,第五次 1 组),就可以得到最终需要的结果。
对于使用 C 的位运算,我们可以使用同样的方法:首先将 32 位整数的高 16 位与低 16 位分别异或,得到一个 16 位向量。然后将所得结果的高 8 位与低 8 位分别异或,以此类推,于是就可以得到odd ones() 的以下实现:

/* Return 1 when x contains an odd number of 1s; 0 otherwise
 * Assume w=32 */
int odd_ones(unsigned x)
{
    unsigned val= x & 0xffff;
    val ^= x>>16;
    val = (val>>8) ^ (val & 0xff);
    val = (val>>4) ^ (val & 0xf);
    val = (val>>2) ^ (val & 0x3);
    val = (val>>1) ^ (val & 0x1);

    return val;
}

图 2: odd ones() 的第一个实现

仔细分析图2中的代码,我们将发现其实还可以再简化。将 32 位整数的高 16 位与低 16 位分别异或
后,我们将不再关心所得结果的高 16 位数据(异或没有进位)
,后续的计算也一样,因此我们可以将
图2简化为图3:

/* Return 1 when x contains an odd number of 1s; 0 otherwise
* Assume w=32 */
int odd_ones(unsigned x)
{
unsigned val= x ^ (x>>16);
val = (val>>8) ^ val;
val = (val>>4) ^ val;
val = (val>>2) ^ val;
val = (val>>1) ^ val;
val = val & 0x1;

return val;
}

图 3: odd ones() 的第二个实现

最后数一下,不包括赋值及返回,本函数一共使用了 11 个运算,满足题目要求。

二 直接调用 X86 架构 CPU 的 PF 寄存器
X86 CPU 的状态寄存器中,第 2 位(最低位为 0 而不是 1,第 2 位名为 PF)用于保存最近的计算结果中低 8 位数据的奇偶性。因此,我们可以在 C 中插入汇编,直接读取该寄存器的值。但因为该寄存器只标示低 8 位的奇偶性,需要将 32 位整数分成 4 个子向量。

int odd_ones_asm(unsigned x)
{
    int ret_val=0;

    asm("testl %1, %1; pushf; "
        "shrl $8, %1; pushf; "
        "shrl $8, %1; pushf; "
        "shrl $8, %1; pushf; "
        "popq %%rbx; movl %%ebx, %0; "
        "popq %%rbx; xorl %%ebx, %0; "
        "popq %%rbx; xorl %%ebx, %0; "
        "popq %%rbx; xorl %%ebx, %0; "
        "shrl $2, %0; andl $1, %0;"
        : "=r" (ret_val)
        : "r" (x)
        : "%rbx"
       );

    return ret_val;
}

图 4: 使用内嵌汇编实现odd ones()

在(computing) 有更多的关于 X86 架构状态
寄存器的描述。


三 验证

在验证该函数时,我首先使用循环得到一个函数的实现,然后用穷举法对比两个函数的输出,具体代码见5,这里给出的是汇编函数的验证,如果要验证使用 C 位运算的函数,简单的修改调用的函数名就行了。
在我的 Athlon3000+(未超频)上,穷举验证大约花了 7 ~ 8 分钟,由此看来,如果要处理一个64 位整数,就不能再使用穷举验证了。

#include <stdio.h>
#include <limits.h>

int main(int argc, char* argv[])
{
    int i;
    unsigned test_x;
    int err;

    /*
     * test all the unsigned integers automaticlly
     */
    err=0;
    for(i=0; i<UINT_MAX; i++)
        if(odd_ones_asm(i) != odd_ones_iter(i))
        {
            printf("Aha! your function odd_ones_asm() got wrong "
                    "when it process 0x%x\n",i);
            err=1;
            break;
        }
    /* test UINT_MAX */
    if(odd_ones_asm(i) != odd_ones_iter(i))
    {
        printf("Aha! your function odd_ones_asm() got wrong "
                "when it process 0x%x\n",i);
        err=1;
    }

    if(!err)
        printf("Congratulations! Your function odd_ones() got "
                "correct with all 32-bit integers!\n");
}

int odd_ones_iter(unsigned x)
{
    int i;
    int ret_val=0;

    for(i=0; i<32; i++)
    {
        ret_val ^= (x>>i) & 0x1;
    }

    return ret_val;
}