（实验三）补码的加减法

1. 实验要求

用C/C++编程实现两个十进制整数（将其转换成补码）加、减运算结果，提示思想：模4补码进行计算

2. 相关知识点

机器字长全部假设为 8 位，只讨论整数，后不再特殊说明

0. 符号位

之前我们符号位都是用 1 位表示，模 4 补码是用 2 位表示，对应关系如下：

符号位	表示
00	正数
01	上溢
10	下溢
11	负数

特别提醒：补码运算符号位作为数的一部分参与运算

1. 补码加法

X + Y = [X] $_补 </annotation> </semantics> </math>$

符号位参与运算
如果有多出来的第三个符号位直接丢弃
运算结果也是补码
最终将运算结果转回真值

2. 补码减法

X - Y = [X] $_补 </annotation> </semantics> </math>$

规则同补码加法

3. 实现思路

0. 准备

包括：

检查输入是否合法，即第一个输入为"+“或”-"，其后输入为数字
确定输入十进制的正负
将输入的 string 转换为 int 类型

1. 转二进制

由准备工作准备好的 int 类型的数字直接转换为二进制，不过要注意两点，一是当数字为 0 时，取不到值，这时我们自己手动添个 0 上去，二是当数字为负数时，结果就很迷…解决方法是用其他变量暂存数字的绝对值

2. 转相反数的补码

和转补码类似，转的时候想到它的相反数

3. 实现加法

对于字符串来说，需要先把俩运算的字符串逆序，算出结果了再逆序一次，需要注意的地方就是注意保留进位和进位每次一起运算

3. 补码转真值

生成的结果可能会产生进位，比如 8 位 + 8 位 = 9 位，这种情况下最高位要丢弃，然后判断此时的符号位是 11 10 01 还是 00，10 和 01 的情况是溢出，11 为负，00 为正

但是有特殊情况，比如 [11101010] $_补 </annotation> </semantics> </math>$

4. 具体实现

#include<iostream>
#include<cmath> //abs
#include<malloc.h> //malloc
#include<algorithm> // reverse
#include<string> // string
#include<sstream> // stringstream
#define PLUS 1 // 正
#define MINUS -1 // 负
#define SYMBOLNUM 2 // 符号位长度
#define WORD_LENGTH 8 // 机器字长
#define MIN (-(1<<(WORD_LENGTH-SYMBOLNUM))) // 最小取值范围
#define MAX ((1<<(WORD_LENGTH-SYMBOLNUM))-1) // 最大取值范围
using namespace std;
typedef struct Integer *Number;
struct Integer{        // 定义一个结构体，把该数的各种码放进去
	string input;  // 输入的带符号十进制整数
	string binary;  // 二进制真值 X
	string yuan_code;   // 原码
	string between_bu_code;    // 二进制真值的相反数的补码 [-X]补
	string bu_code; // 补码 [X]补
	string yi_code;    // 移码
	int symbol;  // 符号位
	int decimal; // 十进制整数
};
/* 准备工作 1.检查输入是否合法 2.确定输入十进制数的正负 3.将 string 类型转换成 int 类型 4.确定输入十进制数的范围 */
void prepare(Number num){
	// 验证输入合法性，确定该十进制整数的正负
	for(int i=0;i<(num->input.size());i++){
		if(num->input[0]=='+' && !i){    // 如果第一个字符为 +
			num->symbol = PLUS;    // 记录符号为 +
		}else if(num->input[0]=='-' && !i){  //如果第一个字符为 -
			num->symbol = MINUS;   // 记录符号为 -
		}else if(!((num->input[i]>='0' || num->input[i]<='9') && i)){  // 如果不是第一个字符，且不在 0~9 之间
			cout<<"输入不合法，请重新启动！\n"<<endl;    
			exit(0);            // 提示并结束程序
		}
	}
	// 转换输入十进制整数的类型
	stringstream container;   // 转换容器
	container<<num->input.substr(1);      // "吞"进输入的十进制整数 
	container>>num->decimal;      // 再将容器中的数"吐"出来
	num->decimal *= num->symbol;  // 带上符号
	
	//确定输入十进制数的范围
	if(num->decimal < MIN || MAX < num->decimal){  // 如果取值比最小值还小，或者比最大值还大，说明超出表示范围了
		cout<<"超出表示范围，请重新启动！\n"<<endl;
		exit(0);     // 提示并结束程序
	}
}
// 转二进制
void tranfer(Number num){
	int tmpDecimal = abs(num->decimal); 
	// 特殊情况 0 
	// 如果 decimal 为 0，初始化字符串为 0，否则初始化为空
	num->binary=(tmpDecimal==0?"0":""); 
	while(tmpDecimal){
		num->binary += tmpDecimal%2+'0';
		tmpDecimal /=2;
	}
	reverse(num->binary.begin(),num->binary.end());  // 逆转字符串
}
// 转换成原码
void ToYuan_code(Number num){
	// 如果输入的是MIN，只有补码能表示，原码置为 ——
	if(num->decimal == MIN){
		num->yuan_code = "——";
		return;
	}
	// 确定原码符号位
	if(PLUS == num->symbol)   // 如果为正，符号位为 00
		num->yuan_code += "00";
	else     // 否则符号位为 1
		num->yuan_code += "11";
	//确定原码数值位
	num->yuan_code += num->binary;  // 原码数值位和二进制相等
	//补充中间的 0
	while(num->yuan_code.size() < WORD_LENGTH)   
		num->yuan_code.insert(SYMBOLNUM,"0");   // 在符号位后面追加 0
}
// 转换补码
void ToBu_code(Number num){
	if(num->symbol == PLUS){    // 如果是正数，补码 = 原码
		num->bu_code = num->yuan_code;
		return;
	}

	// 如果输入的是MIN，只有补码能表示
	if(num->decimal == MIN){
		num->bu_code += "11";
		while(num->bu_code.size() < WORD_LENGTH)
			num->bu_code.insert(1,"0");   // 在符号位后面追加 0
		return;
	}
	//确定数值位
	bool flag = true;
	for(int i=num->yuan_code.size()-1;i>=SYMBOLNUM;i--){ //从低到高位
		if(num->yuan_code[i]=='1'){   
			if(flag){   // 当第一次遇到 1 时，改变标记值，
				num->bu_code +="1";
				flag = false;
			}
			else
				num->bu_code +="0";
		}else{   // 0
			if(flag)
				num->bu_code +="0";
			else
				num->bu_code +="1";
		}
	}
	reverse(num->bu_code.begin(),num->bu_code.end());  // 逆转数组
	
	//确定符号位
	if(num->decimal)   // 只要不是刚好 -0
		num->bu_code.insert(0,"11");
	else
		num->bu_code.insert(0,"00");
}
// 转换负的补码
void ToBetweenBu_code(Number num){
	if(num->symbol == MINUS){    // 如果是负数，负的补码为正
		num->between_bu_code ="00" + num->yuan_code.substr(SYMBOLNUM);
		return;
	}

	//确定数值位
	bool flag = true;
	for(int i=num->yuan_code.size()-1;i>=SYMBOLNUM;i--){ //从低到高位
		if(num->yuan_code[i]=='1'){   
			if(flag){   // 当第一次遇到 1 时，改变标记值，
				num->between_bu_code +="1";
				flag = false;
			}
			else
				num->between_bu_code +="0";
		}else{   // 0
			if(flag)
				num->between_bu_code +="0";
			else
				num->between_bu_code +="1";
		}
	}
	reverse(num->between_bu_code.begin(),num->between_bu_code.end());  // 逆转数组
	
	//确定符号位
	if(num->decimal)   // 只要不是刚好 -0
		num->between_bu_code.insert(0,"11");
	else
		num->between_bu_code.insert(0,"00");
}
// 补码转真值
void bu_code2true_value(string result){
	// 去掉多余的位数（也许进位产生了 3 位符号位）
	reverse(result.begin(),result.end());  // 先逆序
	result = result.substr(0,8);   // 从 0 开始，截取 8 位 
	reverse(result.begin(),result.end());  // 再逆转回去
	
	string true_value;  // 真值
	// 提取符号位
	string symbol = result.substr(0,2);

	// 判断符号位
	if(symbol=="11"){  // 如果为 11，真值为负
		bool flag = true;
		for(int i=result.size()-1;i>=SYMBOLNUM;i--){ //从低到高位
			if(result[i]=='1'){   
				if(flag){   // 当第一次遇到 1 时，改变标记值，
					true_value +="1";
					flag = false;
				}
				else
					true_value +="0";
			}else{   // 0
				if(flag)
					true_value +="0";
				else
					true_value +="1";
			}
		}
		reverse(true_value.begin(),true_value.end());  // 逆转数组
		 
		// 如果此时真值全为 0，真值又是负，只可能是溢出到 -2^(机器字长-符号位长)，根本存不下
		string tmp="";
		while(tmp.size() < WORD_LENGTH-SYMBOLNUM)
			tmp += "0";
		if(true_value == tmp){
			cout<<"溢出"<<endl;
			return;
		}
		// 否则其他情况下才可能是个正常负值
		true_value.insert(0,"-");  // 最前面插入负号
	}
	else if(symbol=="10" || symbol=="01"){  // 如果为 01 或者 10，则溢出
		cout<<"溢出"<<endl;
		return;
	}
	else if(symbol=="00")
		true_value = "+"+result.substr(2);
	// 把数值前面多余的0去掉
	for(int i=1;i<true_value.size();i++)
		if(true_value[i]=='1'){  // 第一次遇到 1，切到前面的 0 
			true_value =true_value[0]+true_value.substr(i);
			break;
		}
	cout<<true_value<<endl;
}
// 实现加法，如果 on 为 ture，[x+y]补，否则 [x-y]补
void Add(string x,string y,bool on){
	string result = "";   // 暂存结果 result = [x]补 + [y]补
	
	// 逆序为求和做准备
	reverse(x.begin(),x.end());
	reverse(y.begin(),y.end());

	int flag = 0;   // 记录进位
	for(int i=0;i<WORD_LENGTH;i++){
		if(x[i]-'0' + y[i]-'0' + flag >=2){  // 如果和大于等于 2，进位为 1
			result += (x[i]-'0' + y[i]-'0' + flag)%2 +'0';
			flag = 1;
		}else{
			result  += x[i]-'0' + y[i]-'0' + flag + '0';
			flag = 0;
		}
	}
	if(flag)
		result +="1";
	// 最后结果逆序
	reverse(x.begin(),x.end());
	reverse(y.begin(),y.end());
	reverse(result.begin(),result.end()); 

	cout<<" "<<x<<" [x]补"<<endl;
	cout<<"+ "<<y<<" "<<(on?"[y]补":"[-y]补")<<endl;
	cout<<"----------------"<<endl;
	cout<<" "<<(flag?"":" ")<<result<<" "<<(on?"[x+y]补":"[x-y]补")<<endl;
	cout<<"即 x+y =";
	bu_code2true_value(result);
}
int main(){
	Number X = new Integer();
	Number Y = new Integer();
	cout<<"请输入"<<MIN<<"~+"<<MAX<<"范围内的带符号十进制整数：";
	cin>>X->input;
	cout<<"请输入"<<MIN<<"~+"<<MAX<<"范围内的带符号十进制整数：";
	cin>>Y->input;
	prepare(X);  // 准备
	tranfer(X);  // 转换为二进制
	ToYuan_code(X);    // 转换原码
	ToBu_code(X);    // 转换补码 [X]补
	prepare(Y);  // 准备
	tranfer(Y);  // 转换为二进制
	ToYuan_code(Y);    // 转换原码
	ToBu_code(Y);    // 转换补码 [X]补
	ToBetweenBu_code(Y);   // 转换负的补码 [-X]补 
	Add(X->bu_code,Y->bu_code,true);   // 实现加法
	cout<<endl;
	cout<<endl;
	cout<<endl;
	Add(X->bu_code,Y->between_bu_code,false);  // 实现减法
	free(X);
	free(Y);
	return 0;
}