Integer Representation¶
Why Binary?¶
Storing in base 3, or higher, would allow us to compress more numbers in less electronic components, but it means each digit has more possible values, leading to a higher noise margin.
Unsigned Integer¶
\((100)_{10} = (0110\_0100)_{2u}\)
\((019)_{10} = (0001\_0011)_{2u}\)
- Conversion from binary to decimal can be done via polynomial expansion.
- Conversion from decimal to binary can be done via repeated division.
Range of Representation - with \(n\) bits, we can represent integers in the range \([0, 2^n)\). This can be verified by the cardinality of this set being \(2^n\).
Sign Magnitude¶
\((-5)_{10} = -(101)_{2u} = ([1]101)_{2s}\)
\((+5)_{10} = +(101)_{2u} = ([0]101)_{2s}\)
- Conversion from binary to decimal and vice versa can be done by treating the non-sign bits as an unsigned integer, and then applying the sign.
Range of Representation - with \(n\) bits, we can represent integers in the range \((-2^{n-1}, 2^{n-1})\). The cardinality of this set is \(2^n-1\), as \((0)_{10}\) may be represented as either positive or negative.
Two's Complement¶
\((-5)_{10} = (1011)_{2t} = (1111\_1011)_{2t}\)
Interestingly, \((1011)_{2u} = (11)_{10} = 16 - 5\)
The two in two's complement comes from us taking the complement, which when added with the unsigned number gives us \(2^n\).
Note 1¶
Due to the nature of the Two's Complement Notation, the first bit of the number also tells us what its sign is, similar to a sign bit.
Note 2¶
Suffixes attached to the base are indicative of the encoding that they follow. These are attached for understanding purposes, and are not needed in your own working. \(X_{2t}\) signifies that \(X\) only has the intended meaning when we interpret it in binary two's complement notation.
This also shows that a binary number, by itself, does not equate to a decimal number. We need to know the encoding process to figure it out. Decoding the same binary nubmer assuming two different encodings can lead to different results.
Subtraction via the Two's Complement Method¶
The video explains how we can perform two's complement addition in base 10, which helps build a cleaner idea of what it does in base 2.
Range Calculation¶
Suppose you want to calculate the possible range of some operation between an \(m\) bit and an \(n\) integer in some \(R\) representation.
- Calculate the range of the two starting numbers in decimal notation.
- Calculate the range of the operation in decimal notation.
- Convert this range back to \(R\) representation, and find the number of bits needed. While doing this, the \(log\) function's result is rounded up.