Remote Control Jeep Community Service Project – Part 5

This is a continuation from Part 4. If you haven’t read it, you can here.

Computers subtract by adding the negative of the number they are subtracting. If you remember your 6th grade math, you’ll know that 5 + -3 is the same a 5 – 3. But before I said that computer’s can’t have negative numbers, right? Yes. But, there is a way negative numbers can be represented by positive numbers. It’s called the 2’s complement, and it’s how computers can store negative numbers.

Remember before when I said what happens when you try to store a number larger than the computer can hold? It loops back around to zero. For instance, let’s say that your computer can hold 4 bits of data (0000-1111 or 0 to 15). If you tell your computer to add 15 + 1, it will return 0 because 1111 + 1 = 0 when you only have 4 bits. But what if you add 15 + 2?  The computer does the same thing again, but it will return 1 now instead of 0. Why? If you pretend you are the computer, and you’re asked to add 1111 and 0010, you will first add the last 2 bits, just like a person would. 1 + 0 = 1, so the last digit in the result is 1. Then you add the 2 second to last bits. 1 + 1 is too big, so the next bit in the result is 0 and you carry the 1. Eventually, the result is 0001, or 1. The same happens if you add 14 + 3, or 13 + 4. If your computer’s limit is 4 bits, 15 + 15 = 0, because you wrap around twice.

To make looking at the binary numbers easier, I’m going to separate each group of 4 from now on. This doesn’t change what the numbers mean, it just makes them easier to read, So 00101101 will now be 0010 1101. I’m also going to write an entire byte of numbers with all of the zeros included.

Now back to the 2’s complement. The way computers store negative numbers like this:

1. Take the absolute value of the negative number you’ve received (-3 becomes 3).
2. Convert it to the opposite of that number (3 is 0000 0011 in binary so the number becomes 1111 1100).
3. Add 1 to the value (1111 1100 + 0000 0001 = 1111 1101).

So 0000 0011 (3) becomes 1111 1101 (-3).

This system works great, because calculations like 3 + -3 work exactly how they should: 0000 0011 + 1111 1101 = 1 0000 0000. The 1 would be the 9th bit, but there can only be 8, so it is lost, resulting in 0000 0000.

And, because of the way adding much farther past the limit works (remember how before 15 + 2 would equal 1 if there were only 4 bits?), -3 + 4 equals 1: 1111 1101 + 0000 0100 = 1 0000 0001. And, of course, the farthest left 1 is lost, resulting in 0000 0001 or 1!

This is how negative numbers work in computers, and hence, how they can subtract. The only problem with doing this is that you can only store numbers half as large as you could if they were only positive. This is because you now have to store twice the numbers (positive and negative) in the same amount of space. This means that the numbers can only be half as large, so that they can fit in that same amount of space. This is the 16-bit signed integer limit. Finally, we get back to the problem I was originally having.

The largest unsigned number you can store in 16 bits is 65,536. But, if the number is signed, the largest values you can store are positive and negative 32,767. It also happens that that is the range of values the xbox controller would output; between 32,767 and -32,767. This is where the problem occurs.

In order to know when I was within 10 points of the target, I was checking if the current speed was greater than the target speed minus 10, and if it was lesser than the target speed plus 10. The problem is, if the target speed was at either of the signed limits, the addition or subtraction of 10 in the check would loop all the way around and break the calculation. It’s called an integer overflow, and it’s what caused all the crazy behavior.

It’s extremely difficult to explain exactly what was happening when the calculation broke, and I still don’t even completely understand.

In the end, it turned out to be pretty easy to fix this, and all I did was divide the incoming values by 2 before I did the calculations. Finally, I was done. I turned the Jeep with the now-fixed code in, and no other problems turned up.

It has been a very long journey to get to this point, but I’ve learned a lot along the way, and It’s been fun. I’m looking forward to the next time I get to work on a project like this and the next time I find a problem like this one, because you can’t learn until you find a problem that you don’t know how to solve yet.