Bits, Bytes and Bases

Bits, Bytes and Bases

Bases:

Everyone knows how to count to ten, and whether you knew or considered it,
that system with ten digits is called base 10 or decimal. A decimal system
consists of ten digits 0 to 9, which can represent any number.

You were probably exposed to the Base 2 system in elementary school,
and promptly forgot about it (if you were like me). "What good is that?",
I thought at the time. But it is VERY important in computing. Base 2 has
only two digits 0 and 1, which correspond to off and on.

Think of it like a light switch.

0 = Off
1 = On


Counting is very simple, we count in the same way as base 10, when we run
out of digits, we increment the next place and continue.


Binary Decimal
0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
1000 = 8
1001 = 9


Now consider another equally important Base in computing, Base 16 or
Hexadecimal, Hex for short. Since it uses more than our "normal" ten decimal
digits, symbols are used to represent some of the digits. Namely A to F. We
count as follows:


Decimal HEXadecimal
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9 (All fine to here)
10 A (Start using symbols for digits)
11 B
12 C
13 D
14 E
15 F


Ok, what's next? Just like with Decimal once we've run out of digits,
we start again with the next number. And its 10, but this one-zero doesn't mean
the same thing as usual. Oh yeah, VB uses &H to denote Hex numbers.

(Remember that any number raised to the zero power is 1. And any number raised
to a power of one is the number itself.)
__________________________________________

&H10 = 1 * (16 ^ 1) + 0 * (16 ^ 0)

&H10 = (1 * 16) + (0 * 1)

&H10 = 16 + 0 = 16 (decimal)

__________________________________________

&HFF = 15 * (16 ^ 1) + 15 * (16 ^ 0)

&HFF = (15 * 16) + (15 * 1)

&HFF = 240 + 15 = 255 (decimal)

__________________________________________


If all the above was not clear, you might want to reread it.

__________________________________________

Bits and Bytes:

Bits are just base two digits, they are either on or off.

0 = Off
1 = On

Four bits together are called a nibble. Eight bits makes a byte.


Binary Hex
0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
1000 = 8
1001 = 9
1010 = A
1011 = B
1100 = C
1101 = D
1110 = E
1111 = F



Notice that one nibble (four bits) is also one Hex digit. This is a
very important relationship. And two nibbles makes one byte.


A 0
&HA0 = 1010 0000

F F
&HFF = 1111 1111


So! We see that its very easy to represent any Hex number by breaking
it down into nibbles. What about a 16 bit integer?

8 0 A 1
&H80A1 = 1000 0000 1010 0001


Study this relationship carefully, it will be invaluable to any programmer.


Lets review, a bit is a binary digit and is either on or off. Four bits
makes a nibble. Each nibble is one Hex digit. Eight bits or two nibbles makes
a byte.

Bit Manipulations:

There are Three basic bit manipulation operators, AND, OR, NOT. Not is
used to toggle the state of a bit. Or is to turn bits on or combine them.
Last And to check the state of a bit.

Ok.. theory is boring if you don't see any use for it. How about
something useful? In order to determine if a number is odd or even we can
check the first bit. That bit is always set for odd numbers.

And Operator:

We use the And operator to check the state of a bit. If both bits
being And'ed are on, then the result is "on" or 1. Any other combination
results in "off" or 0.


This is the truth table for the And Operator:
____________________________________________
0 And 0 = 0
1 And 0 = 0
0 And 1 = 0
1 And 1 = 1


Is 2 Odd?


If (2 And 1) = 1 then ' testing to see if the bit is set

' or from a binary perspective:

If (10 And 01) = 01 then ' which we know is FALSE




Is 1 Odd?


If (1 And 1) = 1 then ' woohoo! The bit is On, its TRUE


Of course this holds true for ALL odd numbers as their one bit is set.

Now, what if you had a long color (4 bytes) and you wanted to get just
the red portion of that color. How could you do that? Just like testing for
odd/even, you use the And operator. Btw, this is called bitmasking.

An RGB color is in the format:

&H00BBGGRR Zero/Zero/Blue/Blue/Green/Green/Red/Red


It is the last 8 bits we're after (RR) so we'll And like this:


Dim lRed As Long
Dim lColor As Long

lColor = &H000000FF ' Red

lRed = (lColor And &HFF)


lRed would now contain just the red portion of the color. Why did this
work? Look at it from a Binary perspective:

1111 1111 And 1111 1111 = 1111 1111


Or Operator


The truth table for Or is:
__________________________
0 Or 0 = 0
1 Or 0 = 1
0 Or 1 = 1
1 Or 1 = 1


Think of it as binary addition with a twist. The twist being, if the
bit is already on and you Or a 1 with it, there is no change. This is also why
real programmers NEVER Add bit flags together, they OR them.

Consider a single long variable with 4 bytes or 32 bits. That one
variable gives us a chance to store the state of 32 flags. Lets say all the
bits are off and we want to set the third bit.


Dim lState As Long
dim lFlag As Long

lState = 0
lFlag = 4

lState = lState Or lFlag


lState now equals 4. Why?

0000 Or 0100 = 0100


What if we attempted the same operation again?


lState = 4 ' from last time
lFlag = 4 ' same

lState = lState Or lFlag


0100 Or 0100 = 0100 ' THE SAME! </Monty Python>


Not Operator:

This one is easy. It merely toggles the state of a bit. If its On then
Not turns it off, and vise versa.

Truth Table:
____________
True = Not False
False = Not True

(It goes a little deeper than that because of signed variables, but that is
another discussion.)

___________________________________________________________________


Bit Shifting:

Bit shifting is nothing more than moving bits around. How do we do it?
Since VB has no "true" bit shifting operator (vb.net does) we use multiplication
and division by powers of two. So if we want to shift bits to the left we use
multplication, and to the right integer division.


Dim lFoo As Long

lFoo = 4 ' 0100 in binary

lFoo = lFoo \ 2 ' shift right one position

lFoo = 2 '0010 in binary



What good is that? Well.. lets go back to the long color example.
Say you wanted only the Green color out of a long.

&H00BBGGRR

Hmmm... that GG is trapped in the middle. I know! Let's shift it 8 bits
to the right and the RR is gone.


Dim lColor As Long
Dim lGreen As Long

lColor = &H00FFFF00

lColor = lColor \ 256 ' lColor is now equal to &H0000FFFF

' Hrm.. how do we get *just* the last byte? We AND it just like we did with
Red before.

lGreen = lColor And &HFF


Shifting to the left is just as easy. Just remember one thing, you
cannot shift into the high bit in the IDE. You can either ignore integer overflows
in the compiled exe, otherwise you can OR the high bit on.


lFoo = 2 ' 0000 0010

lFoo = lFoo * 8 ' shift left three bits

' lFoo now equals 16 ' 0001 0000



I'll explain more about shifting signed types and maybe Xor and Neg later.
If you don't understand, feel free to ask specific questions.

Bit Shifting (in-depth)

VB integer (16 bits) and long (32 bits) data types are signed, meaning they can accommodate both negative and positive values. This means that a single bit is used only for the sign. And the remaining bits are used for data. For instance:


' note these are integer values for brevity
Decimal Hex Binary
0 &H0 0000 0000 0000 0000 ' no bits set
1 &H1 0000 0000 0000 0001
2 &H2 0000 0000 0000 0010
4 &H4 0000 0000 0000 0100
...
32767 &H7FFF 0111 1111 1111 1111 ' largest positive value

-32768 &H8000 1000 0000 0000 0000 ' largest negative value
-32767 &H8001 1000 0000 0000 0001
-32766 &H8002 1000 0000 0000 0010
...
-1 &HFFFF 1111 1111 1111 1111 ' all bits set



Notice you can also consider these values a be unsigned if you look at them from a Hex perspective.

..

Right Shifting

Unsigned

Unsigned shifting is much more common when dealing with binary/bits.

When a unsigned shift is performed, the sign bit is not preserved.

Since the data types we're using Are signed, we'll need to go to a little extra trouble.

Note: The extra ANDing is only needed for negative numbers, positive numbers can just be divided by the appropriate power of two.


Dim iTest As Integer

iTest = &H8000

iTest = ((iTest And &HFFFE) \ 2) And &H7FFF
' iTest = ((iTest And &HFFFC) \ 4) And &H3FFF ' two bits
' iTest = ((iTest And &HFFF8) \ 8) And &H1FFF ' three bits

Debug.Print "The result is: &H" & Hex$(iTest)


Starting with:
&H4 = 0000 0000 0000 0100

Right shifted by one bit equals:

&H2 = 0000 0000 0000 0010

Right shifted by one more bit equals:

&H1 = 0000 0000 0000 0001


Also try:
&H8000 = 1000 0000 0000 0000

Right shifted one bit equals:

&H4000 = 0100 0000 0000 0000

..
Signed

Signed shifting follows along with what we expect mathematically of division, but is a little odd from a bit shifting perspective. The sign bit is preserved and replicated as we shift. Note that for positive numbers, it as the same as unsigned.


Dim iTest As Integer

iTest = &H8000

iTest = iTest \ 2 ' not terribly interesting, or useful, from a bit shifting perspective

Debug.Print "The result is: &H" & Hex$(iTest)


For instance:

&H8000 = 1000 0000 0000 0000

Right shifted one bit equals:

&HC000 = 1100 0000 0000 0000

Right shifted once more equals:

&HE000 = 1110 0000 0000 0000


And also:
&HFFFC = 1111 1111 1111 1100 = -4 (decimal)

Right shifted one bit equals:

&HFFFE = 1111 1111 1111 1110 = -2

Right shifted once more equals:

&HFFFF = 1111 1111 1111 1111 = -1

..

Left Shifting

Shifting left is the same whether the shift is signed or unsigned. Zeros are shifted in on the right and bits move to the left. The sign bit is not maintained during left shifting.

Left shifting in VB is accomplished by multiplying by a given power of two. This is just as fast in VB as it would be in C++, since only a single instruction is involved. It's also necessary to Ignore Integer Overflows in advanced compiler options. This is because shifting into the sign bit (turning it on) makes a number negative.

For Example:


' Project - Properties - Compile -
' Advanced Optimiations - Remove &Integer Overflow Checks
Dim iTest As Integer

iTest = &H8000

iTest = iTest * 2 ' Left Shift one bit

MsgBox "The result is: &H" & Hex$(iTest)


The result will be 0, assuming you checked the correct flag and tried the compiled EXE.
In binary, this is what happened:

&H8000 = 1000 0000 0000 0000

Left shift all the bits by one, equals:

&H0 = 0000 0000 0000 0000

The sign bit overflowed and is now gone as far as we're concerned.



Other examples:

Change iTest and Start with:
&H1 = 0000 0000 0000 0001

Left shift all the bits by one, equals:

&H2 = 0000 0000 0000 0010

(Again) Left shift all the bits by one, equals:

&H4 = 0000 0000 0000 0100

...

Start with:
&H7FFF = 0111 1111 1111 1111

Left shift all the bits by one, equals:

&H8000 = 1111 1111 1111 1110

Note that zero bits are moved into the right side.
And that bits disappear off the left.
The number has also changed from positive to negative.