C Bitwise Operators

When I got laid off I decided that I had some extra time to finally go through the book “The C Programming Language” by Kerninghan and Ritchie (aka “K&R C Book”). I got through the first chapter without too much issue but the section on bitwise operators in the second chapter had left me stumpped. Most of the stuff on bitwise operators is easy to understand, but when you start trying to do the exercises you realize that the book’s content on this subject is a little lacking for what the exercises want you to do. I’m going to spend some time today going over bitwise operators and hopefully help any future would-be C developers understand this subject.

What Are Bitwise Operators

Bitwise operators are operators that allow you to manipulate data at the bit level. Just to be upfront, an little understanding of binary numbers is going to help in a bit way as we talk about these operators. There are six operators that we’re going to focus on: AND, OR (inclusive), OR (exclusive), NOT, left shift and finally right shift.

Binary Numbers

Before we jump right in though, lets look at binary numbers. Since we’re dealing with bitwise operators and dealing with things at a bit level, it’s helpful to make the distinction between a bit and byte. A bit is a single binary digit that can be a 1 or a zero (0). A byte is made up of 8 bits. So lets look at a byte of integer data.

Below is the number 30 in binary form.

[text]
Postition #: 7 6 5 4 3 2 1 0
Bit: 0 0 0 1 1 1 1 0
[/text]

It’s important to note that the “Position #” represents the value of 2 to the power of the number (2^#) so position 3 is 8 because 2 to third power (2^3) is equal to 8. So in this case we add (16+8+4+2) to equal 30. Lets look at the other number we’ll be using in our examples, 115.

[text]
Postition #: 7 6 5 4 3 2 1 0
Bit: 0 1 1 1 0 0 1 1
[/text]

Now we have to the two numbers (30 & 115) that we’ll be spending most of our time looking at. So lets move on to the actual operators themselves.

AND Operator

The AND operator (&) will take any bits where both bits are set to 1. So in the case of 30 & 115 we’ll get 18.

[c]
#include <stdio.h>

main() {
i = 115;
j = 30;
k = i & j;

printf("\n%d & %d = %d\n", i, j, k);
}
[/c]

[text]
Output: 115 & 30 = 18
[/text]

So lets look at this at the bit level:

[text]
76543210 — Position
01110011 &
00011110
————–
00010010
[/text]

As we can see, we only saved the bits where both bits in both numbers were set to 1.

OR (inclusive) Operator

There are two kinds of OR operators, inclusive and exclusive and we will be looking at both today. First we’ll look at the inclusive OR operator (pipe, |). The inclusive OR operator will take bits from both numbers where either bit is set to 1.

[c]
#include <stdio.h>

main() {
i = 115;
j = 30;
k = i | j;

printf("\n%d | %d = %d\n", i, j, k);
}
[/c]

[text]
Output: 115 | 30 = 127
[/text]

And at the bit level:

[text]
76543210 — Position
01110011 |
00011110
————–
01111111
[/text]

As you can see, in the case of using the inclusive OR on 115 and 30, we get 127.

OR (exclusive) Operator

Now lets have a look at the exclusive OR operator (carrot, ^). Here the only bits carried over are those where only one of the two bits is set to 1. Lets look at an example.

[c]
#include <stdio.h>

main() {
i = 115;
j = 30;
k = i ^ j;

printf("\n%d ^ %d = %d\n", i, j, k);
}
[/c]

[text]
Output: 115 ^ 30 = 109
[/text]

And what happens at the actual bit level:

[text]
76543210 — Position
01110011 ^
00011110
————–
01101101
[/text]

NOT Operator

The final bitwise operator I want to look at is the NOT operator. This is represented by the tilde sign (~). What this operator does is reverse the settings of all the bits. If a bit is set to 1 it gets set to 0 and vice versa. This one is tricky though and it took me a a while to fully understand it because it doesn’t act the way you expect in all circumstances.

If you use signed ints, the result of ~115 is actually -116 (or -115-1). If you used unsigned ints, the result will be the same. But if you use unsigned short ints (and you actually specify as such in your code), the result of ~115 is actually 65420. Now you might be wondering what happened there. Well, when you do “unsigned short” integers, you’re actually using 2 byte integers (or 16 bit integers), those look like

[text]
76543210 76543210 — Position
11111111 10001100
[/text]

You’ll notice that the last 8 bits are the reverse of the bits for 115? Well, that’s what the NOT operator does remember? It flips all the bits. After 128 (or 2^7), you just continue multiplying by two, so the second set of bits starts as 256, then 512, then 1024, and so on.

Here’s some basic things you need to know.

[c]
~0 = 65535
~(~0) = 0
[/c]

The first one takes a byte where all the values are 0 and changes them all to 1’s. So every bit is on, thus ~0 will be the maximum value of the integer type. The reverse, ~(~0) is fliping the flipped bits, and thus those bits are being flipped twice. Once to the “ON” position (all 1’s) and then again to the “OFF” position (all 0’s).

Left Shift Operator

The final two operators we will look at today are the left and right shift operators. We’ll start by looking at the left shift operator (<<).

[c]
#include <stdio.h>

main() {
i = 4;
j = i << 2;

printf("\n%d << 2 = %d\n", i, j);
}
[/c]

[text]
Output: 4 << 2 = 16
[/text]

So lets look at this at the bit level:

[text]
76543210 — Position
00000100 << 2
————–
00010000
[/text]

Right Shift Operator

Finally, we’re going to peek at the right shift operator (>>) and if you guessed that this does the exact opposite of the left shift operator, you’d be one hundred percent correct.

[c]
#include <stdio.h>

main() {
i = 4;
j = i >> 2;

printf("\n%d << 2 = %d\n", i, j);
}
[/c]

[text]
Output: 4 >> 2 = 1
[/text]

So lets look at this at the bit level:

[text]
76543210 — Position
00000100 >> 2
————–
00000001
[/text]

Conclusion

There you have it, all the bitwise operators in the C programming language. Note that these can be used in other languages as well, in fact there are several questions over on StackOverflow about when a good time to use bitwise operators is and in different languages. In the near future I’ll look at doing some complex things with these operators (specifically one of the exercises from the K&R book). But this should at least give you a nice overview of bitwise operators.

Advertisements
This entry was posted in programming and tagged , , . Bookmark the permalink.