Binary 010: The Uses of Bit Shifting and Bitwise Operations
- Mia Combeau
- Computer science
- May 7, 2022
Table of Contents
Computers only know one language: binary. Our many programming languages allow us to give instructions in a human-readable format, which are then translated into long sequences of 0s and 1s. Although this level of abstraction is essential to us humans, it can be useful and even much more efficient to manipulate bits directly, thanks to bit shifting and bitwise operations.
We previously had the opportunity to examine how binary works and how computers do basic calculations. Here, we will discover the operators that allow us to manipulate bits and why we might want to use them.
Bit Manipulation Operators
In programming languages that allow low-level bit manipulation, such as C, the operators are as follows:
| Operator | Description |
|---|---|
| « | shift all the bits of a bit field to the left |
| » | shift all the bits of a bit field to the right |
| & | AND : logical operator to compare two bit fields |
| | | OR : logical operator to compare two bit fields |
| ^ | XOR : logical operator to compare two bit fields |
| ~ | NOT : complement by bit |
In order to take a closer look at each of these operators, let’s create a small C program. It will print out the 32 bits of an unsigned integer with spaces for readability. Sadly, printf does not offer any specification to print an integer in base 2. Which means we need to write our own function to format our binary number correctly. We will have two files, bitwise.c which we will modify over the course of this article to test each bitwise operator, and ft_unsigned_itoa_base.c for formatting. Here is the source code :
- bitwise.c
- ft_unsigned_itoa_base.c
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb;
char *nb_str;
nb = 242;
nb_str = ft_unsigned_itoa_base(nb, 2);
printf("Binary number:\t\t%s (Decimal: %010u)\n", nb_str, nb);
free(nb_str);
return (0);
}
#include <stdlib.h>
/* ft_itoa_len:
* Measures the length of the string of an unsigned integer.
*/
static unsigned ft_itoa_len(unsigned n, unsigned base)
{
unsigned len;
len = 0;
if (n == 0)
return (1);
while (n >= 1)
{
len++;
n /= base;
}
return (len);
}
/* ft_num_to_str:
* Translates an unsigned integer into a string
* depending on the given base.
*/
static char *ft_num_to_str(unsigned n, char *str, unsigned len, unsigned base)
{
if (base > 16)
return (NULL);
str = malloc(sizeof *str * len + 1);
if (str == NULL)
return (NULL);
str[len] = '\0';
len--;
while (len)
{
str[len] = "0123456789ABCDEF"[n % base];
n /= base;
len--;
}
str[len] = "0123456789ABCDEF"[n % base];
return (str);
}
/* ft_pad_zeros:
* Adds leading zeros to a number string if needed.
*/
static char *ft_pad_zeros(char *str, int len)
{
char *padded;
int i;
int j;
padded = malloc(sizeof *padded * 33);
if (!padded)
return (NULL);
i = 32;
padded[i] = '\0';
i--;
while (--len >= 0)
{
padded[i] = str[len];
i--;
}
while (i >= 0)
{
padded[i] = '0';
i--;
}
free(str);
return (padded);
}
/* ft_add_spaces:
* Adds spaces to a binary number string.
*/
static char *ft_add_spaces(char *str)
{
int i;
int j;
char *spaced;
spaced = malloc(sizeof *spaced * 41);
if (!spaced)
return (0);
spaced[41] = '\0';
i = 0;
j = 0;
while (str[i])
{
if (j % 5 == 0)
spaced[j] = ' ';
else
{
spaced[j] = str[i];
i++;
}
j++;
}
free(str);
return (spaced);
}
/* ft_unsigned_itoa_base:
* Takes an unsigned integer and a base (2 = binary,
* 10 = decimal, 16 = hexadecimal) as parameters.
* Returns the string corresponding to the given number.
* If the base is binary, the string will be formatted to
* show the 32 bits separated by spaces for legibility.
*/
char *ft_unsigned_itoa_base(unsigned int n, unsigned int base)
{
unsigned int len;
char *str;
len = ft_itoa_len(n, base);
str = ft_num_to_str(n, str, len, base);
if (base == 2)
{
if (len < 32)
str = ft_pad_zeros(str, len);
str = ft_add_spaces(str);
}
if (!str)
return (NULL);
return (str);
}
Output :
With this little program, we will be able to easily observe the effects of bitwise and bit shifting operators on an unsigned integer. Let’s start with bit shifting.
Bit Shifting
Bit shifting is a simple operation during which all the bits in a field are shifted a certain number of positions to the right or left. Let’s try to see this effect with out program. First, we will move all the bits of our unsigned integer one step to the right, and then 10 steps to the left:
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb;
unsigned int nb_mod;
char *nb_str;
nb = 242;
nb_str = ft_unsigned_itoa_base(nb, 2);
printf("Binary number:\t\t%s (Decimal: %010u)\n", nb_str, nb);
free(nb_str);
nb_mod = nb >> 1;
nb_str = ft_unsigned_itoa_base(nb_mod, 2);
printf("Bitshift 1 right:\t%s (Decimal: %010u)\n", nb_str, nb_mod);
free(nb_str);
nb_mod = nb << 10;
nb_str = ft_unsigned_itoa_base(nb_mod, 2);
printf("Bitshift 10 left:\t%s (Decimal: %010u)\n", nb_str, nb_mod);
free(nb_str);
return (0);
}
In this result, we can see that the bits were indeed shifted one step to the right, and then 10 steps to the left. We can also see that zeros come to replace the shifted bits, which changes the value of our number drastically, albeit predictably.
As a matter of fact, shifting bits towards the right amounts to dividing our value by 2 to the power of the number of steps the bits were shifted. Shifting them to the left is the same as multiplying the value by 2 to the power of the number of steps shifted. Our original value was 242, when we moved the bits 10 steps to the left, our value was multiplied by 2 power of 10 (1024) : 242 x 210 = 247,808.
However, if we wish to use bit shifting for multiplication, we can’t forget that if the number is large, there is a good chance we might loose the most significant bit, which would distort the result. In addition, the examples we are using in this article are unsigned integers, but if the number is negative and negative numbers are represented with two’s complement, the sign bit might be altered during a bit shift to the left.
For example, if our data type is 8 bits maximum (a char):
Unsigned binary integer: 1011 0111 (183)
Left shift by 1: 0110 1110 (110)
But 183 * 2 = 366, not 110...
We have lost the most significant bit to the left because of
the overflow!
Signed binary integer: 1011 0111 (-73)
Left shift by 1: 0110 1110 (+110)
But (-73) * 2 = -146, not 110...
Here, we lost the most significant bit that indicated the sign!
Binary Logical Operations
The other operations we can do on a binary number are logical ones. These operators are identical to the logic gates of an electronic circuit: they take one or two inputs and produce an output. They are the AND, OR, XOR, and NOT operators, which are the very foundations of computer processing. Every computer calculation is inextricably linked to this physical logic. Let’s see how each of these operators work.
Bitwise NOT Operator (~)
Unlike the operators shown below, the bitwise NOT operator works with a single input. Simply put, it outputs the exact opposite of a bit field. That is, if the bit is at 0, the NOT operator returns 1, if the bit is at 1, it returns 0.
A tilde, ~, represents this NOT operator. Let’s test it out:
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb;
unsigned int nb_mod;
char *nb_str;
nb = 2423;
nb_str = ft_unsigned_itoa_base(nb, 2);
printf("Binary number:\t\t%s (Decimal: %010u)\n", nb_str, nb);
free(nb_str);
nb_mod = ~nb;
nb_str = ft_unsigned_itoa_base(nb_mod, 2);
printf("Bitwise NOT:\t\t%s (Decimal: %010u)\n", nb_str, nb_mod);
free(nb_str);
return (0);
}
As we can see, all the bits are inverted as a result of the NOT operation. This is what is known as a one’s complement.
Bitwise AND Operator (&)
The logical AND operator compares two bits and returns true (1) only if both bits have a value of 1. If one or the other or both have the value 0, the result of the operation will be false (0). We can sum this up in a small truth table:
| AND | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
To represent this AND operator in a bitwise operation, we use a special character, the ampersand: &. Let’s modify our code a little bit with two numbers:
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb1;
unsigned int nb2;
unsigned int res;
char *nb_str;
nb1 = 2423;
nb2 = 10002;
nb_str = ft_unsigned_itoa_base(nb1, 2);
printf("Binary number 1:\t%s (Decimal: %010u)\n", nb_str, nb1);
free(nb_str);
nb_str = ft_unsigned_itoa_base(nb2, 2);
printf("Binary number 2:\t%s (Decimal: %010u)\n", nb_str, nb2);
free(nb_str);
res = nb1 & nb2;
nb_str = ft_unsigned_itoa_base(res, 2);
printf("Bitwise AND:\t\t%s (Decimal: %010u)\n", nb_str, res);
free(nb_str);
return (0);
}
And indeed, we can see here that only the bits set to 1 at the same position in both numbers were copied to the result of the bitwise & operation, the rest is set to 0.
To do the exact opposite of the AND operation, NAND, all we need to do is invert all the bits in our result with ~(nb1 & nb2) !
Bitwise OR operator (|)
Unlike the AND operator, the OR operator returns true (1) if one of the two bits is set to 1. It is only when both are set to 0 that it also returns 0 (false):
| OR | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
The character we use to represent this bitwise OR operator is the vertical bar: |. Let’s modify our program again to demonstrate:
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb1;
unsigned int nb2;
unsigned int res;
char *nb_str;
nb1 = 2423;
nb2 = 10002;
nb_str = ft_unsigned_itoa_base(nb1, 2);
printf("Binary number 1:\t%s (Decimal: %010u)\n", nb_str, nb1);
free(nb_str);
nb_str = ft_unsigned_itoa_base(nb2, 2);
printf("Binary number 2:\t%s (Decimal: %010u)\n", nb_str, nb2);
free(nb_str);
res = nb1 | nb2;
nb_str = ft_unsigned_itoa_base(res, 2);
printf("Bitwise OR:\t\t%s (Decimal: %010u)\n", nb_str, res);
free(nb_str);
return (0);
}
With precisely the same values as the previous bitwise AND operator example, we find ourselves with a totally different result. Here, as long as there is a 1 at a position in either binary number, it is copied to the result.
Just like the previous operation, we can do the opposite operation to this one, NOR, with a one’s complement of the result: ~(nb1 | nb2).
Bitwise XOR Operator (^)
The logical XOR operator (also known as “exclusive OR”) has one major difference from its counterpart OR. It returns true (1), only if one of the two bits is set to 1. Otherwise, if both are at 1 or both are at 0, it returns false (0).
| XOR | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
We can represent this bitwise operator with a caret: ^. Let’s take a look at the differences with the previous example:
#include <stdlib.h>
#include <stdio.h>
char *ft_unsigned_itoa_base(unsigned n, unsigned base);
int main(void)
{
unsigned int nb1;
unsigned int nb2;
unsigned int res;
char *nb_str;
nb1 = 2423;
nb2 = 10002;
nb_str = ft_unsigned_itoa_base(nb1, 2);
printf("Binary number 1:\t%s (Decimal: %010u)\n", nb_str, nb1);
free(nb_str);
nb_str = ft_unsigned_itoa_base(nb2, 2);
printf("Binary number 2:\t%s (Decimal: %010u)\n", nb_str, nb2);
free(nb_str);
res = nb1 ^ nb2;
nb_str = ft_unsigned_itoa_base(res, 2);
printf("Bitwise XOR:\t\t%s (Decimal: %010u)\n", nb_str, res);
free(nb_str);
return (0);
}
Once more, without changing the values of our binary numbers, we get a very different result because only the bits with a value of 1 in one number but not the other are added to the result.
And of course, the opposite operation, XNOR can be done with ~(nb1 ^ nb2).
Why Use Bit Shifting and Bitwise Operations?
The usefulness of bit shifting and bitwise operations may seem pretty limited at first glance. The vast majority of programming languages take care of these behind the scenes, during compilation, for example. But beyond the intellectual satisfaction that these operators provide by allowing us to come closer to the internal operations of a computer, they are also very efficient.
These bit manipulation operations are undeniably primitive, trivial actions to a CPU. They only take one cycle to perform. For many processors, that is much faster than a multiplication or a division. Even with the technological advances that allow modern processors to do arithmetic and logical operations almost as fast as bitwise and bit shifting operations, the latter still consume less energy and fewer resources.
Bit manipulation is particularly useful for programming in low resource environments, where we must optimize the speed and memory use of our code as much as possible.
Practical Examples of Bit Shifting and Bitwise Operations
There are multitudes of interesting applications for bit shifting and bitwise operations, whether it be to optimize a mathematical operation or to store the terrain map of a 2D video game. The four following examples are only a few common practices.
Checking if a Number is Odd or Even
It goes without saying that if a binary number is even, the least significant bit will be 0, if it is odd, it will be 1. Therefore, we can check any number with the & operation, like this:
#include <stdio.h>
int main(void)
{
int x;
x = 108; // 0110 1100
if (x & 1) // 0110 1100 & 0000 0001 = 0000 0000 = false
printf("%d is an odd number.\n", x);
if (!(x & 1))
printf("%d is an even number.\n", x);
return (0);
}
Since the bitwise & operator compares two bits and gets 1 if both are set to 1 but 0 otherwise, we can explain the logic like this:
108 = 1101100
1 = 0000001
& = 0000000 -> false (0), the number is even.
107 = 1101011
1 = 0000001
& = 0000001 -> true (1), the number is odd.
Checking if a Number is a Power of Two
The method to determine if a number is a power of two requires us to divide that number by two repeatedly until we can’t anymore. If there is a remainder, it isn’t a power of two, but if we get to 1 without any remainder, we know it is a power of two. There is a much simpler and more efficient way to check this with bitwise operations:
#include <stdio.h>
int main(void)
{
int x;
x = 1024;
if (x != 0 && (x & (x - 1)) == 0)
printf("%d is a power of 2.\n", x);
else
printf("%d is not a power of 2.\n", x);
x = 512;
if (x != 0 && (x & (x - 1)) == 0)
printf("%d is a power of 2.\n", x);
else
printf("%d is not a power of 2.\n", x);
x = 800;
if (x != 0 && (x & (x - 1)) == 0)
printf("%d is a power of 2.\n", x);
else
printf("%d is not a power of 2.\n", x);
return (0);
}
This expression works because we know that a number that is a power of two will have a special notation in binary. Each power of 2 is a number that contains only one bit with set to 1, all other bits will be 0:
x = 0100 0000 (64)
x - 1 = 0011 1111 (63)
& = 0000 0000
The condition (x & (x -1)) == 0 returns true (1).
Number 64 is a power of 2.
However, a binary number that isn’t a power of 2 will have bits set to 1 in several different places:
x = 0010 1010 (42)
x - 1 = 0010 1001 (41)
& = 0010 1000
The condition (x & (x -1)) == 0 returns false (0) !
Number 42 is not a power of 2.
Swapping Two Values Without a Temporary Variable
A temporary variable, even a very short-lived one, takes up memory space. We can swap the values of two variables without any temporary variables thanks to the bitwise ^ operator. Keeping in mind that the XOR operator only sets a 1 where one or the other number has a 1, let’s study the following example:
#include <stdio.h>
int main(void)
{
int a;
int b;
a = 3; // 0011
b = 2; // 0010
printf("Before swap: a = %d, b = %d\n", a, b);
// a = 0011, b = 0010
a ^= b; // a = 0011 ^ 0010: a = 0001
b ^= a; // b = 0010 ^ 0001: b = 0011
a ^= b; // a = 0001 ^ 0011: a = 0010
// a = 0010, b = 0011
printf("After swap: a = %d, b = %d\n", a, b);
return (0);
}
Storing Multiple Boolean Flags
A boolean is a simple type of variable that can represent two possible states: true or false. A boolean is always stored in memory on 1 byte, which is at least 8 bits. But all we need is 1 bit to represent these two statues: 1 for true, 0 for false…
If we are dealing with multiple flags, it is much more cost-efficient in terms of memory space to store them all in the same variable. For example, three flags declared in their own boolean variable would each take up 1 byte, so that’s 3 bytes total. Thanks to bitwise operations, we could instead store these three flags in a char, which would be 1 byte for all three. This principle is, by the way, how Unix error codes are handled.
#include <stdbool.h>
#include <stdio.h>
#define FLAG_1 0b00000001
#define FLAG_2 0b00000010
#define FLAG_3 0b00000100
int main(void)
{
// If we use booleans like :
// bool flag_1 = true;
// bool flag_2 = false;
// bool flag_3 = false;
// We use 3 bytes of memory, 1 byte for each flag.
// In contrast, a char takes up only 1 byte of memory
// and can store up to 8 flags !
char flags;
flags = 0; // 0000 0000
// Set a flag as "true" (1):
flags |= FLAG_2; // 0000 0000 | 0000 0010 = 0000 0010
flags |= FLAG_1; // 0000 0010 | 0000 0001 = 0000 0011
// Check the state of a flag:
if (flags & FLAG_1) // 0000 0011 & 0000 0001 = 0000 0001 = true
printf("Flag 1 is true.\n");
else
printf("Flag 1 is false.\n");
if (flags & FLAG_2) // 0000 0011 & 0000 0010 = 0000 0010 = true
printf("Flag 2 is true.\n");
else
printf("Flag 2 is false.\n");
if (flags & FLAG_3) // 0000 0011 & 0000 0100 = 0000 0000 = false
printf("Flag 3 is true.\n");
else
printf("Flag 3 is false\n");
// Set a flag as "false" (0):
flags ^= FLAG_2; // 0000 0011 ^ 0000 0010 = 0000 00001
if (flags & FLAG_2) // 0000 0001 & 0000 0010 = 0000 0000 = false
printf("Oops, flag 2 is still true.\n");
else
printf("Flag 2 is now false.\n");
return (0);
}
The useful thing is that if we ever need to store more than 8 flags, we can simply go to a larger capacity variable type. A short int would allow us to store up to 16 flags, and an int, up to 32!
Bit Twiddling
Low-level bit manipulation is called “bit twiddling” or “bit bashing”, particularly when the solutions are ingenious or non-obvious. Sometimes, these terms can be used in a pejorative manner, for superfluous manipulations that make the source code hard to read for very negligible performance optimizations.
We should take care to use these manipulations appropriately, when the need for optimization arises. Sean Anderson’s collection of Bit Twiddling Hacks [stanford.edu] is rich with examples of useful bit manipulations.
Sources and Further Reading
- Charles Petzold, 1999, Code: The Hidden Language of Computer Hardware and Software
- Wikipedia, Logic gate [wikipedia.org]
- Wikipedia, Bit manipulation [wikipedia.org]
- LLWardIII, Bitwise Operations and Why You Might Care [divnull.com]
- Sreedev Kodichath, Real World Uses of Bitwise Operators [medium.com]
- Sean Anderson, Bit Twiddling Hacks [stanford.edu]