Last week we took a look at the representation of negative numbers in computers, this week we will look at bit shifting and how it helped to fix a problem.

Many modern programming languages have an instruction known as the shift operator. Shifting is very simple, take the binary pattern of a number and shift it sideways by one bit.

If we have the base 10 (decimal) number 24, in base 2 (binary) it has the pattern 00011000. If we shift it to the right by 1 bit, we get the binary pattern 00001100.

00011000(original)
00001100(shifted right by one bit)

If we take that same pattern and shift it to the left by one bit:

00011000(original)
00110000(shifted left by one bit)

The original value can be shifted right and left by more than one bit as well [1].

In this table are the binary values with their decimal equivalents in parenthesis. There are a few things to notice: a left shift of one bit is the same as multiplying by 2, and a right shift of one is the same as dividing by 2.

You lose information when data is shifted past the boundaries of the variable, as can be seen in the row where data is being shifted 4 bits. Since 192 shifted left one bit should have a value of 384, but this is an 8-bit example where our range is 0 to 255, the data gets truncated. This is known as overflow.

When data is shifted right and data is lost, also shown in the shift by 4 row, this is known as underflow.

Shifting in C

In the C language, the “<<” and “>>” operators are used to shift values.

If we take our original decimal value of 24 and shift it right by two bits, the syntax looks like this:

Last week we saw that the most significant bit (MSB), the left-most bit, is used as an indicator that the value is negative. If you shift a value to the right, what happens to the sign bit? The answer is “it depends”.

If we take the decimal value -24, with a binary pattern of 11101000, and shift it with the C code:

with x being negative and y being the number of bits to shift by, we end up with this table of values:

and for a positive value we get this table of values:

The left shifts work the same way if the values are signed or unsigned, a zero is always shifted in on the right.

Right shifts work differently though. Above, instead of shifting in a zero, we see that the MSB is getting duplicated. Negatives get a 1 shifted in, positives get a zero shifted in.

These examples are for 8-bit values. On 16- and 32-bit values, the action is the same, but there are just more bits being shifted.

Looking at the Accelerometer Data

Now we have the information needed to fix a problem with an accelerometer.

The code to read the accelerometer chip gives 3-axis acceleration data as signed 16-bit values in 2's complement format. That’s perfect for modern processors. The mention of 16-bit 2's complement indicates that the data will have positive and negative values, the MSB will be the sign bit, and the values will range between -32768 and 32767 (signed 16-bit values).

The only axis that is interesting at this point is Z (zed, I’m Canadian). This is the up/down axis and measures the pull of gravity. Upright the Z-axis will report measurements corresponding to 1 G of acceleration. With the board upside down, the chip will report -1 G of acceleration. The chip reads up to 2 Gs when you move it around, so the output values, sitting on my table, should be about ½ of its output maximum.

Here is some real data from an accelerometer, with x, y, and z values:

-320, 384, 16000 
-320, 384, 16000 
-320, 384, 16384 
-320, 384, 16384 
-320, 384, 16384 
0, 384, 16000 
0, 384, 16000 
0, 384, 16064 
0, 320, 16064 
0, 320, 16064 
64, 384, 16064 
64, 384, 16064 
64, 384, 16064 
0, 320, 16000 
0, 320, 16000 
0, 320, 16448 
0, 320, 16448 
0, 320, 16448 
0, 192, 16064 
0, 192, 16064 
0, 192, 16064 
0, 320, 16064 
0, 320, 16064 
-128, 320, 16256 
-128, 320, 16256 
-128, 320, 16256 
64, 320, 16000 
64, 320, 16000 
0, 320, 16064 
0, 384, 16064 
0, 384, 16064 
64, 320, 16192

With the dev board sitting flat on my table, the Z axis reads 16384 in decimal, 16000, 16064 and shifts around quite a lot even though the board is just sitting there. If I turn the board upside down I get values like -16576,-16704, and -16640. The values are moving around a lot for a sensor that is just sitting there; 64, 128, 384 counts.

Wait a minute, those values are screwed up! First, I noticed that the amount that they are moving around is really big, I expect some noise, but that’s a lot. Next, the variation is really square, I’d expect them to move around 1, 2, or 6 counts, but numbers like 64 and 128 are too computery. And, when viewed in hexadecimal, the least significant byte is always zero.

Looking through the data sheet, I find that our accelerometer actually gives 12-bit 2's complement numbers. That’s not very useful, it has been many years since there were 12-bit computers around. Being 12-bit numbers, they can only go between -2048 and +2047. The accelerometer is configured to  transmit the 12-bit value shifted with its most significant bit stuffed up into the most significant bit of a 16-bit value, and the least significant 4 bits are all zeros. These values are all shifted by 4, so the values are going to be pretty wonky.

Let’s fix those numbers and see what we get; with the board upright the values would be 1024, 1000, 1004. Upside down, -1036, -1044, and -1040. Those are much more reasonable. They are in the range of -2048 to 2047 and the variation is comparatively small.

This weirdness which can be corrected easily:

The 16-bit value will be sign extended in the shift and will retain its negativity after shifting.

0,24,1000 
0,24,1004 
0,20,1004 
0,20,1004 
4,24,1004 
4,24,1004 
4,24,1004 
0,20,1000 
0,20,1000 
0,20,1028 
0,20,1028 
0,20,1028 
0,12,1004 
0,12,1004 
0,12,1004 
0,20,1004 
0,20,1004 
-8,20,1016 
-8,20,1016 
-8,20,1016 
4,20,1000 
4,20,1000 
0,20,1004 
0,24,1004 
0,24,1004 
4,20,1012

[1] Older processors could only shift values by one bit. To shift by more than one bit, the processor would iteratively shift the value by one bit. If it would only take one cycle to shift a value by one bit, to shift by 5 bits, it would take 5 cycles. The more bit positions you needed to shift, the longer it would take.

More modern processors use a piece of electronics called a barrel shifter, it can shift a value any number of bits in one cycle.

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

If you enjoyed this article, please send me the car that uses this shifter knob.