在chinaunix.net看到这样一个帖子:两个int类型的数据,不用任何的判断语句如if、switch、?:等,找出其中的大值?
诸位大虾见仁见智,提出了很多好的思路。比较可行的,是用位运算和算术运算解决问题.
位运算是在位(bit)一级进行运算或处理.c++中的位运算符有~按位非,<<左移,>>右移,&按位与,^按位异或,|按位或,&=按位与赋值,^=按位异或赋值,|=按位或赋值.与或非的用法一般书上都有,笔者就不在这里唠叨了.值得注意的是右移运算.对于有符号数,在右移时,符号位将随同移动.当为正数时,最高位补0,而为负数时,符号位为1.
另外,我们知道int的范围是从-0x7fffffff到0x7fffffff.
那么让我们回到这个问题.不能使用判断语句,我们不得不使用位运算.我们设整型变量x,y.由于位运算的结果非0即1,那么,我们设定is_x,如果最大值是x,则为1,否则为0.x,y在去掉符号位后相减并右移31位,如果x大,则为1,否则为0.再将符号位代入去运算.这就是win_hate的想法.
zleil将想法变成了代码,如下:
#define MASK 0x7fffffff
int max (int x, int y)
{
int sx; // x的符号
int sy; // y的符号
int s; // x,y在去掉符号位后,如果x大,则s=1;否则为0
int is_x; // 如果最大值是x,则为1,否则为0
sx = x >> 31;
sy = y >> 31;
s = ((x&MASK) - (x&MASK)) >> 31;
is_x = ( (!(sx^sy)) & s ) | ( (sx^sy) & sy );
return is_x*x + (!is_x)*y;
}
真值表:
sx sy s is_x
0 1 * 1
0 0 s s
1 1 s s
1 0 * 0
当然还有很多解法,但都是基于位运算的,笔者就不一一描述了.
位运算很复杂,但很多时候它能给指出我们另一条路.熟悉位运算,也许它能在你找不到办法的时候给你指出一条道路.