无分支位运算实现：mask为0返回1、为-1返回x的表达式求解

需求说明 #

要消除C语言中的if分支，实现无分支编程。现有无符号整数变量mask，取值仅为0（全0位）或-1（全1位，无符号下等价于所有位置1）；另有无符号整数变量x。需要构造位运算表达式，满足：

• 当mask == 0时，返回1
• 当mask == -1时，返回x

背景需求是替换以下带分支的代码：

unsigned x = 3;
unsigned some_number = 42;

if (some_number % x == 0)
{
    some_number /= x;
}

解决方案 #

核心位运算表达式如下：

unsigned denom = 1 | (x & mask);

原理说明 #

• 当mask为全1（-1）时：x & mask结果为x，1 | x等价于x（无符号整数下，按位或操作不会改变x的有效数值）
• 当mask为全0时：x & mask结果为0，1 | 0结果为1

也可使用等价写法：

unsigned denom = (x & mask) | (~mask & 1);

逻辑一致：~mask在mask为全0时是全1，~mask &1结果为1；mask为全1时~mask是全0，~mask &1结果为0，最终输出符合要求。

结合你的代码修改 #

简化版验证代码 #

// Check whether some_number is divisible by x
unsigned mask = ((some_number % x) - 1) >> 31;
unsigned denom = 1 | (x & mask);
some_number /= denom;

完整Project Euler第三题代码修改 #

size_t largest_prime_factor(size_t number)
{
    if (number < 2) return 0;
    if (number == 2) return 2;
    while ((number & 1) == 0)
    {
        number >>= 1;
    }
    size_t lpf = 2;
    size_t i = 3;
    size_t max_iter = sqrt(number);
    while (i < max_iter)
    {
        size_t mask = ((number % i) - 1) >> 31;
        lpf = (i & mask) | (lpf & ~mask);
        size_t denom = 1 | (i & mask); // 替换原代码中的X
        number /= denom;
        i += 2;
    }
    return lpf;
}

mask生成逻辑说明 #

((some_number % x) - 1) >> 31的作用：

• 当some_number能被x整除时，余数为0，0 - 1 = -1（无符号下是全1），右移31位后仍为全1（mask=-1）
• 当some_number不能被x整除时，余数≥1，余数-1 ≥0，右移31位后结果为0（mask=0）

内容的提问来源于stack exchange，提问作者Ali