Everything your computer does can be translated into bits. Bitwise operators perform operations on binary numerals to manipulate individual bits. This can be quite useful for programmatic functions such as Bluetooth where the individual bits in a package’s header are important or controlling different functions on a chip is a requirement. These operations can also be applied to apps for device drivers, compression software, graphics and more. These sensitive tasks require surgical skills and bitwise operations are the cornerstone of this programming practice.
To follow along with this tutorial by creating a .NET interactive notebook in Visual Studio Code. To create a new notebook navigate to View > Command Pallet and search for .NET Interactive: Create a new blank notebook. You will be prompted to select a .dib notebook and choose C# as the language.
Hover over the top or bottom of the first code block in the notebook to add new code blocks by clicking the “+ Code” button. Add a static using to System.Console and two integers as a code block. This will enable us to reference these variables later in the code of this the notebook.
using static System.Console; int a = 29; int b = 33;
Just like math has PEMDAS bitwise operators also have an order of precedence. AND has a higher precedence that OR/XOR. You can perform these bitwise operations on two integer operands. Each operation has its own unique characteristics which we will dig into.
AND (&)
The bitwise AND operator is where we check each bit for both numeric operands and if both operands have a 1 for the bit then the and is true and a new bit is added to the result. The numbers 29 & 33 both have a 1 and only a 1, so that is what is returned by the operation.
WriteLine(a & b); //Outputs 1
OR (|)
The OR operator sets a new bit to one if at least one corresponding bit of the two operands is set. When we look at the binary for the numbers 29 | 33 we can see a sum of 61 bits in total when we compare the bits.
WriteLine(a | b); //Outputs 61
XOR (^)
The XOR operator is true for each bit only when a single numeric bit has value. If both bits have value for a given bit then it is unset to zero. When we look at the result from 29 ^ 33 we can see how a sum of 60 is produced.
WriteLine(29 ^ 33); //Outputs 60
Left Shift (<<)
The shift left operator will shift all the bits towards the left by a variable number of specified bits. The left side of the left shift operand is the bit count, and the right side is number of bits to shift left. The bit positions that get emptied by the left shift are filled with zeros. We can see how 33 << 1 returns a value of 66.
WriteLine(33 << 1); //Outputs 66
Shift right (>>)
Shift right by a variable number of bits by filling removed columns with zeros if left operand is positive else negative. 33 >> 1 = 16 while -33 >> 1 = -17.
WriteLine(33 >> 1); //Outputs 16
IsEven
Because the first bit on the right-hand side is a one, anytime this bit has a value we know a number is even.
((num ^ 1) == num + 1)
NOT (~)
The bitwise NOT operator in C# is a tilde character ~. Unlike AND and OR, the NOT operator is applied to a single operand to its right. The NOT changes each bit to its opposite as zero becomes one, and one becomes zero.
Usages of Bitwise operations
Compression
Let’s think about how we could use bitwise operations to compress a file for example. The premise of compression is that the repeated bits should be assigned shorter codes making the file smaller. You can think of how morse code uses compression because the character ‘E’ is so common that it is assigned a 1. Compression works similarly to this as it is an efficient categorization of bits.
Arithmetic coding is a data compression technique that encodes a data string as a binary and stores frequently used characters with fewer bits and not-so-frequently occurring characters with more bits, resulting in fewer bits. This concept was created 50 years ago in the 1970s at IBM. A compression algorithm should create shorter intervals by using probabilities on repeated bits to predict the next assignment, this is called bit-packing. One way that this can be accomplished is by creating records of bits as a file is compressed, so you can know if a bit might be repeated. Using those records, you can predict what the next bits will be however we do not want to store bits of data unless we can absolutely use them.
A bit is a of uint[] to stored bools and each bool is stored in a bit of uint so the space it occupies is only one-eighht of a bool[]. Each bool is just 1 bit, and 8 bits can be stored in a byte. We can operate on these bits when performing batch operations to improve the efficiency of a compression algorithm. We need to store bits so that we can tell if they are potentially repeated. Normally uints take up 4 bytes/32 bits of space. This means that each uint is 32 binary digits.
Graphics manipulation
Bitwise operations can also be used to manipulate RGBA values in a graphical canvas. A given color for a pixel can be represented by red, green, blue or alpha values. The RGB values make up the primary color while the Alpha value represents opacity. RGBA values are usually stored in a 32 bit integer with 8 bits identifying each value.
RRRRRRRR GGGGGGGG BBBBBBBB AAAAAAAA
There are 2D graphical libraries that allow you to manipulate the colors of a pixel such as SkiaSharp or Maui.Graphics. Bitwise algorythms can be used when drawing pixels to create masks, flip colors, create cool filters and bitmap effects to alter an image.
Binary Search
Given a sorted array of n elements, how would you write a function that searches for a given element in an array. A easy approach to this is to do a linear search. A brinary search algorythm searches for a sorted array by repeatedly dividing the search interval in half. It begins with an interval covering the whole array then Ii the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half of the divide. Otherwise, narrow it to the upper half of the divide. This cycle repeatedly checks until the value is found or the interval is empty.
Microcontrollers
Microcontrollers are everywhere. They are in our home automation devices, tv remotes, toys, vehicles the technology literely powers many of the things we take for granted everyday but how do they work. A microcontroller is an integrated circuit (IC) device used to control areas of an electronic system using a microprocessor unit (MPU). These devices are optimized for embedded apps that require both processing capability, digital responsiveness, and access to electromechanical components.
The code used to program software for these devices may use bitwise operations to toggle a bit, clear a bit, test a bit, extract bits, or monitor a bit. These devices often dont pack a ton of power so the bit manipulations we make to the bytes must improve the overall efficiency of the software. This sort of low level programming is exactly what bitwise operations were created for so you will commonly use it here.
The example
For simplicity sake we will create an example that adds 1 to a number using bitwise operations. There are two approaches to solving this problem. To add one to a number (say 0011000111), we flip all of the bits after the rightmost 0 bit resulting in a value of 0011000000. Next, we flip the rightmost 0 bit also resulting in an answer of 0011001000.
int AddOne(int number)
{
var one = 1;
// Flip all the set bits until we hit a 0
while((int)(number & one) == 1)
{
number = number ^ one;
m <<= 1;
}
// flip the rightmost 0 bit
number = number ^ m;
return number;
}
There is a simpler approach to this problem however I found it useful to take the long approach first to get familiar with some of the bitwise operators.
~number = -(number+1) [ ~ is for bitwise complement ]
(number + 1) is due to the addition of 1 in 2’s complement conversion
To get (x + 1) apply negation once again. So, the final expression becomes (-(~x)).
int AddOne(int number) => (-(~number));
Summary
That’s it for my take on bitwise operations. Bitwise operations are a fantastic way to manipulate binary data to create new binary results. There are many bitwise algorithms out there which you can use in your solutions as the concept of bitwise operations has been around for over 50 years. I hope that my explinations helped and you learned a bit!