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

我需要使用Bit运算符比较两个整数。 我遇到了一个问题，我必须比较两个整数而不使用比较运算符。使用位运算符会有所帮助。但是如何？

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

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

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 

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

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

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

正确实现isPositive(x) 更为棘手 ，因为0也将被视为正数。 因此，不使用isPositive(a - b) ，而是使用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) 

Answer 3

使用二进制二进制补码表示法

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

参考： 这里

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