User Rating: / 1
PoorBest
Written by Bryce Ringwood

We humans are familiar with counting in powers of ten. Unfortunately computers count in binary and performing the translation from binary to decimal and vice-versa does not always turn out to be particularly helpful or insightful. This article deals with integers. Floating point numbers are stored in memory as mantissa and exponent and we seldom, if ever, do the bitwise operations on them that are described here. Indeed - this article is really more about the operations than the numbers.

Not only must computers count, but they must add, subtract, multiply and divide. They must also shift the contents of register (memories) to the left and right. If that wasn't enough, they must also perform boolean operations "AND", "OR","NAND","NOR" and "XOR". Depending on the computer, you will find a horde of other "instructions" that can be performed on the bits contained in a computer's memory location.

Computers also need to represent character strings in binary format. You might like to look at a table that converts ASCII characters to their binary format., but I don't think you will find one.

Each 8-bit representation of a character, unsigned integer, etc is refferred to as a byte. Microcomputers are generally referred to as 4(rarely), 8, 16 or 32-bit. An 8-bit computer has memory arranged in words of 1 byte each. A 32-bit comuter has a 4-byte word, whereas a 4-bit computer has a half-byte (nybble) word. The 'C' compiler will sort all this out for you, but an assembler won't! In general, the longer the word length, the more memory can be addressed by the computer CPU. This is good news indeed for the Arduino fraternity, as Microchip have brought out a 32-bit version of the Arduino which has a humongous amount of memory on-board. Can't wait to try it - its affordable too. :=).....

Number Conversions

When we represent a number, such as 143 in the decimal system, we really mean shorthand for:

\textstyle 1 \times 10^{2} + 4 \times 10^{1} + 3 \times 10^0

The same number can be represented in binary form as:

1000 1111

or, in other words:

\textstyle 1 \times 2^{8} + 0 \times 2^{7} + 0 \times 2^{6} + 0 \times 2^5 +1 \times 2^4 + 1 \times 2^3 +1 \times 2^2 +1 \times2^1 +1\times 2^0

Calculating the above formula will convert the number to a decimal. To convert the other way, you can use a process of repeated division,  thus:

143/ 2 = 71 remainder 1

71/2  =   35 remainder 1

35/2  =   17 remainder 1

17/2   =    8 remainder 1

8/2     =    4 remainder 0

4/2    =     2 remainder 0

2/2    =    1  remainder 0

1/2    =    0  remainder 1

The first remainder calculated in the above sequence is the least significant binary digit.

Representing 10001111 is inconvenient, so pogrammers convert to hexadecimal. The is is counting to base 16. Writing 10001111 as 1000 1111, we can see we have :

\textstyle 8 \times 16^1 + 15 \times 16^0

In the hexadecimal system, we need additional symbols for the numbers between 10 and 15. These are given the symbols A,B,C,D,E and F. So the number '15' or '1111' becomes 'F', and the first digit is '1000' or '8'

Thus :

\textstyle 8F_{base16} = 143_{base10}

Note that in 'C' hexadecimal values are preceded with '0x', thus int var = 0x8F; will set the value of var to 143 in decimal.

Fortunately, you soon get used to converting from binary to hex, and in any case, you just use Microsoft's calculator in "scientific view"  (view->scientific) to convert from one number system to the other without really understanding what you are doing. The understanding will develop later.

Now you can look at a table of ASCII characters, and see the hexadecimal equivalent opposite - and picture the pattern of 1s and zeroes in memory.

Arithmetic Operations

(Pronounced in Arith-Metic, not like "School Arithmetic"). These are the functions Addition, Subtraction, Multiplication and Division.

This is fairly straightforward. Lets add 14 to 7, like this:

0000 0111

0000 1110

0001 0101 = 21

You simply carry 1 every time  a column of figures exceeds 1, in the same way you do for decimal addition every time the sum of the column exceeds 9.

Subtraction

This raises the question of negative numbers. In many computer systems, negative integers are often represented by their "twos complement" representation.  To get the twos complement of a number, you simply reverse all the bits and add 1, thus 7 becomes

0000 0111

Reverse the bits =

1111 1000

1111 1001

Now we can calculate 14 - 7 as 14 +(-7), like this:-

0000 1110

1111 1001

0000 0111 - Which = 7, if we ignore the carry bit.

Multiplication

Now that we can add and subtract, we can also multiply by repetitive addition.

Division

In a similar manner, division is a process of repeated subtraction, until a remainder less than the dividend is achieved.

Think of it this way: 7 divided by 3 can be thought of as: remainder= 7 +(-3) +(-3) . So we have added (-3) twice, therefore 2 is the quotient and 1 is the remainder.

This is interesting, but not particularly useful. The microprocessor chip does all this for us.

There are the logical operations which will allow us to send the correct pttern of bits to an external device, such as a dot matrix LCD, or will allow us to garner the correct input from a digital temperature probe or an A/D converter.

Logical Operators

The 'C' language bitwise operators are given in brackets.

OR ('|')

The OR operation provides an output if either input is high, thus 1001 | 1100 = 1101.

AND ('&')

This useful operator provides an output only if both inputs are high, thus 1001 & 1100 = 1000. This is very useful for masking the outputs to a port.

Note that & is also the "address of" operator - operator overloading perhaps?

NOT ('~')

Now you know the purpose of the tilde on the keyboard. ~0011 = 1100.

Sometimes called the 1s complement operator.

NOR and NAND

Equivalent to NOT OR and NOT AND. Invert the AND and OR with a NOT (~) afterwards.

XOR (^)

Produces an output if one or other input (but not both) is high. Thus 0101 ^ 1010 = 1111 and

1111 ^ 0101 = 1010. In other words successive applications of XOR get you back to the beginning. This is beloved of animators who XOR pictures of sprites (your mouse pointer frexample) across a screen.

Shifting bits (<< and >>)

The remaining operators are not so much mathematical or logical, but they are useful. The shift left operator ('<<' )shifts all the bits in a word the left. Thus 0000 1100 << 2 = 0011  0000. The shift right operator does the opposite 0011 0000 >> 3 = 0000 0110. This is equivalent to multiplying by 4 and dividing by 8, repectively.

Conclusion

That just about covers the bare minumum needed in order to understand and write computer programs that convert values so that values can be displayed and inputs can be read and translations can take place which mean something to people. Don't worry if it doesn't make sense all at once. Also, if you can't get your head around it, maybe you can look at another source on the web that explains things more clearly - its always better to look at several sources. After a while, you just write programs using these principles almost automatically, and of course, that's when you start making the biggest mistakes.

I didn't mention octal number systems (even though the download calculators have octal conversion.) It was useful with the Sperry 1100 and its funny 6-bit bytes and 36 bit word, but that was a long time ago.

Some References

"IBM and XT Programming - A Guide for Programmers" - Scanlon LJ, Brady / Prentice-Hall, 1985

"The Art of Electronics" - Horowitz. P and Hill W, Cambridge Press, 1982

The incorrect bits are all mine - please let me know about them.

Joomla template by a4joomla