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

Question

我需要使用位运算符比较两个整数。我遇到了一个问题，我必须在不使用比较 operator.Using 位运算符的情况下比较两个整数 help.But 怎么办？

让我们说一 = 4; b = 5;

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

Answer 1

您至少需要与 0 进行比较，理论上这就是 CPU 所做的比较。例如

等于可以建模为 ^ 因为位必须与 return 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

您可以将 + 实现为使用 >> << & | 和 ^ 的一系列逐位操作，但我不会对你造成这种影响。

Answer 2

使用二进制补码表示法

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

参考：Here

Answer 3

如果没有像 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))

请注意，isGreater 也适用于输入 5, 0 和 0, -5。

更棘手 正确实施 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) returns 1 那么 max(5, 5) 将 return 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)

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是位

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));
    }

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);
}

小于等于大于，但你交换了 a 和 b。

琐事：这些比较函数实际上用于安全（密码学），因为CPU比较不是恒定时间的；又名不能抵御定时攻击。

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

Compare two integers using bit operator

java

integer

使用二进制补码表示法