This article is part of the sequence The Basics You Won’t Learn in the Basics aimed at eager people striving to gain a deeper understanding of programming and computer science.
Last time, we talked about character sets and encoding. This time, we will return to dealing with binary numbers. However, this time we won’t examine how binary numbers work and what is their nature. We have covered that in previous articles. Today, we will see how to apply that knowledge in practice by examining how bitwise operations work.
This topic is usually neglected in a traditional computer science curriculum (At least it is in some universities I know). But I think that this knowledge can be useful for two reasons:
- Expanding your computer science knowledge by gaining a deeper understanding of binary numbers and of low-level computer science aspects.
- Gaining a valuable tool which can be useful when pursuing specialization as a low-level programmer (Embedded developer, for example).
We will start by examining what tools do we have at our disposal – the operations which modern programming languages provide us with. Then we will move on to applying that knowledge for actually manipulating numbers in a binary fashion and finally – we will see some real-world examples of how bitwise operations are used to achieve a highly efficient system.
Bitwise operations
These operations are performed using operands, which are pretty close to the logical operators we already know:
& – Bitwise AND
| – Bitwise OR
^ – Bitwise XOR
~ – Negation
<< – Shift left
>> – Shift right
The first four operations should be familliar. The logical equivalents, act on boolean expressions, which can be either true or false and result in a boolean expression which can be either true or false, as well. The bitwise operators, on the other hand, don’t act on boolean expressions. They act on the individual bits of a number directly. This chart summarizes their action:
And here is an example to further clarify your understanding:
The negation (~) operator is unary. That is, it takes only one integer operand and negates all of the bits of the supplied number. All 1s become 0s and 0s become 1s.
The aforementioned operators should be familiar to you. The last two operators, however, are something new.
The shifting operators (shift left (<<) and shift right (>>)) take a number and shift all its bits to the left or right by some value.
Whenever a bit goes out of scope, it is discarded. That is why you should be careful with these operators.
What you might notice, is that applying these operations result in a very familiar result.
It turns out, that shifting right is functionally equivalent to integer division and vice versa.
For example:
12 >> 1 results in: 6
5 >> 1 results in 2 (1 bit goes out of scope)
These are the bitwise operations which programming languages supply you with. They might seem quite a few and simple, at first, but combined together, they can result in a powerful functionality.
Basic usage
Now, we will explore some of the most basic ways you can use bitwise operations. The following routines help you extract bits from a number and set bits at a given position. When you combine the, you can achieve much more sophisticated results.
Identifying a bit at a given position
One of the first things we might want to see is what kind of bit does the number have in a given position. For example, let’s say we want to see the value of the bit at position 3 (starting from zero) from the number 62.
What we have to do is first shift the number to the right 3 times. That way, the bit of interest will be in position 0 in the resulting number. Next up, we can apply the bitwise AND operation to the result and the number 1. That way, we are assured that all the bits in positions greater than 0 will be set to zero. And that gives us the desired final result. We see that the bit at position 3 is a one.
int num = 62; // 0011 1110 int pos = 3; int mask = num >> pos; // 0000 0111 int result = mask & 1; // 0000 0001 Console.WriteLine(result);
Setting a one at a given position
Another common task might be to set a bit at a given position. This task can be broken up into 3 different tasks as the routine differs based on what bit do we want to set. First up, we will explore the task of setting a one in a given position.
Let’s say we want to set a 1 to position 5 of the number 72. This time, we shift the number 1 to the left by 5. The resulting number in programming jargon is called a mask. So what we have now is a number which has all zero bits except for the position we are interested in. Now, the final step is to apply the operation bitwise OR between the initial number and the mask.
The OR operation has the following property:
0 | X = X
That means that if you apply the OR operation between a zero and any other number, we will get the other number. In our case, that means that the bits of our initial number will be preserved as they are, since they have been OR-ed with zeroes. Except for the bit of interest, it will result in a one independently of its value thanks to this property:
1 | X = 1
int num = 72; // 0100 1000 int pos = 5; int mask = 1 << pos; // 0010 0000 int result = num | mask; // 0110 1000 Console.WriteLine(result);
Setting a zero at a given position
Now, if we want to set a zero at a given position, it will be more tricky.
For this example, we will set the bit at position 3 to zero of the number 62.
We start off in a similar fashion as the last routine. Shift the number one 3 times to the left so that we get a number which has a one in the designated position and zeroes everywhere else. At this point, though, there is no operation that can set the desired bit to zero in all cases.
But what we can do, is negate the number we got. That way, all the bits of the number will be set to 1 except for the designated bit, which is set to 0. Now, we again take advantage of some properties of the OR operation and we apply the bitwise OR between the number we got and our initial number. This gives us the result we desired and it works even if the bit at the given position was 0 initially.
int num = 62; // 0011 1110
int pos = 3;
int mask = 1 << pos; // 0000 1000
mask = ~mask; // 1111 0111 (this is actually a 32 bit number,
// but I am omitting the leftmost bits)
int result = num & mask; // 0011 0110
Console.WriteLine(result);
With this approach, though, you should be very careful about the types of the numbers you use. Make sure they are the same type. Otherwise, you can get to a situation in which you shift an integer number by 33 positions and it goes out of scope. The operations from then on, will produce wrong results.
long num = 8589934654; // 0000 0010 (33th bit)
// ... ... 0011 1110
int pos = 33;
long mask = 1 << pos; // 0000 0010 (33th bit)
// ... ... 0000 0000
mask = ~mask; // 1111 1101 (33th bit)
// ... ... 1111 1111
long result = num & mask; // 0000 0000 (33th bit)
// ... ... 0011 1110
Console.WriteLine(result);
This code will give an erroneous result. What we have is a number, which has a 1 in the 33 bit position, and we are trying to set it to zero. However, the 1 we are shifting is an integer and when we try to shift it by 33 positions, it goes out of scope and the mask at this point becomes 0. The correct way of performing this operation:
long num = 8589934654; // 0000 0010 (33th bit)
// ... ... 0011 1110
int pos = 33;
long mask = (long)1 << pos; // 0000 0010 (33th bit)
// ... ... 0000 0000
mask = ~mask; // 1111 1101 (33th bit)
// ... ... 1111 1111
long result = num & mask; // 0000 0000 (33th bit)
// ... ... 0011 1110
Console.WriteLine(result);
Inverting a bit at a given position
The final routine can be used as a substitute for the routines we just discussed. However, in order to use it, you will need some initial info about the bit you want to set as it always inverts the bit independent of its initial value.
Let’s say we want to invert the bit at position 3 of the number 62 (again).
Again, we shift a 1 to the left 3 times. This time, we use one of the most underestimated operators in programming logic – the XOR (Exclusive OR).
If we apply the XOR operation between the initial number and the number we got by shifting the one, the bit at the designated position will be inverted independent of its initial value. All other bits remain the same. We achieve this effect due to the following properties of the XOR operator:
0 ^ X = X
1 ^ X = !X (The opposite of X)
int num = 62; // 0011 1110 int pos = 3; int mask = 1 << pos; // 0000 1000 int result = num ^ mask; // 0011 0110 Console.WriteLine(result);
Real-world issues
I have shown you the basic things you can achieve using bitwise operations. However, a good question arises which is – how can we use this?
For this purpose, I will present to you two real world issues which can be solved using bitwise operations.
The first one has a rather limited applicability. Bitwise operations are used when the software has to communicate with a hardware component. If you want to display something on a small black and white screen, for example, you send an array of numbers, whose bits represent the cells of the display. In order to set a pixel on or off, you have to manipulate a bit from those numbers. That can be done using bitwise operations.
Another issue is rather high-level. Imagine that you have a set of elements and you want to designate whether a certain event has occurred to each one of those elements. For example, you have an array of words and you want to designate whether a word has appeared in a text.
An initial approach is to allocate a boolean array equal to the count of the words. The boolean value at a given index indicates whether a word at the same index from the other array has occurred or not in the text. Fair enough. However, if the words you want to check become a lot, the overhead for upkeep of the other array in terms of memory becomes high.
What we can do instead, is use an array of numbers and the bits of those numbers serve the same purpose as the boolean array we just talked about. Let’s demonstrate the difference in terms of memory with an example.
For simplicity, let’s say we have 32 words. If we allocate an array of 32 boolean values, that gives us 32 * 1 = 32 bytes of memory. Note that a boolean takes up 1 byte in normal cases.
Instead, we can use one 32 bits number and the bits of the number show which words have been used. That way, instead of taking up 32 bytes of memory, we take up only 4 bytes (32 bits = 4 bytes).
If we have more than 32 values, then we need an array of numbers and a set of sophisticated routines for easily manipulating this “bit array”.
Conclusion
Bitwise operations can be a powerful tool in the hands of a programmer, who pursuits a high-performance system. Of course, this knowledge is not always applicable in a high-level context, but there are situations, in which this can serve as a great tool for optimization.
Furthermore, dealing with binary numbers is a fundamental topic for anyone aiming to specialize as a low-level developer as it is often used to achieve a highly-efficient interface with the skeleton of the computer system – the hardware.
But whenever you use bitwise operations in your project, make sure to spend some time hiding the raw binary operations you perform behind some more high-level abstractions such as classes or functions. Reading code, which uses binary operations can be a real headache.
Next time, we will discuss some of the most popular sorting algorithms. But not with the aim of learning how they work, but rather how we can efficiently use them to solve real-world issues.
