logo标签列表

不使用任何比较操作符比较两个整数

c++if-statementcomparison
12

是否有可能在没有比较的情况下找到两个整数中最大的那个？我找到了一些解决方案：

if(!(a/b)) // if a is less than b then division result will be zero.
{
    cout << " b is greater than a";
}
else if (!(a-b)) // we know a is greater than or equal to b now.  check whether they are equal.
{
    cout << "a and b are equal";
}
else
    cout << "a is greater than b";

但是 if(c) 或者 if(!c) 是与零进行比较。此外，它不适用于负数。事实上，我需要一种避免任何 if 语句的解决方案。相反，我应该使用 switch 语句和算术运算符。谢谢。

11
这就是为什么今天学校教授的大部分编程知识都是无用的。 - Lasse V. Karlsen
2
@LasseV.Karlsen 实际上，在没有硬件条件移动的时候，这是一个有用的加速技巧。我不记得现在GPU是否支持它们，所以可能仍然有必要使用它。在评估无知时要小心 :) - Quartz
除了作为“学校”编程问题外，这也是编程面试中非常常见的问题 - 当他们想要看看你的思维方式时。 - azec-pdx
2
@LasseV.Karlsen：这不是关于学习如何在没有比较的情况下比较两个整数。而是关于学习如何思考问题。非常有用。 - Lightness Races in Orbit
15个回答
43
2
同意最后一句话。如果这对你的平台是一个好主意，编译器应该为你执行此优化 :) - Laserallan
b ^ ( (((a-b)>>(sizeof(a)*8-1) & 1) - 1) & (a^b)) 我原本想说，计算机科学课程应该深入到编译器以下，但是许多CPU架构都已经有了MAX和MIN指令。 - Pete Kirkham
比较一下这个 Stack Overflow 的问题：https://dev59.com/7HVC5IYBdhLWcg3wpSzf - plinth
@Laserallan 或许这些学生最终会编写优化的编译器？ - user1630889
那么他们肯定需要知道它。我不喜欢在生产代码中使用它，因为优化很可能与架构有关，而且在我看来可读性更差。 - Laserallan
4
这是一个有趣的位操作版本，它没有任何条件分支。
int g = (int)"greater";
int l = (int)"less";
int e = (int)"equal";

int a = 7;
int b = 10;

char *result = (char*)((((a - b) >> 31) & l) | (((b - a) >> 31) & g) | ((~((a - b) | (b - a))) >> 31) & e);
cout << result;
2

您可以利用计算a - b的符号取决于哪个数更大的事实。这在许多比较的实现中被使用。但我相信您永远无法完全避免比较。在这种情况下，您仍然至少需要评估处理器上标志的内容。

如果您只需要显示较小的数字，还可以使用算术技巧：

result = ((a + b) - sqrt((a - b) * (a - b))) / 2

编辑 嗯...你可以使用switch吗？

我应该使用switch语句和算术运算符。

switch基本上与链式的if相同，因此它也使用比较。这听起来好像确实只需将a-b与零进行比较即可确定其符号。

1
char c;
c=0x3D + (!(b/a) && (a-b)) - (!(a/b) && (a-b));
printf("a %c b",c);
1

在问题中提供的示例和迄今为止的任何答案都没有保护免受除以零的影响。你到底为什么要避免使用“if”语句？我怀疑这是关于 ?: 运算符的作业问题。

cout << "Maximum is: " << ((a>b)?a:b)

我们开始吧。

没有比较就不可能比较两个数字。你可以欺骗一下，进行间接操作，但归根结底你还是在比较某些东西。相信编译器优化代码并选择最佳操作。

三元运算符是一种短压缩运算符 ;) - Alejandro
1
作为一个毫无意义的练习，这里有一种实现cond函数的方法 - 以替代if，假设它（还有switch和?:）从语言中消失了，并且您正在使用C++0x。
void cond(bool expr, std::function<void ()> ifTrue, std::function<void ()> ifFalse)
{
    std::function<void ()> choices[2] = { ifTrue, ifFalse };
    choices[expr == false]();
}

例如

cond(x > y,
    /*then*/ [] { std::cout << "x is greater than y"; },
    /*else*/ [] { std::cout << "x is not greater than y"; });

就像我说的，毫无意义。

哈哈！考虑到kvphxga似乎是个新手，这个回答真的很有趣！ :) - avp
'==' 是一个比较运算符。 - rich.e
@reakinator - 不是，它是等于运算符。然而，>是一个比较运算符，在这个答案中也出现了。 - Daniel Earwicker
好的，我来改一下措辞：“a == b”是在比较a和b。好了，别再抨击了，他已经说过这样做毫无意义了。 - rich.e
等号运算符是一种比较运算符，为什么我还在质疑这个问题我也不知道。 - rich.e
0

我认为这种方法比其他方法更好，你可以在C和Java两种编程语言中使用这个逻辑，但是int应该是4字节，如果int是2字节，则将右移15字节而不是31字节。

enter code here

#include<stdio.h>

main()
{
   int a, b;
   printf("Enter three numbers\n");
   scanf("%d %d", &a, &b);
   printf("Largest number is %d \n",findMax( a,b ));
}
int findMax( int x, int y)
{
  int z = x - y;
  int i  = (z  >>  31)  &  0x1;
  printf("i = %d shift = %d \n", i, (z>>31));
  int  max  =  x - i  *  z;
  return max;
}
0

我真的看不出来为什么要这样做：谁会想在编程中没有 "if" ？

一个可能的答案是：

( ( a + b ) + abs ( a -b ) ) / 2

我猜 "abs" 只是把 "if" 隐藏了起来，就像三元运算符只是另一个名字的 "if" 一样...

4
第一个问题的答案是使用高度管道化或SIMD机器的人，分支会带来麻烦。 - Charlie Martin
0
奇怪的想法：使用函数指针数组。然后通过一些算术和位运算得到该数组的索引。
0
假设X和Y是两个输入。 当X>Y时，结果为：((X+Y)+ abs(X-Y))/2 当X
现在你可以从#include中获取abs()函数，它实际上返回绝对值。
祝好！
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接