So in this video, when we are talking about fixed point representation and fixed point
arithmetic, we’ll predominantly be talking about integer numbers where the binary point
is to the right of the LSB.
Right, we already discussed a couple of ways of representing integers.
There is the unsigned representation, where we ignore all negative integers.
This is commonly called unsigned int data type in programming languages.
If a value seems like it’ll never be negative, then it’s generally good practice to use
unsigned integers.
It’ll give you twice the maximum representable value of a signed integer, but most of the
time, it’s never really about the range, it’s more about the intent.
When you declare a variable as an unsigned int, you’re publishing to the reader of
the code that the value will never be negative.
For example, the number of samples in a buffer can’t be negative, same with the sample
rate, and same with the index to an array.
A negative index doesn’t really make sense.
Again, it’s all about the intent, it doesn’t give you any added performance advantage.
But you always have to be aware of arithmetic overflow.
If an unsigned number does drop below zero, it’ll be wrapped around to the other end
of the range.
If you were to take 8 bit unsigned integer, assign it to zero, and subtract 10 from it,
you end up with 246, which is essentially 10 subtracted from the upper end of the range.
Do the same with a 32 bit unsigned integer, and you get a really large value.
So it’s up to the user to make sure that negative numbers don’t arise from calculations
with unsigned integers, otherwise you’d end up getting nonsensical answers.
The next representation model that I hinted at was the magnitude and sign representation.
One of the bits, usually the left most bit is used to represent the sign of the number,
and the rest of the bits are used to represent the magnitude of the number.
Take the example of the number 7 in an 8 bit representation.
The value in binary is 0000 0111.
Now according to this model, negative 7 is just flipping the left most bit, to get 1000
0111.
Using this representation, negating a number is a really fast operation, just flip one
bit.
Conceptually at least, this looks like a sound model.
It’s easy to visualize and understand.
But implementing this in hardware is difficult.
There are several problems with this model.
One of them is the ambiguous zero problem.
Consider this 8 bit number.
The value represents zero of course.
Let’s flip the sign bit.
What is this number now?
Negative zero?
We know that zero is neither positive nor negative, and now we have the problem of handling
2 different types of zero, both redundant and ambiguous.
The main problem with this model is when binary addition is involved.
The addition of 2 numbers isn't trivial anymore, we need to first check whether the number
is negative and handle it differently if it is.
Since binary addition is one of the fundamental operations a computer processor does, and
since millions of such operations happen every second, this added check significantly drops
the efficiency.
To understand the problem, you need a tiny intro to binary addition.
Consider the numbers 7 and 3 in binary.
Now, binary addition is similar to decimal addition, where you add the numbers, and if
there’s an overflow, then you carry the excess value to the next digit.
In decimal addition, 7 +3 is 10, you can’t represent 10 in a single digit, so you carry
the excess of 1 over to the next digit.
In binary addition, it’s similar, the overflow happens when the value is greater than 1.
1 + 1 is 10 in binary, we retain the 0, carry the excess of 1 over to the next digital.
1 + 1 + 1 is 11.
We retain 1, carry over 1.
1 + 1 again, retain zero and carry over 1.
1 + 0 is just 1, so there is no overflow.
The rest of the digits remain the same since binary addition of 0 is just 0.
The resulting number 1010 is the decimal equivalent of 10, all good.
But let's say we add +7 and -3.
The answer is quite obviously 4, but when we implement binary addition, the value ends
up being -10.
So clearly we need to first recognize that one of the numbers being added is a negative
number, then we need to use the binary subtraction algorithm, then we need to figure out if the
resultant number is negative or positive to switch the sign bit, all the while accounting
for possible overflow.
This is tedious.
And we want to avoid additional checks when dealing with binary addition.
In other words, we want to make addition as simple as possible, irrespective of whether
the numbers being added are positive or negative.
To do this, we need a new representation model.
Enter 2’s complement.
2’s complement is a binary representation model that handles negative numbers differently
as opposed to just having a sign bit.
The positive numbers are the same as we’ve seen before, only the negative numbers change.
Let’s just look at an example.
Consider an 8- bit representation of the number 3.
This is fair enough, we’ve seen this before.
Negative 3 in 2’s complement is this number.
Right, that’s really hard to visualize and read for us humans.
But, as we’ll soon find out, this sort of representation is computationally very efficient
for computer hardware to handle.
Let’s take the same example as before.
Add 7 and -3.
These are the numbers, and if we just go ahead and perform binary addition as before, we
end up with this, which is the binary equivalent of 4, which is the answer we were expecting.
How did we end up here?
Why are we representing negative 3 this way?
Computing the negative of a number or the 2’s complement of a number is a 2 step process.
First, you take the 1’s complement of the number.
1’s complement is just a fancy way of saying flip all the bits of the number.
If a bit was previously 0, it becomes 1, and if it was previously 1, it becomes zero.
Essentially a bitwise negation operation.
The second step is to add one to the result.
There you go, that’s it.
If we take the 2’s complement of this number again, we end up with the original.
So it’s clearly a reversible operation.
But why?
Why do we represent numbers this way?
How do we build our intuition to work with 2’s complement representation?
The really simple motivation behind this is, when you add a number with its negative, the
result should be zero.
If we can force this to happen, our representation model should handle a wide variety of cases.
How do we force this to happen?
If you take any n bit number, and the add it with its 1’s complement, you’ll end
up with the largest number that n-bits can represent.
You can quickly try this.
Take any arbitrary 8-bit number.
And take the 1’s complement of this.
Add them together, and you get all one’s signifying the largest possible number that
n-bits can hold.
What if we add one to this?
We get an overflow, 8 bits can no longer hold this value, the number resets to zero, and
the overflow that’s supposed to go to the 9th bit is discarded, since there is no memory
available for that 9th bit.
Simply put, any n-bit number, added to the 1’s complement + 1 of the same number is
zero.
It’s the same equation as before, any number added to the negative of the same number is
zero.
And so we treat the 1’s complement + 1 as the negative number of the original.
Another simple way to look at 2’s complement numbers is to visualize the rotoray dials
of a slot machine, or the odometer of a car.
What happens when you reverse the spindle and the gears of the dials manually, below
zero?
In the case of a car’s odometer, nothing really happens if you’ve seen Ferris Beuller’s
day out, reversing a car doesn’t actually reverse the odometer gauage!
But let’s just say that hypothetically it does.
The resulting number is all 9’s, the largest number possible, and reduces from there on
out.
Now consider the same rotary dials with binary numbers instead.
1 rotation below 0, results in all 1’s which we term as -1 in 2’s complement.
-2 is one rotation below that, -3 is one rotation below that, and so on.
As long as the most significant bit is 1, the number is negative.
Once the most significant digital is flipped to zero, teh numbers are positive and follow
the familiar logic that’s easy for us to understand.
With 2’s complement representation, you also avoid the ambiguous zero problem.
2’s complement of zero is zero itself, so you don’t have to worry about a redundant
zero that we saw with the sign and magnitude representation.
Another nice quirk about 2’s complement model is that if we need to extend the width
of the register that’s holding the value, let’s say from 8bits to 16 bits, all we
need to do is pad the extended register bits with the most significant bit of the number.
This way, the extra bits when expanding the storage of the register from 8 bits to 16
bits is padded with 0’s for positive numbers and 1’s for negative numbers, the original
value is still retained.
A final thing to note is that 2’s complement is the predominantly used signed notation
for binary number.
Unless otherwise stated, you can always assume that when dealing with signed integers in
computer, the underlying binary representation is always 2’s complement.