Monday, 19 January 2015

Fiddle and Bits and Bits and Bits

My last post didn't fully answer the question: "What are the possible values a variable can be?" I will complete the answer here.

I will use 8-bit bytes for the entirety of this article.

Least Significant Bit


The least significant bit is the right most bit. It is so named because it represents the smallest possible number in the binary system: zero or one. It is the least significant value of the eight.

Don't let that fool you. It can be quite useful. More on that at the end of the post.

Byte of Bits


Lets look at an empty, zeroed byte: 00000000 (eight zeros).

The least significant bit is the right-most bit. So let's switch that bit on: 00000001.

We now have the number one. Move the bit up one slot and the value becomes two: 00000010.

How did that happen? Maths!

Math


Each bit in the byte is 2's compliment (see my previous post).

Each bit's value is 2 raised to a power. Starting at zero, incrementing by one for each step, move right to left and raise 2 to that power. The least significant bit is 2^0. The second least significant bit is 2^1, then 2^2 and so on. Sum the bits turned on for the value the byte represents.

Check it out:

Binary
Equation
Decimal
00
(0 x 2^1) + (0 x 2^0) = 0 + 0
0
01
(0 x 2^1) + (1 x 2^0) = 0 + 1
1
10
(1 x 2^1) + (0 x 2^0) = 2 + 0
2
11
(1 x 2^1) + (1 x 2^0) = 2 + 1
3

The value of each bit, from left to right, looks like this: 128, 64, 32, 16, 8, 4, 2, 1.

If you sum all these values, you get the value: 255. That's the maximum value of an unsigned byte!

Signedness


Ok, time to makes things weird. Well, not finding out your life-partner is your cousin weird but weird enough.

On the opposite side of the byte from the least significant bit is the most significant bit.

In many languages a type may be signed or unsigned. An unsigned byte can only be positive, whole numbers. A signed byte can be positive or negative whole numbers.

Most Significant Bit


A computer doesn't have a notion of a negation sign. It can represent a negative number, sure, but all it sees are bits. Using two’s compliment, how can a single bit be a sign when it must be a number?

The most significant bit does determine whether the value is negative or not. However, the eighth bit always has a value of 128.

Confused, yet? Good!

More Maths


When a computer interprets a signed byte the most significant bit becomes a negative value not a negative sign. Rather than being the value 128, it becomes -128.

Consider this: can you have a value of negative zero? Can zero ever be negative or is zero just zero?

If zero can’t be negative and the most significant bit merely represented the sign of the value, then what does 1000000 mean? This would be -0 and that is not a number.

To make the value -1, we need to add a value to -128 to get there. If we remove the eighth bit from the byte, the remaining seven bits consist of the values: 64, 32, 16, 8, 4, 2 and 1. Sum them all together and you get the value 127. -128 + 127 = -1.

Negative one is 11111111. There's a trick with this at the bottom of this post.

Let’s do another example of a negative number. Lets shoot for -54. What number do we need to add to -128 create this number in binary?

We just need to solve this equation: x = y + z; where x = -54 (the number we want), y = -128 (most significant bit) and z is the value we need.

-54 = -128 + z
-54 + 128 = -128 + z + 128
74 = z

Set the balance of the bits to 74 and the actual value will be -54: 11001010

Signed Values


We can now fully answer the question, “What values can a given C type have?”

A single byte has 256 different values. A C type that consists of a single byte is the char type.

An unsigned char can consist of the values 0 to 255.
A signed char can consist of the values -128 to 127.

Not a Dummy


Don’t feel bad if you have to read things over a few times for it to sink in. It took me a bit to really wrap my head around this but once I did, things really fell into place.

You can cheat, too. If an 8 bit byte has 256 values then divide it by two. That value negated is the lower bound. Reduce that same value by one for the upper bound.

256 / 2 = 128
Lower bound = -128
Upper Bound = 128 - 1 = 127

Fun Fact


Binary is how numerical permissions work for the ‘chmod’ command in Linux.

Bits
Value
Permission
000
0
None - Denied!
001
1
Execute
010
2
Write
100
4
Read

Combining the bits together we get the following table.

011
3
Write (2) + Execute (1) = 3
101
5
Read (4) + Execute (1) = 5
110
6
Read (4) + Write (2) = 6
111
7
Read (4) + Write (2) + Execute (1) = 7

This is the beauty of binary and two’s compliment. You can combine any number of unique options together without overlap.

Cool Tricks


Now that you’re a pro at understanding binary, I thought I might show you a pair of nifty tricks before I leave you.

1. Want to test for whether a number is odd or even?

if (n & 1 == 0) { /* even */ } else { /* odd */ }

2. Want to test whether a signed type is negative or positive?

const char MSB_BYTE = 1 << 8;
if (n & MSB_BYTE == MSB_BYTE) { /*negative */ } else { /* positive */ }


3.  Want to set an unsigned variable to it's maximum value but don't know what it might be on a particular machine? Many languages will let you do this little trick.

unsigned char c = -1

It sets all the bits on, which is always the maximum value. Go back to the "More Maths" section to see why this works.

There are no guarantees these tricks will work everywhere so read the specification for your language and check the compiler implementation to know before using them!

If you have never done bit shifting or used logical operators than this tricks probably make no sense. Once you learn about them come back here and think about these tricks and see if you can figure out why they work.