Bit Shifting

The left and right shift operators are the last two bitwise operators for us to look at.

In C (and C++), << and >> are used to shift bits around inside bytes. Not just in any random fashion – these operators move all the bits either to the left or to the right, exactly as their names imply.

Left bit shift

This is the easy one. No matter what your integer type (long, short, signed, unsigned), applying this operator always moves the bits to the left and pads with zeros from the right. The bits that move off to the left are discarded – they are gone forever and you can’t get them back.

For each place that the bits are shifted, it is the equivalent of multiplying by 2.

62 << 2 = 248    //or, multiply by 4

In binary:

0011 1110 //62
(00)1111 1000 // 248 (discarded) padded

The next example shows what happens if you use an integer that is not large enough to hold the result. 120 << 2 should give you 480, but since we are using a single byte, we lose bits from the left and the result is 224:

120 << 2 = 224

In binary:

0111 1000 //120
(01)1110 0000 // 224 (discarded) padded

Right bit shift

The right shift does the opposite of the left shift. If you are applying it to an unsigned integer this is always the case and it is always the equivalent of dividing by 2 for each place shifted (and it always rounds down towards zero).

62 >> 2 = 15    // or, divide by 4

In binary:

0011 1110 //62
0000 1111(10) // 15 padded (discarded)

Right shifting signed integers

If you apply a right shift to a signed integer, then the result may vary. On some machines, under some compilers, it will pad with sign bits, i.e. 1s for a negative number and 0s for a positive number, since the leftmost bit is the sign bit for signed integers. This is also termed the ‘arithmetic shift’. On other machines, with other compilers, it will always pad with zeros. This is termed the ‘logical shift’.

GCC, which is the compiler I use, implements the arithmetic shift. You can easily write a few lines of code to test out what your own compiler does if you can’t find details in the documentation.

Note that right shifting a negative signed integer rounds towards negative infinity, not zero. -50 >> 2 will give -13, but -50 / 4 will give -12.

Two’s complement is used to represent signed integers, so the binary representation for the negative numbers below is probably not familiar. However, you can still see how the shift is applied here. (I’d like to cover two’s complement representation at some point in the future – it requires its own post to be explained effectively.)

1100 1110 // -50
1111 0011(10) // -13 padded (discarded)

What would I use bit shifting for?

We’ll take a look at some examples next week – right now I have a 3 week old baby that needs feeding!

Bitwise NOT

Well, we’re now onto the final of the four bitwise operators – bitwise NOT – probably the most simple of the four to understand.

Bitwise NOT is represented by the tilde symbol, ~, and only takes one operand.

Can I see an example?

~125 = 130

What is this actually doing?

Bitwise NOT essentially flips the bit setting for each bit, resulting in what is known as the “one’s complement” of the original number.

So the example above has a bit output as follows:

01111101    // 125
10000010    // 130

What would I use bitwise NOT for?

Turning off an individual bit

Actually, the NOT operator doesn’t itself turn off a bit, but in conjunction with the AND operator, you can use it with a mask to turn off a bit in a nice readable manner.

This is best illustrated with a full example:

char settings = 0;    // 00000000
char FLAG1 = 1;    // 00000001

Let’s assume that ‘settings’ is a byte we use to represent 8 boolean values. First of all, we’ll set the first bit of our settings variable to 1 using the OR operator and our FLAG1 mask:

settings = settings | FLAG1;

In binary this is:

00000000    // 0
00000001    // 1

If we want to turn that bit off again, instead of using AND and defining a new mask (11111110), we can use our FLAG1 mask and the NOT operator as follows:

settings = settings & ~FLAG1;

This reads quite intuitively: settings AND NOT FLAG1 turns off the first bit in settings. In binary:

00000001    // 1
11111110    // 254
00000000    // 0 – back to our original number

Note that applying the NOT operator to the flag generates the same binary sequence we would need to define as a new mask if we wanted to use AND alone (11111110). The NOT operator saves us a variable.

Can’t I just use XOR to turn this bit on and off?

Well spotted, yes you can!

settings = settings ^ FLAG1 // turns first bit on or off

The difference with XOR is a) you may not know if you are turning the bit on or off without checking the result (or input) as it’s just a switch, and b) XOR always has an effect, whether you intend it to or not.

With AND NOT you know you are explicitly turning a bit off, and if the bit is already off when you apply the mask, the result is unchanged.

Next week we’ll take a look at bit-shifting and summarise what we’ve covered with the four bitwise operators.

Bitwise XOR

Today we’ll look at the third out of four bitwise operators – bitwise XOR.

Bitwise XOR is represented by the symbol ^ and is an exclusive OR operation.

Can I see an example?

130 ^ 10 = 136

What is this actually doing?

Bitwise XOR compares each bit setting and if either one is set, sets the corresponding output bit to 1. However, if both bits are set, then the corresponding output bit is set to zero.

So to clarify, both OR and XOR compare each bit setting and if either one is set, sets the corresponding output bit to 1. However, if both bits are set, OR sets the output to 1, while XOR sets the output to zero.

In short, XOR gives a result of 1 only if the two inputs are different.

So the example above has bit comparisons as follows:

10000010    // 130
00001010    // 10
10001000    // 136

What would I use bitwise XOR for?

Let’s take a look at how we might use XOR.

Toggling with with XOR

XOR is primarily used to toggle bits on and off. Let’s say we have a byte which represents 8 boolean values and we want to turn the first two off and on again. We can use the same mask to toggle the bits we are interested in if we use the XOR operator.

10000111    // 135
00000011    // 3
10000100    // 132

Applying the mask turns off the last two bits.

10000100    // 132
00000011    // 3
10000111    //135

Applying it again turns the bits back on.

All the other bits remain unchanged. XOR is just like applying a switch – very useful in low level programming.

Next week we’ll take a look at bitwise NOT. Have fun!


Bitwise OR

Following on from last week’s look at the bitwise AND operator, this week I’m going to look at bitwise OR and provide an example of how you can use it.

Bitwise OR is represented by the | symbol.

Can I see an example?

130 | 10 = 138

What is this actually doing?

Bitwise OR compares each bit setting and if either one is set, sets the corresponding output bit to 1. So in the example above, we can see the actual bit comparisons as follows:

10000010    //130
00001010    //10
10001010    //138

Note that it doesn’t matter if one or both bits are set in what we are comparing. As long as either one is set, the output bit is set to 1.

What would I use bitwise OR for?

OK, an example follows – it’s much easier to understand the usefulness of these operators when you see them in action.

Turning on an individual bit

Remember last week we used bitwise AND to turn off an individual bit? Well bitwise OR allows you to do the opposite. By using a mask with the bits set that we want to turn on, we can modify the individual bits in any byte.

Let’s say we have a byte, containing 8 bits, which are used as true/false values. Without changing the settings of any of the other bits, we want to set the first bit to be true. We apply the mask 1 (decimal) as follows:

11000100    // 196
00000001    // 1
11000101    // 197

The result is that the first bit (that is, the right-most bit) is now set to 1, and the other bit settings remain unchanged.

That’s all there is to it!

Next week we’ll look at bitwise XOR.