前言
前几天做算法题时遇到一个数值比较问题，我上网查了许久，补了一下计算机组成原理的原反补码、有无符号、溢出和汇编的比较指令的基础知识，并在知乎上看到一位大佬的解题思路，然后完成了只考虑无溢出比较时的代码。
如果有和我一样需要补基础知识的小伙伴可以参考我写的同系列的文章如何使用➕、➖和位运算符进行数值比较（二），想了解有溢出比较的小伙伴可以参考如何使用➕、➖和位运算符进行数值比较（三）。
一、题目
- Description
输入两个整数，输出较大的值。
- Input
输入两个整数，中间用空格间隔。
- Output
输出较大的值。
| Sample Input | Sample Output |
|---|---|
| 10 20 | 20 |
| 1 -1 | 1 |
| 5 5 | 5 |
- Hint
注意：要求只能使用+、-、<<、>>、&、|、^、~，不能使用条件选择语句、? : 及比较运算符
二、问题分析
不能直接使用比较运算符，只能另觅他法。其实，仔细一想：无论使用什么运算符，在硬件层面，都会转化为最本质的布尔运算，所以一定可以使用位运算实现整数比较。
此时，我们往下一层想：汇编语言的比较指令（CMP）是如何实现的？这里是不是可以根据汇编CMP的原理对数据进行比较呢？
这里为什么说要想到汇编语言上呢，是因为我们现在用的c编译器，无论GCC还是VC6 的cl.exe，都是将c语言代码编译成汇编语言，然后再用汇编器将代码汇编成机器码。所以如果你能搞清楚汇编，就相当于从根本上明白了c，而且，如果用机器的思维去考虑问题，必须用汇编。这样的话，如果碰见比较奇怪的c语言问题就可以把他编译成汇编语言去看。（我一般接触到的用c的大佬都是说他是汇编和c的方向。）
所以根据汇编语言实现比较的原理，不考虑溢出时，可以得出一个思路：
- 让需要比较的两个数据x,y相减，得出差z，然后通过某些标志位对z进行判断。如：标志位为0，则表示z>=0，x>=y，输出较大值x；标志位为1，则表示z<0，x<y，输出较大值y，即0=>x，1=>y。如何实现呢？
- 使用位运算符得出表达式：(z & y) | ((~z) & x))（这里如果借助门电路理解起来会不会容易些）
门电路
那这个标志位该怎么获得呢？
- 大概看出这个标志位与x的符号位可以有所联系，z>=0时符号位是0，z<0时符号位是1。
（巧了吗这不是）但应该怎么获取符号位呢？ - 符号位是差值z二进制表示的最高位，可以使用位运算
int t = z&0x8000 0000
获取到符号位，由于需要的标志位是0或1，所以还需要将t右移31位。
t >>= 31;
- 使用获取到的符号位（即标志位）与x、y进行(z & y) | ((~z) & x))运算，最终输出较大的数值。
三、C语言实现
#include<stdio.h>
int main() {
//无溢出比较，即被比较的两个数差值较小，不会有溢出的情况产生
int x, y;
scanf("%d %d", &x, &y);
int z = x - y;
int t = z & 0x80000000; //取差值的符号位
t >>= 31; //对符号位进行处理
printf("%d", (t & y) | ((~t) & x));
return 0;
}
下面是知乎大佬的代码，思路、代码和注释都很清晰，原文链接在参考处：
int choose(int x,int y,int s){
/*
* s = 0x0 => return x
* s = 0xFFFF FFFF => return y
*/
return ( s & y ) | ( (~s) & x );
}
void modify(int *x){
/*
* t = 0 ==> t = 0
* t = 0x8000 0000 ==> 0xFFFF FFFF
*/
int t = *x;
t >>= 1;
t >>= 2;
t >>= 4;
t >>= 8;
t >>= 16;
*x = t;
}
int basic_compare(int x, int y,int *larger,int *smaller){
/*
* 不考虑溢出
* 若 x >= y,返回 x
* 若 x < y,返回 y
*/
/*
* z >= 0 ==> x-y >= 0 即 x >= y
* z < 0 ==> x-y < 0 即 x < y
*/
int z = x - y;
/*
* 取出z的符号位，符号位在最高位
* 0x8000 0000应该随着int的寄存器长度改变而改变
* z >= 0 ==> t = 0
* z < 0 ==> t = 0x8000 0000
*/
int t = z & 0x80000000;
/*
* t = 0 ==> t = 0
* t = 0x8000 0000 ==> 0xFFFF FFFF
*/
modify(&t);
/*
* 综上所述,
* x >= y <==> t = 0
* x < y <==> t = 0xFFFF FFFF
*/
/* 输出比较中的大值,(t & y) | ((~t) & x) */
*larger = choose(x,y,t);
/* 输出比较中的小值,(t & x) | ((~t) & y) */
*smaller = choose(x,y,~t);
}
四、运行效果
运行效果1
运行效果2
以上就是全部的思路，整理不易，转载请注明出处~
