Programming In C: Bitwise Operators
This article is part of a series – How to Program Anything: C Programming
This article is a continuation on expressions that can be constructed in the C language. We’ve studied literal expressions in the previous article. This article will focus on expressions involving operators. If you remember, expressions are pieces of code that are executed right away to yield some kind of result, as opposed to a statement which may affect an entire program’s structure. An example of an expression could be the bitwise AND operator (&). When you AND two variables together the computer goes through each value bit by bit, and if two bits in the same placevalue are the same it passes through to the result.
Operators in C are half of the equation towards getting stuff done in your programs. The other half are the statements that make up the structure of a program, however, we have yet to get to that. Operators are basically actions that are taken in a program on the given data. It’s all well and good to define variables, which we’ve been doing so far, but we have to be able to do something with those variables.
Operators can be split up into five main classes: program, arithmetic, bitwise, logical, and relational. We covered arithmetic operators in a previous article in the series. We also already covered relational and logical operators in this article. In this article we focus on the bitwise operators.
As written previously, C is a middle-level language. This means that it offers the expressiveness and ease of use of a higher-level language, but still maintains the ability to control things at a low-level. This basically means that we can construct higher-order programs in C, but still stay close to the processor. C as a middle-level language was designed to take the place of assembly language and it wouldn’t be able to do this without being able to operate on the binary representations, or bits, of any particular value. When we say an operation is bitwise we are referring to the actual manipulation of the exact bits in a variable or value. Because their binary representation is quite complex you cannot perform bitwise operations on floats or doubles. Only ints or chars are available for us to tinker with.
The following is a list of the bitwise operators:
- & (AND)
- The AND bitwise operator
- | (OR)
- The OR bitwise operator
- ^ (XOR)
- The EXCLUSIVE OR (XOR) operator
- ~ (NOT)
- The NOT bitwise operator
- >> Shift Right/dt>
- Shift the bits to the right
- << Shift Left
- Shift the bits to the left
You’ll notice a similarity between three of the bitwise operators and their corresponding logical operators. While the logical operators work on overall truth values (1 or 0) and return simple truth values, the bitwise operators go through a value bit by bit and apply the same logic to each bit in the sequence. The logic employed is called boolean logic, and is named after George Boole whom I wrote about in an article on binary titled Algebraic Tron. It’s a good read and gives you a larger idea about the type of boolean operations we’re going to be performing.
The & Bitwise Operator
As written, the & bitwise operator (AND) goes through each of its operands values bit by bit. It lines them up like you might be doing an addition, and compares each placevalue in each operand to each other. The result is placed in the same placevalue in a return value. The truth table I set up for the AND operator is as follows:
With this truth table in hand, we can examine what I mean when I say that the operator goes through a value step by step. In order to understand how we reach the binary values we do from the values of the integers I highly suggest you read the article series I did on the binary counting system here. I assume in this article that you know how to convert a decimal number into it’s binary representation. Let’s take two char values, 34 and 55 and & them, resulting in a new value. We can visualize the whole thing according to this code snippet:
char x, y, r; x = 34; y = 55; r = x & y; /* 34 -> 00100010 55 -> 00110111 & -v ---------------- 00100010 -> r */
As you can see in the code snippet’s comment, the & operator goes through each bit placevalue by placevalue, and compares the two together. It then returns as it’s expressions result the byte that was constructed. In this case its 00100010. Each place where there were two ones in each operand there is a one in the result, otherwise there’s a 0.
The & operator is useful when you want to clear bits away from a given variable. Say you’re only interested in the first three bits of a value, but there are other bits that are cluttering it up. It would be hellish to construct a bunch of relational operations to tease out the values of those three bits (and may not even be possible), but with an & operator, you simply need to & the value with 00000111. Only the bits where there is a 1 are going to transfer through, so voila, a clean value.
In fact, a nifty programming trick uses the & operator just like this. Say you have a set of “flags”, true or false values, you want to store neatly in memory. Rather than waste a whole char for each flag, you can pack all the flags into one char, one for each bit. This way you can pack eight flags into one byte. When you are interested in the value of any one of the flags you just & it with a binary representation that has just that placevalue set to 1.
The | Bitwise Operator
The | bitwise operator (OR) also goes through each of its operands values bit by bit. However, this time if one, the other, or both are equal to 1 then the result is 1. Just like the & operator it proceeds through the value’s placevalues. The truth table I set up for the OR operator is as follows:
From this table we can see that we’ll get a 1 every time any of the other operands has a 1 in the examined placevalue. We can examine this operation in the following code snippet:
char x, y, r; x = 34; y = 55; r = x | y; /* 34 -> 00100010 55 -> 00110111 | -v ---------------- 00110111 -> r */
As you can see in the code snippet’s comment, the & operator goes through each bit placevalue by placevalue, and compares the two together. It then returns as it’s expressions result the byte that was constructed. In this case its 00110111. Each place where there were any ones in each operand there is a one in the result, otherwise there’s a 0.
Following our flags example from the previous operator, you can see where this operator would come in handy. We use the & operator to test the value of a flag, well, we use the | operator to set the value of a flag. If we want to flip the 7th flag in the char we just | it with 01000000 and then store the result back in the original variable using perhaps a compound assignment such as a |= 0x
The ^ Bitwise Operator
The ^ bitwise operator (Exclusive OR, or XOR) also goes through each of its operands values bit by bit. However, this time if one or the other bits are equal to 1 then the result is 1, but if both bits equal 1 or 0 the result is 0. Just like the | and & operators, it proceeds through the value’s placevalues. The truth table I set up for the XOR operator is as follows:
From this table we can see that we’ll get a 1 every time either one of the operands has a 1 in its placevalue, but not if both are the same. We can examine this operation in the following code snippet:
char x, y, r; x = 34; y = 55; r = x ^ y; /* 34 -> 00100010 55 -> 00110111 ^ -v ---------------- 00010101 -> r */
As you can see in the code snippet’s comment, the ^ operator goes through each bit placevalue by placevalue, and compares the two together. It then returns as it’s expressions result the byte that was constructed. In this case its 00010101. Each place where there were any ones in only one of the operands there is a one in the result, otherwise there’s a 0.
The ~ Bitwise Operator
The ~ bitwise operator (NOT, or one’s complement) also goes through each of its operands values bit by bit. However, this operator is a unary operator (having one operand), although it doesn’t alter it’s operand. It simply is used for the result it returns. The idea with the ~ operator is that wherever there is a 1 in the operand, then output a 0, and wherever there’s a 0 output a 1. Essentially it just flips bits to be their opposite. The truth table I set up for the NOT operator is as follows:
From this table we can see that we’ll get a 1 for every 0 in the operands binary representation, and the opposite for every 0. We can examine this operation in the following code snippet:
char x, y, r; x = 34; r = ~x; /* 34 -> 00100010 ~ -v ---------------- 11011101 -> r */
As you can see in the code snippet’s comment, the ~ operator goes through each bit placevalue by placevalue, and compares the two together. It then returns as it’s expressions result the byte that was constructed. In this case its 11011101. Each bit was reversed into its opposite value. Note again that this operand doesn’t alter the operand, only returns a result that is the opposite.
The Bit Shift Operators
The two bit shift operators, >> and <<, are somewhat special operators. They take two operands, one being a value, and the other right-hand one being a number. Their goal is to “shift” the bits of the value to the left or to the right by the number given on the right hand of the operator. Their syntax can be summed up by the following:
value >> number to shift value << number to shift
These operators, like the other bitwise operators, don’t alter the original operand but return a new result.
Intuitively you might think that the shifts of bits “wraps around”, where a 1 dropping off one side shows up on the other side. You’d be wrong. Any bits that shift off one end of the value are lost, and any additional bits shifted onto the other end or set as zero.
NOTE: If you are shifting a signed negative integer to the right, a 1 will be brought in instead of a 0 so that the sign bit is remains the same.
A code snippet might better illustrate the intentions of these operators:
char y, r; y = 55; r = y << 1; /* 55 -> 00110111 << 1 -v 01101110 --> r */ r = y << 4; /* 55 -> 00110111 << 4 -v 01110000 --> r */ r = y >> 2; /* 55 -> 00110111 >> 2 -v 00001101 --> r */
One use of such a strange operator is to quickly multiply a value by 2 or divide a value by 2. A shift to the left efficiently multiplies a number by 2 (provided it doesn’t run off the edge and lose a bit), while a shift to the right quite efficiently divides by 2 (provided again a bit doesn’t run off the edge). This is highly useful in many applications, particularly in speeding up graphical calculations as well as different kinds of encryption techniques.
Order of Precedence
Bitwise operators are computed in a certain order when in relation to each other. The idea is that the operators are processed from left to right one before the other. That is the XOR operator computes before the | operator. Here is the list of the order of operations for the bitwise operators:
- ~ (Not, or One’s Complement)
- << and >> bitshift operators
- & (the bitwise AND operator)
- ^ (the bitwise XOR operator)
- | (the bitwise OR operator)
Parentheses can always affect this order. Parenthese are evaluated from the innermost first to the outermost, but wherever they are they bump the evaluation up so that it happens before normal precedence. The following two expressions evaluate like so:
a | b ^ c // b ^ c is evaluated, then that result with a (a | b) ^ c // a | b is evaluated, then that result with c
By incorporating bitwise operations in its core language, C provides a way to program low level processor specific operations inside a more structured program (as compared to assembly). C lets us perform ands, ors, exclusive ors, and one’s complement operations to chars and ints. Remember that because of their complex binary representation C doesn’t allow these types of operations on floats or doubles. By utilizing bitwise operations we can perform some nifty tricks including hosting binary flags in one variable, encryption, and fast multiplication and division.
This article is part of a series – How to Program Anything: C Programming
If you appreciate this article you might consider supporting my Patreon.
But if a monthly commitment is a bit much, I get it, you might consider buying me a coffee.