C语言中对ULONG_MAX使用位移位导致程序挂死的原因分析

问题描述 #

我编写了一个小型C程序，用于计算将一个数转换为另一个数所需翻转的比特位数量。程序在正常情况下运行良好，但当传入ULONG_MAX作为参数时出现程序挂死的异常行为。相关代码如下：

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

/**
 * flip_bits - Count the number of bits to flip to equalize two numbers
 * @n: First number
 * @m: Second number
 *
 * Return: the number of bits to flip
 */
unsigned int flip_bits(unsigned long int n, unsigned long int m)
{
        unsigned long int diff, count;
        int i;

        diff = n ^ m;

        count = 0;
        i = 0;
        while (diff >> i)
        {
                if (diff >> i & 1)
                        count++;

                i++;
        }

        return (count);
}

/**
 * main - check the code
 *
 * Return: Always 0.
 */
int main(void)
{
    unsigned int n;

    n = flip_bits(1024, 1);
    printf("%u\n", n);
    n = flip_bits(402, 98);
    printf("%u\n", n);
    n = flip_bits(1024, 3);
    printf("%u\n", n);
    n = flip_bits(ULONG_MAX, 0);
    printf("%u\n", n);
    return (0);
}

原因分析 #

当传入ULONG_MAX和0时，diff = ULONG_MAX ^ 0的结果是ULONG_MAX，也就是该类型所有比特位都为1。此时循环条件diff >> i的问题在于：

• i被定义为有符号int类型，而unsigned long int的比特位数（比如64位）通常大于int的最大值（比如32位系统中int最大值是2^31-1）。
• 当i递增到int的最大值后，继续加1会触发有符号整数溢出，这在C标准中属于未定义行为，此时i会变成负数。
• 移位操作的右操作数如果是负数，同样属于未定义行为，这会导致diff >> i的结果永远不为0，循环无法终止，最终程序挂死。

修复方案 #

有两种简单的修复方式：

方式一：将循环变量改为无符号类型 #

把i的类型从int改为unsigned int或者size_t，避免有符号溢出的问题，同时确保循环能在i达到unsigned long int的比特位数时终止：

unsigned int flip_bits(unsigned long int n, unsigned long int m)
{
        unsigned long int diff, count;
        size_t i; // 改为size_t或unsigned int

        diff = n ^ m;

        count = 0;
        i = 0;
        while (diff >> i)
        {
                if (diff >> i & 1)
                        count++;

                i++;
        }

        return (count);
}

方式二：优化比特位统计逻辑 #

使用更高效的比特位统计方法，每次清除最低位的1，直到diff变为0，这种方法不需要循环变量，也不会出现溢出问题：

unsigned int flip_bits(unsigned long int n, unsigned long int m)
{
        unsigned long int diff = n ^ m;
        unsigned int count = 0;

        while (diff)
        {
                count++;
                diff &= diff - 1; // 清除最低位的1
        }

        return count;
}

这种方法的效率更高，循环次数等于diff中1的位数，而不是类型的总比特位数。

内容的提问来源于stack exchange，提问作者Nwaburu Emeka Christian