Bitwise operators in C

In last week's post I very briefly mentioned bitwise operators. This week's post is going to look at bitwise operators in detail. If you're already familiar with bitwise operators, feel free to skip this post.

Chars, Integers and bits

In C numeric types such as integers are stored using binary. For example 18 is 10010 in binary, and would therefore be stored with bits similar to the following:

0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0

The exact number of leading bits will vary depending on the data type and compiler used, however C specified unsigned integers must contain at least the range 0 to 65535. Therefore integers must be at least 16 bits long (216 - 1 = 65335). To simplify the rest of this post all subsequent examples with use unsigned chars, and assume the maximum possible unsigned char value is 255.

Printing bits

Unfortunately printf doesn't have a built in way to print a binary representation of a char. To get around this a function similar to the following can be used:

void print_bits(unsigned char x)
{
    int i;

    for (i = sizeof(unsigned char) * 8 - 1; i >= 0; i--)
        printf("%d", (x >> i) % 2);
}

The function above will print a binary representation of a number, for example print_bits(18) should output the following line:

00010010

Bitwise AND

In C the logical AND operator (&&) will return 1 if both operands are true, otherwise it will return 0. The table below shows possible outcomes for a && b, where a and b are either 0 or 1:

b = 0b = 1
a = 000
a = 101

The bitwise AND operator (&) carries out the same logic, but for each individual bit. For example consider the following:

unsigned char a = 155;
unsigned char b = 171;
unsigned char c;

c = a & b;

In the example above, a would be represented by the following bits:

1 0 0 1 1 0 1 1

And b would be:

1 0 1 0 1 0 1 1

The & operator will go through each bit in a and b and perform a logical AND. The leftmost bit in both a and b is 1, therefore the first bit will be 1:

1

The next bit will be 0, because it's 0 in both a and b:

1 0

Once each bit is evaluated, the following value will be assigned to c:

1 0 0 0 1 0 1 1

Bitwise OR

The logical OR operator (||) also has a bitwise equivalent. The following table shows potential outcomes when bit a is compared to bit b:

b = 0b = 1
a = 001
a = 111

The bitwise equivalent of || is |:

unsigned char a = 155;
unsigned char b = 171;
unsigned char c;

c = a | b;

In the example above, a would be represented by the following bits:

1 0 0 1 1 0 1 1

And b would be:

1 0 1 0 1 0 1 1

And the resulting value assigned to c would be 187:

1 0 1 1 1 0 1 1

Bitwise OR (exclusive)

The bitwise OR operator is normally inclusive, that is if both bits are 1, the result will be 1. C also has an exclusive bitwise OR (^). Unlike the inclusive bitwise OR, if both bits at a given position are 1 the resulting bit will be set to zero:

b = 0b = 1
a = 001
a = 110

For example if an exclusive OR is used:

unsigned char a = 155;
unsigned char b = 171;
unsigned char c;

c = a ^ b;

The resulting value of c will be 48, instead of 187:

0 0 1 1 0 0 0 0

Bit shifting

There are two bit shifting operators, left shift (<<) and right shift (>>). These operators move each bit either left or right a specified number of times. For example:

unsigned char x = 7;

printf("%d\n", x); /* print 7 */

x = x << 2;
printf("%d\n", x); /* print 28 */

x = x >> 2;
printf("%d\n", x); /* print 7 again" */

In the example above x starts of as the following:

0 0 0 0 0 1 1 1

The bits in x are then shifted to the left twice, the blank bits on the far right are filled in with zeros:

0 0 0 1 1 1 0 0

Note: each shift effectively doubles the value, therefore the final value is 28 (7 * 2 * 2).

Finally the value is shifted back two places by the right shift operator, and the two bits on the far left are replaced with zeros:

0 0 0 0 0 1 1 1

It's important to note that the shift operators will truncate bits. This can be demonstrated with the following code:

unsigned char x = 1;
x = (x >> 1) << 1;

In the example above x is shifted right then left, however doing this will effectively lose the right hand bit and x will end up as 0.

Ones' complement

Unlike the bitwise operators above, the ~ operator is a unary operator; therefore it only takes a single operand. Each bit in the operand is inverted, so 1 becomes 0 and zero becomes 1. For example:

unsigned char x = 142;
x = ~x;

In the code above x starts as 142:

1 0 0 0 1 1 1 0

Each bit is then flipped and 113 is assigned to x:

0 1 1 1 0 0 0 1

Note: an unsigned number and it's complement should always add up the maximum possible value for that data type. This happens because each position will always have a 1 and a 0, so adding the two together will result in each bit being set to 1. This is useful if you want to quickly work out an unsigned numbers compliment, to do this you can just subtract the number from the maximum possible value for that data type.