Last week, at the real Embedded Wednesdays at www.ents.ca, some of the students were looking through the datasheet for the accelerometer on our STM32F401C Discovery board. The data sheet said that the accelerometer sent its reading in 2’s complement format. Nobody knew what that meant.

This week we'll discuss the various ways of representing number systems in computers, and next week we'll discuss how the accelerometer was using 2's complement and what we needed to do to unscramble the data.

Most computers store their data in binary [1], positive numbers are pretty straight forward, how are negative numbers stored? They are also stored in binary, but their format changes to represent negative numbers. First, let’s lay out the problem; we’ll start out with a 3 bit computer (because it’s just a little bit better than a 2 bit computer).

The number system in our 3 bit computer looks like this:

Easy stuff, but our number system can only represent positive numbers in the range 0 to 7.

To represent negative numbers, we need to make some changes to our numbering system. There are three methods, we will start with the one that modern computers use.

This method is called 2's complement. Complement is the electro-computerese word for inverting a bit. If a bit is zero, it becomes a one; if a bit is one, it becomes a zero.

In 2's complement, to convert from a positive number to a negative number, or vice versa, you complement (invert) and then add 1. The table of 3 bit values ends up looking like this:

The most significant bit (MSB) is the leftmost bit. In decimal numbers, the number 42 would have 4 as the most significant digit. If you change it by 1, the total value changes by 10. If you change the 2 in "42" by 1, the total value only changes by 1. Therefore the leftmost digit is more significant than the others. The rightmost bit is the least significant bit (LSB) using the same logic.

The rightmost digit, the 2 in 42, would be the least significant digit. if you added one to that, you'd increment the total value by one (42 +1 = 43). However, with the most significant digit, if you change it by 1, the total value changes by 10 (42 => 52).

In 2's complement notation, we use the MSB as a sign indicator, so all negative numbers will have an MSB of 1. If a computer has a 32-bit processor the MSB will be the sign bit, and there will be 31 more bits to contain the value.

To negate the number 2 on our 3 bit processor:

010 // number 2
101 // invert each bit
110 // add 1 and you get the pattern for -2. The leftmost bit is 1, and this is the sign bit.

To negate the number -1:

111 // number -1
000 // invert
001 // add 1 and it becomes 1

Our 3-bit system has a range of -4 to +3.

For examples of doing math in binary, see the Khan Academy videos in the references.

The next encoding method is called 1's complement. It was used in older computer and chip designs. It uses fewer transistors to make the device, but the software has to undo some of the design decisions.

This way to represent negative numbers involves simply inverting all of the bits (all of the 1s become 0s and vice versa).

All of the negative values still use the MSB as the negative indicator, but to figure out how big the number is, you invert all of the bits and you will get the positive equivalent. This method has the weirdness of having positive and negative 0. Our 3-bit system has a range of -3 to +3.

Addition is a bit weird:


  011    // 3
+ 110    // -1
-----
 1001    // 2---whoops, no, that’s 9

To correct the answer, take the MSB and add it back in:


 1001   // 9 - take off the MSB and add it back in
  001   // 1 
 +001   // MSB 
-----
  010   // 2, that’s better

So, 1's complement has weird math, a reduced useful range, and a negative zero.

The final method is the simplest but it has problems too. This encoding method is known as sign magnitude. It doesn’t get used much, but would show up in designs where negative numbers were an afterthought and support was added as cheaply as possible.

To represent negative numbers, simply use the MSB as the sign bit, then the other bits will be the value.

Our range is now -3 to 3, and we’ve got negative zero.

Next week we'll look at how the 2's complement format is used in our accelerometer and how to unscramble the measurements.

[1] For more information on binary and hexadecimal see: https://www.khanacademy.org/math/pre-algebra/applying-math-reasoning-topic/alternate-number-bases/v/number-systems-introduction

This post is part of a series. Please see the other posts here.