发表于 更新于 分类于 ， 本文字数： 335 阅读时长 ≈ 1 分钟

\(2.3.\)Binary Arithmetic

1.Negative number representation

  For a negative number \(x\), we use \(2^n - x\) to represent it.

  • \(e.g.\)-4 is represent as 1100 in four-bit binary number, also equal to 16-4=12.

  In order not to mistake this representation with positive number, we prescribe that a positive number cannot use the left-most bit to represent number.

2.Binary addition

  Before discuss the numerical addition, we first take a look at the bit-to-bit addition. We use the folloing API to deal with the carry: 

1
2
3
4
5
6
7
CHIP AddBit {
	IN a, b;
	OUT out, carry;

	PARTS:
	......
}

  After the implementation, for a number, we just need to do AddBit for each bit of it.

\(p.s.:\)How do we deal with the following 4-bit addition1000 + 1100?   The answer is 0100. This is because the left-most bit addition gets a carry, but it is out of the bit range. This is called integer overflow. When facing this, the computer will do \(\mod 2^n\) to the true result, where \(n\) is the bit number.

\(p.s:\)By the integer overflow theory, we can prove that the simple positive addition also suits negative numbers.

\(proof:\)Assume there are two negative number \(x,y\), they are represented as \(2^n-x,2^n-y\). Add them together, and we get \(2^{n+1}-x-y\). The result apparently overflow the range, so\(\mod 2^n\), and we get \(2^n - x - y\). This is the binary representation of \(-x-y\), \(QED\).

3.Binary subtraction

  To do subtraction, we just need to add a number's negation. We know that \(-x\) is represented as \(2^n-x\). Let's do some transformation like:

\[(2^n-1)-x+1\]

  Why this? Notice that \(2^n-1\) is 1111, and it's easy to subtract other number, for carry will never occur in this instance. For \(+1\), since we have implement addition, it's also easy.