使用位运算符比较两个整数

Question

我需要使用位运算符比较两个整数。 我遇到了一个问题，即必须在不使用比较运算符的情况下比较两个整数。 使用位运算符将有所帮助。但是如何呢？

假设 a = 4; b = 5;

我们必须证明 a 不等于 b。 但是，我想进一步扩展它，比如说，我们将显示哪个更大。 这里 b 更大。

- Zahid Hossain

---

你能否提供一个描述你问题的例子？ - SubOptimal

据我所知，这在像C这样的语言中是可能的，因为布尔值被表示为整数。但在Java中不行，因为你只能使用比较来获取布尔值。对整数使用位运算符始终只会得到一个整数。 - Codebender

Answer 1

您至少需要与0进行比较，这在本质上就是CPU执行比较的操作。例如：

相等可以被建模为^，因为位必须相同才能返回0。

(a ^ b) == 0

如果这是 C 的话，你可以省略 == 0，因为它可以被隐含。

!(a ^ b)

在Java中，如果你想将一个int转换为boolean，就必须至少进行一些比较操作。

通常使用减法来进行比较，但要考虑溢出的情况。

(long) a - b > 0 // same as a > b

减法就是加上一个负数，而负数可以用 ~x+1 表示，所以你可以这样做：

(long) a + ~ (long) b + 1 > 0

要删除+1，您可以将其更改为

(long) a + ~ (long) b >= 0 // same as a > b

您可以使用>> << & |和^一系列按位操作实现+，但我不会让您这么做。

- Peter Lawrey

---

这个答案有一些问题。首先，在C语言中，!(a ^ b)与(a ^ b) == 0在底层上是完全相同的。没有特殊的汇编命令可以执行!a。因此，您仍然需要进行比较。您关于从整数中获取布尔值需要比较是正确的，但实际上您可以在不使用比较的情况下获得0或1。请查看我的答案。 - Topa

对于 !a vs a==0，取自C文档第6.5.3.3节，表达式!E等同于(0==E)。 - Topa

Answer 2

正如Peter所提到的那样，你无法将1或0转换为bool，除非使用比较运算符。但仍然可以在没有比较运算符的情况下获得max。

我使用bit（1或0）而不是int，以避免混淆。

bit msb(x):
    return lsb(x >> 31)
bit lsb(x):
    return x &1

// returns 1 if x < 0, 0 if x >= 0
bit isNegative(x):
    return msb(x)

使用这些辅助工具，isGreater(a, b) 看起来像这样，

// BUG: bug due to overflow when a is -ve and b is +ve
// returns 1 if a > b, 0 if a <= b
bit isGreater_BUG(a, b):
    return isNegative(b - a)    // possible overflow

我们需要两个辅助函数来检测相同和不同的符号。

// toggles lsb only
bit toggle(x):
    return lsb(~x)

// returns 1 if a, b have same signs (0 is considered +ve).
bit isSameSigns(a, b):
    return toggle(isDiffSigns(a, b))
// returns 1 if a, b have different signs (0 is considered +ve).
bit isDiffSigns(a, b):
    return msb(a ^ b)

因此，通过修复溢出问题，

// returns 1 if a > b, 0 if a <= b
bit isGreater(a, b):
    return 
        (isSameSigns(a, b) & isNegative(b - a)) | 
        (isDiffSigns(a, b) & isNegative(b))

请注意，对于输入 5, 0 和 0, -5，isGreater 的工作也是正确的。

实现 isPositive(x) 要更加棘手，因为0 将被认为是正数。因此，不使用上述代码中的isPositive(a-b)，而是使用isNegative(b-a)，因为isNegative(x) 对于0 工作正常。

现在可以实现max如下：

// BUG: returns 0 when a == b instead of a (or b)
// returns a if a > b, b if b > a
int max_BUG(a, b):
    return
        isGreater(a, b) * a +   // returns 0 when a = b
        isGreater(b, a) * b     //

为了解决这个问题，使用辅助函数isZero(x)。

// returns 1 if x is 0, else 0
bit isZero(x):
    // x | -x will have msb 1 for a non-zero integer
    // and 0 for 0
    return toggle(msb(x | -x))

当 a = b 时，使用此修复方法：

// returns 1 if a == b else 0
bit isEqual(a, b):
    return isZero(a - b) // or isZero(a ^ b)

int max(a, b):
    return
        isGreater(a, b) * a +   // a > b, so a
        isGreater(b, a) * b +   // b > a, so b
        isEqual(a, b) * a       // a = b, so a (or b)

话虽如此，但是如果 isPositive(0) 返回1，则 max(5, 5) 将返回10而不是5。因此，一个正确的 isPositive(x) 实现应该是：

// returns 1 if x > 0, 0 if x <= 0
bit isPositive(x):
    return isNotZero(x) & toggle(isNegative(x))

// returns 1 if x != 0, else 0
bit isNotZero(x):
    return msb(x | -x)

- hIpPy

Answer 3

使用二进制补码表示法

int findMax( int x, int y)
{
 int z = x - y;
 int i  = (z  >>  31)  &  0x1;
 int  max  =  x - i  *  z;
 return max;
}

Reference: Here

- rhitz

---

你是在暗示你找到了一种避免首先进行比较的方法吗？ - Peter Lawrey

这不能判断两个值是否相等。 - Codebender

是的先生，这是第二部分的答案：“但是，我想进一步扩展它，比如说，我们将展示哪个更大”，而不进行比较。 - rhitz

Answer 4

a ^ b = c                    // XOR the inputs
                             //  If a equals b, c is zero. Else c is some other value

c[0] | c[1] ... | c[n] = d   // OR the bits
                             //  If c equals zero, d equals zero. Else d equals 1

注意：a，b，c是n位整数，d是一位。

- Jet Blue

Answer 5

Java中不使用比较运算符的解决方案：

    int a = 10;
    int b = 12;
    boolean[] bol = new boolean[] {true};

    try {
      boolean c = bol[a ^ b];
      System.out.println("The two integers are equal!");
    } catch (java.lang.ArrayIndexOutOfBoundsException e) {
      System.out.println("The two integers are not equal!");
      int z = a - b;
      int i = (z >> 31) & 0x1;
      System.out.println("The bigger integer is " + (a - i * z));
    }

- Jayanta Debnath

Answer 6

我假设你需要一个整数（0或1），因为你需要在Java中从整数获取布尔值进行比较。

这里有一个简单的解决方案，它不使用比较，而是使用减法，实际上可以使用位运算来完成（但不建议，因为在软件中需要很多周期）。

// For equality,
// 1. Perform r=a^b.
//    If they are equal you get all bits 0. Otherwise some bits are 1.
// 2. Cast it to a larger datatype 0 to have an extra bit for sign.
//    You will need to clear the high bits because of signed casting.
//    You can split it into two parts if you can't cast.
// 3. Perform -r.
//    If all bits are 0, you will get 0.
//    If some bits are not 0, then you get a negative number.
// 4. Shift right to extract MSB.
//    This will give -1 (because of sign extension) for not equal and 0 for equal.
//    You can easily convert it to 0 and 1 by adding 1 (I didn't include it in below function).
int equality(int a, int b) {
    long r = ((long)(a^b)) ^0xffffffffl;
    return (int)(((long)-r) >> 63);
}

// For greater_than,
// 1. Cast a and b to larger datatype to get more bits.
//    You can split it into two parts if you can't cast.
// 2. Perform b-a.
//    If a>b, then negative number (MSB is 1)
//    If a<=b, then positive number or zero (MSB is 0)
// 3. Shift right to extract MSB.
//    This will give -1 (because of sign extension) for greater than and 0 for not.
//    You can easily convert it to 0 and 1 by negating it (I didn't include it in below function).
int greater_than(int a, int b) {
    long r = (long)b-(long)a;
    return (int)(r >> 63);
}

小于（Less than）与大于（Greater）类似，但是你需要交换a和b。

趣闻：这些比较函数实际上在安全领域（密码学）中被使用，因为CPU的比较不是恒定时间的；也就是说，不安全防范计时攻击。

- Topa