牛逼的二进制

1.前言

计算机使用二进制来表示所有形式的数据:颜色、文字、图像等。当前辈们想方设法要造一台计算机时都会遇到一个问题:怎么用电来表示数? 显然他们发现开关的开和关正好对应二进制的0和1，然后计算机就使用二进制直到如今。

那计算机怎么使用二进制表示负数呢?怎么表示小数?怎么进行运算呢?

2.用二进制表示负数

由于二进制不能表示负数，所以必须使用正数来表示负数，将最高位当符号位使用，0正1负，这样就可以使用加法来进行减法运算。

而补数就是用正数表示负数，一个正数的补数就是它的负数，所以二进制数与它的补数相加结果必为0。

获得补数的方法是将二进制数取反加一。

注意：运算结果是负数时，也是用补码来表示。将其返回到源码再在前面加负号就是运算结果。

3.用二进制进行乘法和除法

二进制进行乘除是使用移位运算，将二进制数总体进行左移或右移。

• 左移：移动后空出来的最低位补0：
  

• 右移分为逻辑右移和算数右移，逻辑右移移动后空出来的最高位补0，例如霓虹灯;算术右移移动后空来的最高位补移位之前符号位的值。
  
  此外，移位后最高位和最低位多出的数字直接丢弃。左移就是乘2的倍数，右移就是除以2的倍数。

4.符号扩充

以8位的二进制数为例，符号扩充指在保持值不变的前提下，使用16或32位来表示这个进制数，方法很简单，只需要用符号位的值填充最高位。

5.用二进制数表示小数

先来看两个问题：

1.将二进制数1011.0011转换成十进制：

2.小数点后四位的二进制可以表示的十进制有哪些：

由图可知二进制数是连续的，十进制不连续，中间的十进制数都无法用二进制表示。比如十进制的0.1转換成二进制是一个循环小数，计算机遇到这种循环小数时会根据数据类型进行截断或者四含五入。例如float会保存小数点后六位。这也是计算机进行小数运算时容易出错的原因，可以使用整数代替小数运算再复原的方法来解决这个问题。

6.小数的存储方式：浮点数

浮点数指用符号、位数、基数和指数来表示小数。由于计算机使用二进制，基数固定为2。

浮点数在内存上是这样存储的：

尾数部分使用正则表达式表示，指数部分使用“EXCESS”系统表示。

1)正则表达式

二进制数中使用的是将小数点前的值固定为1的正则表达式。就是将小数点左移或右移，使得左边有且只有一个1。由于第一位肯定是1，在内存上就可以不存，节省了一个数据位。

2)“ EXCESS”系统

因为指数部分也可能是负数，为了不使用符号位，前辈们创造出 “EXCESS”系统。通过将指数部分表示范围的中间值设为0，用正数表示负数。比如八位二进制最大值为255，即用127表示0，126就为-1，128为1。

7.说明

本文为《程序是怎样跑起来的》读书笔记，如有错误，请兄弟们指正，大家一起进步!

    微处理器用二进制补码系统表示有符号整数，因为它可以将减法运算转换为对减数的补数的加法运算。

1.什么是二进制补码运算

    我们先引入补数的概念：

补数：一个数与它的补数之和是一个常数。例如一个一位的十进制数与它的补数之和总是9，2的补数是7，4的补数是5。在n位的二进制算术中，数P的补数Q=-Q（即常数是）。 

    令n位二进制数N的二进制补码定义为-N。如果N=5=00000101（8位二进制数），则N的补码为-00000101=100000000-00000101=11111011（注意此处11111011用于表示5的补码，不要看成无符号整数）。

    下面看几个例子：

5：00000101，5的补码：11111001   

7：00000111，7的补码：11111001

    例1：将7与5的补数相加

00000111 + 11111011 = 1000000010

    结果为9位二进制数100000010。由于一共只有8位，我们忽略最左边一位，结果为00000010，也就是2。即7与5的补数相加结果为2，效果等同于7-5=2。

    例2：将7的补数与5相加

11111001+00000101=111111110

    结果为9位二进制数111111110，忽略最左边第九位后结果为11111110，“刚好”是二进制2的补码（-00000010=11111110），也就是5-7=-2。

    从上述例子看，在二进制运算中，对于正数N而言，减去N的操作和加上N的补数的操作效果是相同的，也就是说-N等价于N的补数。

    那么，为什么要引入补码运算呢？ 

2.用补数的加法代替减法   

    二进制补码算术不是魔术，具体展开看，在n位的二进制算术运算中，我们令Z=X-Y，我们试着用X加上Y的补数来运算，由于Y的补数为-Y，所以

X+Y的补数=X+(-Y)=+(X-Y)=+Z

    换句话说，我们用X加上Y的补数会得到Z加上，但只体现在最左边的第n+1位（如同上述例子中第九位的1），会被丢弃掉。所以此时我们得到了Z=X-Y=X+Y的补数，也就是说，在二进制补码运算中，减去一个数，等同于加上这个数的补码。

    到这里，我们可以进一步直接放心地在二进制补码运算中用一个数的补码来表示这个数的负数了，如果不放心，我们还可以证明，对一个数进行两次求补将得到这个数本身：例如

-5=-00000101=11111011

再次求补：-(-5)=-11111011=00000101=5

    我们考虑加法的所有情况，请看下面的实例。令

X=9=0000101, -X=11110111

Y=6=00000110, -Y=11111010

    此时有

X+Y=00000101+00000110=00000111=15

X-Y=00001001+11111010=100000011=3（红色最高位舍弃）

-X+Y=11110111+00000110=111111101=-3（3的补码）

 -X-Y=11110111+11111001=111110001=-15(15的补码)

    结合之前所有的论证， 上述所有4中加减法中的情况都正确得到了我们想要的结果，例如将6与9的补码相加完成运算-9+6，得到-3，确实是3的补码。

3.求补运算

    我们现在可用补码加法来代替减法了，但是，例如N的补码是-X，我们求补的操作本身不就是一次减法吗？！别急，补码运算可没这么蠢，求补的运算是非常简单的。我们将表达式-X表示为下面的形式：

    例如，8位（n=8）时有

    表达式111...1-X的值很容易计算。对于X的第i位，如果=0，则1-0=1，同样，若

=1，则1-1=0，很显然，取 的反就行了，换句话说计算111...1-X部分的值只需要将X每一位取反。可见计算X的补码非常容易：

计算数N的补码，所要做的就是将X的每一位取反，然后将取反结果加1。

    例如，对于二进制的6=00000110，6的补码为11111001+1=11111010。

    这种补码运算相对于减法来说，非常适合用硬件实现，效率也很高。

4.补码的特点

1. 补码是一个真正的互补系统+X+(-X)=0;
2. 补码0被表示为00...0，是唯一的；
3. 补码的最高位为符号位，如果符号位为0，则该数为正；符号位为1，则该数为负；
4. n位二进制补码数的表示范围为(-)~​(​​​​​​-1)，例如对于n=8，补码的范围为-128~127.共有=256个不同的数（128个负数，1个0，127个正数）；
5. 补码加法和减法可以使用同样的硬件完成，因为补码减法由被减数加上减数的补数实现。

 5.运算溢出

     n位二进制补码数的表示范围为 (-)~​(​​​​​​-1)。如果运算结果位于这个范围之外会发生什么呢？

    我们令5位有符号二进制补码数的表示范围为-16~+15，考虑下面的例子：

    情形1：5+7=00101+00111=01100=12

    情形2：12+13=01100+01101=11001=-7

    在情形1中，我们得到了期望的结果+12，但在情形2中，我们得到的结果是一个负数，因为它的符号位是1，如果将他视作无符号整数，它将是，但是我们不可能将两种解释应用到一个表示方法中，所以一旦采用了补码表示，那么11001就只能表示-7。

    同样，如果两个负数相加且结果小于-16，也会超出5位二进制补码的表示范围。

    情形3：-9-12=10111+10111=101011

    在情形3中，第六位1舍弃后，结果为正数01011=11。

    这两个例子都说明了什么是运算溢出，它发生在补码加法当两个正数的和为负数，或两个负数的和为正数的时候。也就是说，如果操作数A和操作数B的符号位相同，但结果的符号位与它们不同的时候，则可以判定发生了溢出。

十进制转二进制补码

首先要明确的是：十进制直接转成二进制是转化为二进制原码，正数的原码和补码相同，但负数的原码按位取反末位加一才是补码。
因此流程图大概如下：

整个代码我贴在最后

主要逻辑代码：

public static String convert(int num) {
		StringBuilder resultString = new StringBuilder();
		// 初始化补码数组，共12位
		String[] complementStrings = new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" };
		boolean ifNegative = false;
		if (num < 0) {
			complementStrings[0] = "1";
			num = -num;
			ifNegative = true;
		}
		// 加入到补码的数组中，开头从12-strings.length开始
		String[] strings = Integer.toString(num, 2).split("");
		// 对应在strings数组中的下标
		int j = 0;
		for (int i = 12 - strings.length; i < 12; i++) {
			complementStrings[i] = strings[j];
			j++;
		}
		// 如果为负数，先全部取反,否则直接拼接
		if (ifNegative) {
			for (int i = 1; i < complementStrings.length; i++) {
				if (complementStrings[i].equals("1")) {
					complementStrings[i] = "0";
				} else {
					complementStrings[i] = "1";
				}
			}
			// 送进函数加一
			resultString.append(binaryPlusOne(complementStrings, 11, 1));
		} else {
			resultString.append(strings.toString());
		}
		return resultString.toString();
	}

重要代码1：末位加一

为递归算法,递归逻辑为每次将一位执行与进位的加法并拼接，走完整个数组，返回。

	/**
	 * 
	 * @param strings 二进制数数组
	 * @param temp 对哪一位执行加法
	 * @param carry 进位值
	 */
	private static String binaryPlusOne(String[] strings, int temp, int carry) {
		if (temp < 0) {
			StringBuilder tempBuilder = new StringBuilder();
			for (int i = 0; i < strings.length; i++) {
				tempBuilder.append(strings[i]);
			}
			return tempBuilder.toString();
		} else {
			// 计算加上进位后的值
			int tempInt = Integer.parseInt(strings[temp]) + carry;
			// 更新对应位置上的值
			strings[temp] = String.valueOf(tempInt % 2);
			// 更新进位
			carry = (tempInt) / 2;
			// 更新坐标
			temp--;
		}
		return binaryPlusOne(strings, temp, carry);
	}

二进制转16进制

同样也是递归的思想，每次将二进制字符串最后四位进行转化，并拼接，知道拼完为止。

重要代码

	/**
	 * 将二进制转为16进制
	 * 
	 * @param binaryString
	 * @param length
	 * @return
	 */
	private static String binaryTo16(String binaryString, int length) {
		if (length < 4) {
			return binaryString;
		}
		return binaryTo16(binaryString.substring(0, length - 4), length - 4)
				+ binaryTo16Map.get(binaryString.substring(length - 4, length));
	}

总体代码，粘了就能用

输入为一个十进制数（其二进制位数在12位以内）
输出为 12位二进制补码和二进制补码对应的16进制码的拼接（以分号隔开）

示例：

输入：-7
输出：111111111001;FF9

import java.util.HashMap;

public class BinaryCodeTransfer {
	public final static int totalNumber = 12;
	public final static HashMap<String, String> binaryTo16Map = new HashMap<String, String>() {
		{
			put("0000", "0");
			put("0001", "1");
			put("0010", "2");
			put("0011", "3");
			put("0100", "4");
			put("0101", "5");
			put("0110", "6");
			put("0111", "7");
			put("1000", "8");
			put("1001", "9");
			put("1010", "A");
			put("1011", "B");
			put("1100", "C");
			put("1101", "D");
			put("1110", "E");
			put("1111", "F");
		}
	};

	public static void main(String[] args) {
		System.out.println(convert(-7));
	}

	public static String convertToBase72(int num) {

		return Integer.toString(num, 2);
	}

	public static String convert(int num) {
		StringBuilder resultString = new StringBuilder();
		// 初始化补码数组，共12位
		String[] complementStrings = new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" };
		boolean ifNegative = false;
		if (num < 0) {
			complementStrings[0] = "1";
			num = -num;
			ifNegative = true;
		}
		// 加入到补码的数组中，开头从12-strings.length开始
		String[] strings = Integer.toString(num, 2).split("");
		// 对应在strings数组中的下标
		int j = 0;
		for (int i = 12 - strings.length; i < 12; i++) {
			complementStrings[i] = strings[j];
			j++;
		}
		// 如果为负数，先全部取反,否则直接拼接
		if (ifNegative) {
			for (int i = 1; i < complementStrings.length; i++) {
				if (complementStrings[i].equals("1")) {
					complementStrings[i] = "0";
				} else {
					complementStrings[i] = "1";
				}
			}
			// 送进函数加一
			resultString.append(binaryPlusOne(complementStrings, 11, 1));
		} else {
			resultString.append(strings.toString());
		}

		// 如果大于零直接求出十六进制，否则，放入16进制处理函数中
		resultString.append(";").append(binaryTo16(resultString.toString(), 12));
		return resultString.toString();
	}

	/**
	 * 
	 * @param strings
	 * @param temp
	 * @param carry
	 */
	private static String binaryPlusOne(String[] strings, int temp, int carry) {
		if (temp < 0) {
			StringBuilder tempBuilder = new StringBuilder();
			for (int i = 0; i < strings.length; i++) {
				tempBuilder.append(strings[i]);
			}
			return tempBuilder.toString();
		} else {
			// 计算加上进位后的值
			int tempInt = Integer.parseInt(strings[temp]) + carry;
			// 更新对应位置上的值
			strings[temp] = String.valueOf(tempInt % 2);
			// 更新进位
			carry = (tempInt) / 2;
			// 更新坐标
			temp--;
		}
		return binaryPlusOne(strings, temp, carry);
	}

	/**
	 * 将二进制转为16进制
	 * 
	 * @param binaryString
	 * @param length
	 * @return
	 */
	private static String binaryTo16(String binaryString, int length) {
		if (length < 4) {
			return binaryString;
		}
		return binaryTo16(binaryString.substring(0, length - 4), length - 4)
				+ binaryTo16Map.get(binaryString.substring(length - 4, length));
	}
}