A Bit on bits and bytes
Back during school days we used to count 0 , 1, 2..9.. and we referred Decimal Number system of base 10 consisting 10 digits. Any number can be formed using powers of 10. For eg. 125 is :
This is what we were using till now. But then what is 0 and 1. Why 0 and 1? Our computers are Electrical devices who understand either on or off. We follow Binary system consisting of two digits 0 and 1 in order to communicate with them. Let it be a text or an image or a number, everything is 0 and 1 inside the computer’s brain. Same is for binary, using base 2 we can actually decode what the number is. For eg. What 1001 in binary format means? It is the number 9.
Basic rules of Binary Addition and Subtraction:
These are not actually the rules, just some of the memories of addition and subtraction in our third grade. Bear with me the basic concepts and then we will climb up on amazing things.
1+0 = 1;
0+0 = 0;
0+1 = 1;
1 + 1 = 10 write 0 and carry 1 in 2's place;
Well we all know 1+1 is 2. Also 2 is nothing but 10 in Binary. If we had 19 in decimal addition what would we do? Write 9 and carry one in tens place? Similarly here also we write 0 and carry one. Cool? Now let’s see about subtraction of binary digits:
0–0 = 0;
1–0 = 1;
1–1 = 0;
0–1 = 1 by borrowing 2;
Now this is how it takes place:
So this was all about the basic binary and it’s Arithmetic. But how are all these 1’s and 0’s stored in the computer? In the Random Access Memory of computer there are so many addresses which are allocated to different data types as we create them. Here, we will concentrate only on Integer type. One 0 or one 1 is referred as a bit. 8 bits consist of 1 byte. Each byte is given it’s own address. The size of an Integer in Java is fixed unlike in C++ which depends on the machine, it is 4 bytes that is 32 bits. Now let’s see our variable in the hypothetical memory diagram:
Now let’s suppose the value of a is 2555. This is how the 1’s and 0’s are stored in 32 bit integer. Let’s assume the horizontal representation
When least significant bit occupies the lower address, it is called Little Endian while when the least significant bit occupies the higher address, it is called Big Endian representation.
Now if it is an int, I can store any whole number value, can I? The answer is no because every data type has a specific range. Now how is that range decided?
If we have one bit, we can have 2 values either 0 or 1.
Here, we notice that if there are n bits then 2 raised to n values are possible. And the range of values is from 0 to (2^n -1). As an example see the example of 3 bits..the values from top to bottom in decimal are 0 to 7 i.e. from 0 to
(8–1).
Since int has 32 bits..0 to (2³²-1) values are possible.
However there is one problem, in this manner we cannot include negative numbers! Is there any way so that we can represent negative numbers?The first thing that came to my mind was why can not I add a ‘-’ sign before the number as we do in decimal. Why can’t -(001) represent -1? The problem here is computer does not understand ‘-’..it only knows 0 and 1.
What if we made the Most Significant Bit as the sign bit and the rest of the bits as the magnitude bits?If MSB is 0 the number is positive and if it is 1 the number is negative. See the 3 bits example above, The first four numbers then will be considered positive and the last four numbers negative as followed:
There are two problems here:
1. 0 occurs two times.
2. Arithmetic subtraction does not make any sense in binary format. As an Activity try
001+101. Did you get 0? No, right? There is something wrong with this convention. 1 + (-1) must give 0 but using binary numbers and arithmetic we got -2!
What do we do then to represent negative numbers also? The best way is using 2’s complement method. Negative of a binary number is stored as 2’s complement. It says to find the negative of any number:
a. Invert the number (0 changes to 1 and vice versa)
b. Add one to it.
Cherry on the cake is that when you add the number and it’s 2’s complement you get 0 i.e. we can perform normal binary arithmetic.
The 2’s complement of 001:
a. Invert: 110
b. Add one: 111
Things will look like this when we use 2’s complement.
In this system also, the negative number’s MSB is 1. Do not get confused by converting the above negative binary numbers into decimal and simply adding a negative sign, this is not how it works. While evaluating the number take negative sign only with MSB term and add to it rest all terms. For e.g :
Now we can evaluate the range. For 3 bits the range is (-4 to 3) that is (-2² to 2²-1). Thus, we can see that for n bits the range is
(-2^(n-1) to 2^(n-1)-1).
Now, Didn’t the question ‘WHY’ stuck your mind while reading the rules of 2’s complement? Well, this is the analogy that I read once:
Whenever we find a negative of a number, what we basically do is subtract that number from 0. Consider the number 12 in 8 bits. It’s binary representation is 00001100. In order to find it’s negative we go 12 steps beyond 0.
The computer only considers eight bits and discards everything else. In the above example the zero at MSB also borrowed but since our machine will considers 8 bits, it does not matter. Subtracting the eight(n) bit number from 0 is equivalent to subtracting it from 100000000 i.e 1 followed by 8 0’s(n 0's) or 2⁸ (2^n). 100000000 is equivalent to (11111111+1)
So what are we finally doing..
11111111+00000001–00001100(the number)
And in binary subtracting a number from a number whose all bits are 1 is equivalent to inverting the bits of that number. As an activity, try it.
And this is what we are doing as a shortcut. Inverting the bits and then adding one.
Thank you for reading.