Bitwise operations involve working with individual bits stored in a computer’s memory. They perform actions on the individual bits within a binary representation of an integer value, which leads to an efficient manipulation and evaluation of binary data.
I have observed that many developers, even some experienced ones, lack a clear view on bitwise operations. In this article, I shine a light on them and hopefully help you get good with them. There’s an interactive playground embedded in this post so you can try every operation out as you read.
# Overview
# NOT, AND, OR, XOR
Bitwise NOT, AND, OR, operations are analogous to doing the corresponding logical operation bit by bit.
A description of these operations are given below, in case if you aren’t familiar with them.
| logical gate | description |
|---|---|
| NOT | negates the output. 0s turns to 1s and vice versa |
| AND | 1 when both inputs are 1; 0 otherwise |
| OR | 0 when both inputs are 0; 1 otherwise |
| XOR | 1 when inputs are different; 0 when they are same |
AND, OR, XOR
You can change the operation by clicking/pressing on the operator.
We do the AND operation, bit by bit, on the binary representation of 48, 27. Use the controls below to step through the bits. The corresponding truth table is shown below.
| A | B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
NOT
I want to mention a point which might cause confusion while getting started with bitwise NOT operation.
In a bitwise NOT operation, all the leading zeros will be flipped to a 1. This means varying number of leading zeros produce different outputs from the same input.
Use the buttons below to add/remove leading zeros to see what outputs are produced. You can see the output value (8) changes even though the input value (23) doesn't.
# SHIFTS
A bit shift operation moves all the bits by specific number of bits, in a specific direction. While doing so, some bits will be made vacant, and some will be pushed off. Shift operations are classified based on what happens to these pushed off and vacant bits.
| Name | Vacant bits | Pushed off bits |
|---|---|---|
| Arithmetic left shift | filled with 0 | discarded |
| Arithmetic right shift | for unsigned integers: filled with 0 | |
| Logical left shift | filled with 0 | |
| Logical right shift | ||
| Circular left shift | vacant bit is filled with pushed off bit | |
| Circular right shift | ||
SHIFTS
The shift is done on binary representation of the first operand. The second operand is the number of positions to be shifted. The bits can be shifted to either left or right.
You can change the operation by pressing on the operator.
affect the output of the shift when the bits overflow.
Supports 6 to 12.
LOGICAL SHIFT
The right-most digit are shifted off.
The vacant bit on the left side are filled with 0.
Usually, in most programming languages (including C/C++, Java, JavaScript and Python), only logical shifts are available.
Also note that in Python 3, the numbers are stored using arbitrary precision, which can be thought of infinite amount of zeros in front of the number.
CIRCULAR SHIFT
The vacant bit on the left side are filled with the bit pushed off from the right side
There is also a third type of bitwise shift: Arithmetic Shift. I have excluded it here, as it is analogus to logical shift when dealing with unsigned integers.
# Uses
Now, you might be asking why should we care about these bitwise operations at all? And here’s why I think it’s advantageous to learn about them.
Bitwise operations become extremely useful when optimizing algorithms and writing low-level system software.
As they operate on individual bits, they tend to be a lot faster compared to other operations such as division and modulo. We can optimize complex algorithms by switching out those expensive operations with equiavalent bitwise operations.
Bitwise operations are also used for efficient memory usage. Let’s say we have to store 5 boolean values. If we declare a variable for each, totally we will allocate 5 bytes (40 bits) in memory. Although a boolean value can be expressed using a single bit, boolean variables are usually allocated with a byte (8 bits). On a memory-limited device, for example Arduino Nano, the unused 7 bits on each boolean could have been put to good use. Instead of declaring 5 variables, we can store all those values in a single 8-bit integer variable, where each bit point to each boolean value (5-bit integers are enough, but we can’t have them). Bitwise operations allow us to read, write, and manipulate each value from that variable.
Note that bitwise operations come with cost: readability and maintainability. When a piece of code include one or more bitwise operations, many developers will probably have a hard time comprehending what the code does. Even the one who authored it, will need a few moments before all these funky-looking operations make sense. Be sure to keep it as readable as possible whenever you use bitwise operators.
Above, I have mentioned that these operations are faster than other
operations. Faster in terms of CPU cycles, not seconds. Computers we now use
can run more than a million CPU cycles in a second. And they have plenty of
memory. They can run software written with no optimization in mind in reasonable
amount of time. Bitwise operations wouldn’t make much difference usually.
And considering the readability cost, we may not want or need to apply the
above-mentioned optimizations using bitwise operations, generally.
However there may come a time when these optimizations are mandatory. Having a solid overview on these operations will be benefical in that case.