在没有比较运算符的情况下查找 2 个数字之间的最小值

Question

我看到下面的方法给出了最小值 b/w 2 个没有关系运算符的数字

y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))

在这里如果 x=6 和 y=4 x-y=2 是正数并且将这个值向右移动 31 次得到 0。（因为 +ve 数的符号位是 0）并且 eqn 变成

y + ((x-y)&0)

从上面的等式我们得到 y 作为最小值，这是正确的。

但是对于 x=4 和 y=6 的情况，x-y=-2 并将其向右移动 31 次得到 1 并且等式变为：

y + ((x-y)&1)

根据我的理解，-2 和 1 的按位 & 变为 0，方程式给出 o/p 作为 y(6) 而不是 x(4)。有人可以解释一下吗？

完整代码：https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/

谢谢

Answer 1

该网站的解释有误。当x < y

(x - y) >> 31 = 0b1...1 (32 ones) (*)

然后

y + ((x - y) & 0b1...1) = y + (x - y) = x

(*) 注意负数的右移是implementation-defined。通常，它执行 arithmetic right shift，用二进制补码表示中的负数的最高有效位填充所有二进制数字 1。

Answer 2

与 "normal" 方式相比，它在许多体系结构上效率不高且速度较慢。我还应该提到它不可读并且很容易出错。

示例：

int foo(int x, int y) 
{
    return (y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1))));
}

int foo1(int x, int y) 
{
    return x > y ? y : x;
}

以及生成的代码 (ARM Cortex)：

foo:
        sub     r0, r0, r1
        and     r0, r0, r0, asr #31
        add     r0, r0, r1
        bx      lr
foo1:
        cmp     r0, r1
        movge   r0, r1
        bx      lr

或 x86

foo:
        sub     edi, esi
        mov     eax, edi
        sar     eax, 31
        and     eax, edi
        add     eax, esi
        ret
foo1:
        cmp     edi, esi
        mov     eax, esi
        cmovle  eax, edi
        ret

Answer 3

在新标准获得批准之前，有符号整数的表示形式是 implementation-based，并且 >> 在它们上面也是如此（<< 是一个 UB）。假设平台得到有符号值作为 2 的补码，那么二进制中的 -2 是 11111111111111111111111111111110。将其右移 31 次实际上可能导致所有位设置的值（等于 -1）或值 1，具体取决于实现.应该是 static_cast 到 unsigned 以明确的方式移动。

在没有比较运算符的情况下查找 2 个数字之间的最小值

Finding minimum value between 2 numbers without comparision operators

c

c++

bit-manipulation

bitwise-operators

bitwise-and