Tutorial Walkthrough

In this tutorial, we will discuss bitwise operations in depth, and some cool things that you can achieve with them. We will first learn about different number systems as this is one of the fundamental requirements prior to performing bitwise operations. We will then discuss the different bit operations and bitwise operators. We will go over many examples in code, specifically in C/C++, though the core part (the bitwise operations) are almost identical in any programming language. Finally, we will put own knowledge to use and build different applications that use bitwise operations for optimization, encoding, and others.

Before we begin, I will note that if you understand very well the binary, octal, and hexadecimal, and how to convert between them, you may skip the next section entirely. Now, you may begin.

A Little Background On Bits and Bytes

A bit is a binary number (0 and 1) and it is the unit that computers utilize to perform computations and operations. A byte is a string of 8 bits, and thus "0" or "1" is a bit, but "0000 1010" and "1001 0100" are bytes; note that the space between each string of 4 bits is for visual purposes.

Different Number Systems

We normally deal with the decimal system. The decimal system, as its name implies, has 10 different numbers; from 0-9. The binary number system is composed of two numbers, 0 and 1. In computer science and programming, we usually deal with four different number systems: Binary, Octal, Decimal, and Hexadecimal. The octal has 8 different numbers (0-7), and the hexadecimal 16 (0-F, including A, B, C, D, E, and F after 9).

We can convert between these number systems because each number has an intrinsic value, and the number system is just a different way of representing it. Converting between binary, hexadecimal, and octal is relatively easy, however, from decimal to any of the other requires an extra effort. We will focus our efforts mostly in binary and hexadecimal for purposes of this tutorial, and because those will be used the most often anyway.

Converting Between Hexadecimal And Binary

First, we must establish that we require 4 binary digits–4 bits–to form 1 hexadecimal digit. The idea is that you require at least 4 switches (on or off) to represent 16 possibilities (0-F). One bit will allow 2 possibilities (0 or 1), 2 bits 4 possibilities (00, 01, 10, 11, or from 0-3), 3 bits 8 possibilities (0-7), and 4 bits 16 possibilities (0-15 decimal, or 0-F hexadecimal). That means that any hexadecimal digit can be represented with 4 bits. From now on we will append an "x" to a number to represent that it is in hexadecimal, such as 5x, and a "b" to represent it is binary, such as 0101b.

The easiest way to convert numbers between hexadecimal and decimal is to memory the 16 representations of binary in hexadecimal. Here is the table:

If you learn this table, you could convert any number between binary and hexadecimal. For instance, if you want to convert 10101011010111b to hexadecimal, you group each string of bits by 4, starting from the right-most group, and prepend 0s if the last group is less than 4 bits, so my binary number is: "0010 1010 1101 0111b". Note how I have prepended two zeros to make the left-most group have 4 bits. After, it is just simply converting each group of 4 bits to their corresponding hexadecimal digit from the table, and the resulting number is 2AD7x. Converting from hexadecimal to binary is just reverting the process, so 43ABx = 0100 0011 1010 1011b. With practice, this will become second nature and converting between these two bases will be as quick as adding two numbers.

Bitwise Operators

There are 5 bitwise operators that we will discuss in this tutorial; AND, OR, NOT, XOR, and Left-Right bit Shifting. The NOT is unary–only require one operand–whereas the rest are binary, and thus require two operands. Let's define each of these operations.

AND, OR, And NOT Operators

The AND operator occurs between two bits. It is equivalent to the logical AND operator when applied to two bits. If we consider 1 as true and 0 as false, then we can conclude that x AND y is true if both x and y are true, otherwise, it is false. The AND operator can be represented with the ampersand (&) in programming languages. From now on, we will denote x AND y as x & y. A simple table with the AND operator is as follows:

Note that it is only 1 (true) if both x and y are 1. What if you have more than one bit in each operand? If x = 0111b and y = 1001b, then, and the title suggest, the operation is performed in a bit-wise manner, that is, each bit in the first operand with each bit in the same position of the second operand, so x & y = (0 & 1) (1 & 0) (1 & 0) (1 & 1) = 0001b. Later in the tutorial, we will use the AND operator for some useful tasks.

The OR operator, on the other hand, is 1 if at least one bit is 1. That means that it is only 0 if both bits are zero. This operator is also equivalent to the logical OR if both operands are a single bit. The OR operator is represented with the pipe character (|), and from now on, we will use x | y to refer to x OR y. Here is the table of the OR operator:

If our operands have more than one bit, then the operator is applied bit-wise. if x = 0111b and y = 1001b, what is x | y? (0 | 1) (1 | 0) ( 1 | 0) (1 | 1) = 1111b.

The NOT operator is perhaps the simplest one. It simply inverts a bit, so NOT 0 is 1 and NOT 1 is 0. It is equivalent in nature to the logical NOT operator if the operand (remember is a unary operator) is a single bit. The NOT operator is represented with a tilde (~), so NOT x = ~x. Below is a table with the NOT operator:

Again, if the operand has more than one bit, then the operator is applied to each bit; ~0011b = 1100b.

You may want to practice with the following:

0110 1011 0110 1010b & 1100 1011 0000 1011b = 0100 1011 000 1010b

1111 0011 1011 1011b | 0010 0110 0101 1011b = 1111 0111 1111 1011b

~0110 1011 0000 1111b = 1001 0100 1111 0000b

Tip: To perform the bit-wise operations in hexadecimals, convert them to binary first.

5D91x & 2911x = 0911x

1011x | FD60x = FD71x

~45FD = BA02x

XOR Operator

The XOR operator is a very useful one. We will explore some of its uses in the next section. The XOR operator is 1 if the operands (1 bit) are opposite. The XOR operator is represented with a carrot (^), so to represent x XOR y, we will use x ^ y. Here is the table:

If you pay close attention, you can think of the XOR operator as an optional NOT operator. The value of x is inverted whenever y = 1. This has very nice uses that we will explore soon. If the XOR operator is applied to two operands with more than one bit, then the operation is performed bit-wise. For instance, 0110b ^ 1011b = 1101b.

You can practice with the following exercises:

0110 1011 0110 1010b & 1100 1011 0000 1011b = 1010 0000 0110 0001b

5D91x ^ 2911x = 5480x

Bit Shifting

Bit shifting is an operator that allows just that–to shift the bits–either left or right. The first operand is the one that you wish to shift, while the second operand indicates by how many bits you wish to shift it. First, we must note that the positions of the bits are counted from 0 and from right to left, so a number 0001b has positions from 0 to 3, and 1 is at position 0. Since this operation is to shift the bits of the first operand, it is performed only when such operand has more than one bit. The left and right shift operators are represented with angle brackets, << and >>, respectively. Let's suppose x = 0110b, and I wish to shift it left by 2 bits, then the left-most 2 bits will disappear, and 2 "0"s will be appended. x << 2 = 1000b. Let's break down the operation without getting rid of the left-most two bits: 01 1000. The shifting operation subtracts (in the case of left shift) n to the position of each bit, where n is the second operand. So the 01 now have positions 5 and 4, respectively, 4 and 5 are not part of the result since the number is only of 4 bits. If the operation had been x >> 2, then the result would be 0001b as the right-most 2 bits would occupy positions outside of the four possible ones.

If our operand had more bit capacity, then it is a different story. Let's consider x = 0000 1010b. What is x << 3? 0101 0000b. The left-most 3 bits (that were all zero) disappeared, and 3 more zero were appended in the 3 right-most positions. What is x >> 3? 0000 0001b. The right-most 3 bits disappeared, and 3 more 0s were prepended in the 3 left-most positions.

Note that usually the second operand, n, is decimal because it makes the intent more clear, but you can very well say x << 0011b.

Here are some exercises to practice:

0100 1011b << 3 = 0101 1000b

1101 1001b >> 4 = 0000 1101b

FD01x >> 5 = 07E0x

Operations With Different Bases

Note that operations may occur with different bases (binary, decimal, and hexadecimal). We have already seen this in the bit shifting section where we shifted binary and hexadecimal numbers by an amount n in decimal. Internally, every number is composed of bits, therefore, you can already perform operations between different bases, and internally it will be between two binary numbers.

Bitwise Operators In Code

In this section, we will explore how these bitwise operators are using in code–programming languages. This guide will have the programming language of C/C++ as an example, but Java, Python, and the majority of other programming languages are exactly the same in this regard. As you will soon find out, the symbols that represent these operators are universal to any programming language.

It is no accident that we used the symbols &, |, ~, ^, <<, and >>. These are the symbols used in most, if not all, programming languages that support bitwise operations. Prior to using these operators in code, we must know how numbers and other types of data is stored in programming languages such as C/C++.

Type Sizes In C/C++

The smallest amount of data you can store in a modern computer is 8 bits–1 byte–that means, that the smallest size of any type of data in your programming language is 1 byte; yes, even a boolean variable that is binary and would, in theory, only require 1 bit to store. With that being said, here is a table with the size of different types in C/C++:

As you can see, the int basic data type may be either 2 or 4 bytes, depending on whether the CPU is 32bits or 64bits. Since we know the sizes of the different data types, we know must understand that if you store any data into a char type, it must always have 8 bits, so 1b is stored as 00000001b. It is important to understand the sizes of the data since it will be of the utmost importance when deciding on your operations.

Note: Qualifiers such as "unsigned" and "signed" do not affect the size of the type, rather they change the range of possible values because they either include or exclude negative numbers. For instance, the range of "unsigned char" is 0-255 decimal, whereas that of "signed char", or simply "char", is -128-127, inclusive. In most of the tutorial, we will use the qualifier "unsigned" so as to avoid explaining how negative numbers are stored with 2's complement. The important thing is that it all comes down to a string of bits, regardless of the qualifier or type.

Binary, Hexadecimal, and Octal in C/C++

It is really useful to be able to express numbers with bases different than 10. In C/C++, and most programming languages, you express binary numbers by leading with "0b" (zero-b), hexadecimal by leading with "0x" (zero-x), and octal by leading with "0" (zero). Here are some examples in C/C++:

int main()
{
    int x;                /* Assume this is 4 bytes (32 bits) */
    unsigned char y;      /* This is 1 byte (8 bits) */
    unsigned long int z;  /* This is 8 bytes (64 bits) */

    // Binary
    x = 0b1001;           /* Since x is 32 bits, 28 zeros are prepended */
    y = 0b11011;          /* y is 8 bits so 0b00011011 is the full number */
    z = 0b1000 * 0b101;   /* Both numbers are converted to have 64 bits */

    // Hexadecimal
    x = 0x3df0;           /* Note that this is equivalent to 0x3DF0 */
    y = 0xF;              /* 0x0F since there are 8 bits (2 hex digits) */
    z = 0xF4dd;           /* 0x0000000000F4dd */

    // Octal
    x = 0755;             /* Octal 755 is equivalent to 0b111 101 101 */
    y = 075;
    z = 05524;

    return 0b0;
}

In C, you can display numbers in hexadecimal format by using the format identifier "%x", or "%X". There is no native way to display numbers in binary format in C, however, we will demonstrate displaying hexadecimal numbers in C/C++, and binary and octal numbers in C++:

#include <iostream>
#include <bitset>

int main()
{
    int x = 0x5f;
    printf("%x \n", x);   // Displays 5f
    printf("%X \n", x);   // Displays 5F
    printf("%04x \n", x); // Displays 005f

    std::cout << std::hex << x << std::endl;  // Displays 5f
    std::cout << std::oct << x << std::endl;  // Displays 127
    std::cout << std::dec << x << std::endl;  // Displays 95

    /* If you with to use bitset, you must include it */
    std::cout << std::bitset<8>(x) << std::endl; // Displays 01011111

    return 0x0;
}

The Bitwise Operators in C/C++

The symbols we used before, &, |, ~, ^, <<, and >>, correspond to the operators AND, OR, NOT, XOR, Left Shift, and Right Shift, respectively, in most, if not all, programming languages that support such operators. For instance, in C/C++, you perform each of the bitwise operations in the following way:

#include <stdio.h>

int main()
{
    unsigned char x;
    printf("Please enter a number: ");
    scanf("%d", &x);

    printf("x & 0x5d = %x\n", x & 0x5d); // Displays the result of x & 0xd5 in hex
    printf("x | 0x5d = %x\n", x | 0x5d); // Displays the result of x | 0xd5 in hex
    printf("x ^ 0x5d = %x\n", x ^ 0x5d); // Displays the result of x ^ 0xd5 in hex
    printf("~x = %x\n", ~x); // Displays ~x in hex
    printf("x << 2 = %x\n", x << 2); // Shift left 2 times
    printf("x >> 3 = %x\n", x >> 3); // Shift right 3 times

    return 0b11101010 * 0x0;
}

It is imperative that the shift operators be understood, as it is used in many of the operations that we will see in the next section. The reason is that it is sometimes more readable to shift a bit left/right than to write the corresponding bit from the beginning. Additionally, sometimes the position of the bit that must be 1 is unknown. Here is an example of what is meant:

int main()
{
    unsigned char x; // Remember that unsigned char is 1 byte (8 bits).
    x = 1; // This is equivalent to 0b00000001 or 0x1
    x = x << 2; // This is equivalent to 0b00000100 or 0x4
    x = 0x80; // This is equivalent to 0b10000000

    // But what if the position of the bit is unknown?

    int position = 5; // I want the bit in position 5

    x = (1 << 5); // 1 = 0b00000001; 0b00000001 << 5 = 0b00100000; 0x20
    return 0755 - 0x1ED;
}

Now it the time for you to practice in the programming language of your choice as many interesting operations and "tricks" lie ahead. I recommend that you get comfortable with these operators and intuitively understand what is happening before proceeding.

Operations

In this section, we will explore some of the uses of the different operators, and in the next section, we will finally use a programming language to demonstrate them. Note that for purposes of this setting, we will assume that all of our operands contain 8 bits.

Setting, Clearing, And Toggling A Bit

Setting a bit means to set it to 1, regardless of its current state. Since we are dealing with 8-bit numbers, we must specify which bit we wish to set. First, let's assume that we want to set the right-most bit, that is, the bit at position 0. We know that the OR operator always returns 1 if at least one operand is 1, so we can take this to our advantage. If we say x = 0000 0000b, and we wish to set the bit at position zero, then we need only to say x = x | 0000 0001b and obtain 0000 0001b. Now let's say that y = 0110 0111b and we wish to set bit 4 (the one bolded), then we must say that y = y | 0001 0000b, which equals 0111 0111b. I hope it becomes a bit clear why the OR operator is the one to use here. If the bit we wish to set is already set (1), then we will have 1 | 1 = 1, if it is 0, then we will have 0 | 1 = 1. Any other bit in the first operand will remain unchanged because 0 | 0 = 0 and 1 | 0 = 0, so we only set 1 in the bit(s) we wish to set, and the rest should be 0.

Clearing a bit means to set it to 0, regardless of its current state. We must also think of which bit we wish to clear. The perfect operator for this is the AND operator. If x is any bit (just one bit), then x & 0 = 0, and x & 1 = x. Remember that the AND operator is 0 if at least one operator is 0, and thus if the second operand is 0, regardless of the value of the first operand, the result will be 0 as well. On the other hand, if the second operator is 1, then the result will depend only on the first operand because 1 & 1 = 1 and 0 & 1 = 1. So, if we have x = 0001 1001b and we wish to clear the bit in position 3, then we would say: x = x & 1111 0111b and the result is 0001 0001b.

Toggling a bit means to invert it. If the bit in question is 0 then we set it to 1, otherwise, we set it to 0. Now, it may not be as simple as you may think. Utilizing the NOT operator is not right because we are dealing with many bits–8 to be precise–and if we used the NOT operator we would toggle every bit, which is not what we want. Now, we know of the XOR operator that can be thought of as an optional NOT operator. Remember that it inverts the bit if the second operand is 1. So if x = 0100 1011b and we wish to toggle the bit at position 3, then we would do x = x ^ 0000 1000b, and the result would be 0100 0011b.

Also, note that you can set, clear, and toggle multiple bits at a time. For instance, if I wanted to set bits 0 and 7, you perform x = x | 1000 0001b.

Have you noticed how our second operand tend to be either all 0s but one, or all 1s but one? Would it not be easier to express that operand in hexadecimal? For instance, if you wished to set bit number 2 in x = 0101 1001b, then instead of doing x = x | 0000 0100b, you could compact it as x = x | 04x. If you wished to clear bit number 5 in x = 1010 0111b, then you would do x = x & DFx.

Now, let's program functions to set, clear, and toggle a bit in an arbitrary position p:

/* This code is made to run in C or C++
 */

typedef unsigned char byte_t; // unsigned char is 1 byte which is 8 bits.

/* Set the bit in position p */
void set_bit(byte_t *data, byte_t p)
{
    /* We must shift 0b00000001 by p to the left */
    *data = *data | (1 << p);
}

void clear_bit(byte_t *data, byte_t p)
{
    /* We must invert 1 to become 0b11111110, but
     * prior to that we must shift the 1 so it is
     * where it's needed.
     */
    *data = *data & ~(1 << p);
}

void toggle_bit(byte_t *data, byte_t p)
{
    *data = *data ^ (1 << p);
}

int main()
{
    byte_t data = 0x4d;
    printf("%02X -> ", data);
    set_bit(&data, 4);          /* It should be 0x5D now. */
    printf("%02X;\n", data);
    printf("%02X -> ", data);
    clear_bit(&data, 0);        /* It should be 0x5C now. */
    printf("%02X;\n", data);
    printf("%02X -> ", data);
    toggle_bit(&data, 7);       /* It should be 0xDC now. */
    printf("%02X;\n", data);

    return 0b01 - 0x1;
}

Here are some exercises for your to try:

Using only binary:

Clear bit in position 4 in x = 0110 1011b: x = x & 1110 1111b

Set bit in position 5 in x = 0100 1011b: x = x | 0010 0000b

Toggle bit in position 1 in x = 0101 1011b: x = x ^ 0000 0010b

Using only hexadecimal:

Clear bit in position 2 in x = 0110 1011b: x = x & FBx

Set bit in position 3 in x = 0100 1011b: x = x | 08x

Toggle bit in position 2 in x = 0101 1011b: x = x ^ 04x

Using Bitmasks To Extract Bits

A bitmask is a piece of data (bits) that allow you to extract–mask out–certain information. Let's take an unknown, 8-bit number x, and I wish to know the value of the bit at position 2. A bit mask to extract such information would consist of an 8-bit number with all bits set to zero, except for the bit you wish to extract, so a mask m = 0000 0100b. If we used the AND operator, then we know that we can extract that bit, so the result r = x & m. This works because every bit in the mask that is 0 will always be 0, whereas the other bit for which the mask is 1, will result in the bit of x in that position. But how do we know if the bit in question is set or not? If x = 0110 1011b, and you wish to extract bit 5, then our mask m = 0010 0000b. If we use the AND operator, then we obtain that x & m = 0010 000b, and that is m. In general, if a mask turns out to be true, that is, all bits in question are set, then you will have x & m = m, otherwise, x & m ≠ m. It is often convenient to make our bitmasks have a hexadecimal base, so if we wished to extract bits 2 and 7 of a variable y, then our mask is 84x, and our question would be; is y & 84x = 84x?

Bitmasks are useful because it allows you to store information in a single variable and keep track. Here is a simple example in C where I store 5 different flags in a single variable:

/* These are the masks of each flag. */
#define REQUESTED_HELP    0x01  /* corresponds to 0b00000001 */
#define REQUESTED_MENU    0x02  /* corresponds to 0b00000010 */
#define ENTERED_USER      0x04  /* corresponds to 0b00000100 */
#define ENTERED_PASS      0x08  /* corresponds to 0b00001000 */
#define ENTERED_EMAIL     0x10  /* corresponds to 0b00010000 */

typedef unsigned char byte_t;
/* Note that we may store up to 8 flags in a single byte_t variable */

/* Macro function to extract whether a flag is enabled */
#define IS_FLAG_ON(data, mask)     ((data & mask) == mask)

int main()
{
    byte_t data;
    scanf("%x", &data);
    
    if (IS_FLAG_ON(data, REQUESTED_HELP))
    {
        /* Do something here... */
    } 
    else if (IS_FLAG_ON(data, REQUESTED_MENU))
    {
        /* Do something here... */
    }
    else if (IS_FLAG_ON(data, ENTERED_USER | ENTERED_EMAIL))
    {
        /* Do something here...*/
    }
    else
    {
        fprintf(stderr, "No action was requested.\n");
        exit(1);
    }

    return 0b10011111 * 0x04 - 0x9f * 0b100;
}

Did you notice how in the last else-if we used the OR operator to join the conditions, and that is to say if both flags are on? It may seem counter-intuitive to use the OR operator to join, but if you recall, to OR "ENTERED_EMAIL" and "ENTERED_USER" is to set the corresponding bits for both conditions, and the result produced is 0x14 or 0b00010100. The IS_FLAG_ON macro function only returns true if data & mask = mask, which means that both bits must be set. Bitmasks have many uses and we will use it later in the guide to store some data and extract it.

Circular Shifts

So far, we have discussed left shift and right shift, however, it is sometimes useful to perform a circular shift–or rotation–of bits. To understand a circular shift, imagine that the string of bits no longer has an end or a beginning, rather the bits are arranged in a circle, and you may rotate the circle. When you rotate it, you do not lose any bits, rather they change their current position. A left circular shift of 1 bit in x = 0b10010110 produces x = 0b00101101. The 1 that was at position 7 is now at position 0. To restore it to the previous state, you can perform a right circular shift of 1 bit. To perform a circular shift we require certain information that includes: The number of bits in the data, by how many bits we which to rotate, and the direction of the rotation. Here is the algorithm to rotate a number x by m amount to the left, and it has n number of bits:

1. Shift x to the left by m and call the partial result x1;
2. Shift x to the right by n – m and call the partial result x2; and,
3. Assign to x the result of x1 | x2.

To make it easier to understand, let's do one example where x = 0b1100 1101, m = 3, and n = 8:

1. x1 = x << 3; x1 = 0b0110 1000;
2. x2 = x >> (8 – 3); x2 = 0b0000 0110;
3. x = x1 | x2; x = 0b0110 1110;

I hope this example makes it easy for you to understand circular shifts. Now let's write an example in code:

/* By using the sizeof function we get the number of bytes
 * and by multiplying by 8, we get n, the number of bits.
 */
#define CIRC_SHIFT(x, m)     x = (x << m) | (x >> (sizeof(x) * 8 - m))

int main()
{
    unsigned char x = 0xf3;

    CIRC_SHIFT(x, 5); // Rotate by 5 bits
    printf("%02x\n", x); // x is now 0x7E

    return 0x80 & ~(1 << 7);
}

There are many other operations that can be performed, but these three will do nicely for some tasks that we can perform.

Beyond Operations

In this section, we will put what we've learned to the test by writing a few programs using the operations explained in the previous section.

Date, Time, and Date-Time

Usually, to store a date, time, or date time, you use several bytes of memory, and if you send it through the network, those bytes are sent as well. You may be thinking, well, 4 more bytes will not really add any noticeable overhead in a network, but what if you have millions of nodes? Those 4 bytes are not so insignificant after all. In this lesson, we will learn to pack data so that it is more compact but you still retain the same information. This is a loose way of performing lossless compression, but it is not the intent.

Date is defined as a tuple of day, month, and year. Time is defined as hours, minutes, and seconds of a particular day and date-time includes both. The most common way of storing a date is either in a string with a format such as "mm-dd-yyyy", or three separate integers. Let's write some code and make some analysis of the amount of data used:

struct date_ver_1
{
    int day; // 4 bytes
    int month; // 4 bytes
    int year; // 4 bytes
}; // 12 bytes total

/* Hmm... The maximum day # is only 31, therefore we do not need 4 bytes
 * The maximum month # is 12, so we certainly do not require 4 bytes
 * The maximum year # we can assume the max is 5000, so we do not require 4 bytes
 */

struct date_ver_2
{
    unsigned char day; // 1 byte
    unsigned char month; // 1 byte
    unsigned short year; // 2 bytes
}; // YES! We only used 4 bytes

char *date; // Each character is 1 byte so mm-dd-yyyy = 10 bytes

/* Can we do better? Certainly
 * Let's see, to store days from 1-31 we only need 5 bits (2^5 = 32)
 * To store the month we only need 1-12, so 4 bits (2^4 = 16)
 * To store year from 0-4999, and that is 13 bits (2^13 = 8192)
 * The total is 22 bytes ~ 2 bytes + 5 bits. So we need at least 3 bytes.
 */

typedef unsigned int packed_date_t; // Can store a date.
/* It is still 4 bytes, but we have an additional 10 bits
 * to store other information about the date, flags, and other things
 */

void pack_date(packed_date_t *date, int mm, int dd, int yyyy);
int unpack_month(packed_date_t date);
int unpack_day(packed_date_t date);
int unpack_year(packed_date_t date);

#define MONTH_MASK    0xf0000000    // 0b1111 0000 0000 0000 0000 0000 0000 0000
#define DAY_MASK      0x0f800000    // 0b0000 1111 1000 0000 0000 0000 0000 0000
#define YEAR_MASK     0x007ffc00    // 0b0000 0000 0111 1111 1111 1100 0000 0000

int main()
{
    packed_date_t date;
    pack_date(&date, 9, 20, 1994);

    /* Just a random number to the casual observed */
    printf("The packed date is: %d\n", date);

    /* However, we know more than that: */
    printf("Date: %02d/%02d/%04d\n", unpack_month(date), 
            unpack_day(date), unpack_year(date));
    return 0;
}

void pack_date(packed_date_t *date, int mm, int dd, int yyyy)
{
    // We will store the month in the first 5 bits of the 32 bits
    *date = (mm << (32 - 4));

    // In the next 4 bits
    *date = *date | (dd << (32 - 4 - 5));

    // In the next 13 bits
    *date = *date | (yyyy << (32 - 4 - 5 - 13));
}

int unpack_month(packed_date_t date)
{
    return (date & MONTH_MASK) >> (32 - 4);
}

int unpack_day(packed_date_t date)
{
    return (date & DAY_MASK) >> (32 - 4 - 5);
}

int unpack_year(packed_date_t date)
{
    return (date & YEAR_MASK) >> (32 - 4 - 5 - 13);
}

Quite a ride, that one. I hope that upon analysis of the above code, you can understand what is going on and replicate it with other things. Next, we will store a time. A time has an hour (0-23), minutes (0-59), and seconds (0-59). Let's see how we can pack that one up:

struct time_ver_1
{
    unsigned char hour; // 1 byte
    unsigned char mins; // 1 byte
    unsigned char secs; // 1 byte
}; // 4 bytes (memory is stored in blocks of 4 bytes)

/*
 * To store hour (0-23) only 5 bits are needed
 * To store mins (0-59) only 6 bits are needed
 * To store secs (0-59) only 6 bits are needed
 * Only 5 + 6 + 6 = 17 bits (2 bytes + 1 bit) are needed
 * Unfortunately, we will still need 4 bytes
 * but we have an extra 15 bits for other information
 */

typedef unsigned int packed_time_t;

#define HOUR_MASK 0xf8000000  // 0b1111 1000 0000 0000 0000 0000 0000 0000
#define MINS_MASK 0x07e00000  // 0b0000 0111 1110 0000 0000 0000 0000 0000
#define SECS_MASK 0x001f8000  // 0b0000 0000 0001 1111 1000 0000 0000 0000

void pack_time(packed_time_t *time, int hh, int mm, int ss);
int unpack_hour(packed_time_t time);
int unpack_mins(packed_time_t time);
int unpack_secs(packed_time_t time);

int main()
{
    packed_time_t time;
    pack_time(&time, 17, 45, 32);

    /* Just a random number to the casual observed */
    printf("The packed time is: %d\n", time);

    /* However, we know more than that: */
    printf("Time: %02d:%02d:%02d\n", unpack_hour(time), 
            unpack_mins(time), unpack_secs(time));
    return 0;
}

void pack_time(packed_time_t *time, int hh, int mm, int ss)
{
    *time = hh << (32 - 5);

    *time = *time | (mm << (32 - 5 - 6));

    *time = *time | (ss << (32 - 5 - 6 - 6));
}

int unpack_hour(packed_time_t time)
{
    return (time & HOUR_MASK) >> (32 - 5);
}

int unpack_mins(packed_time_t time)
{
    return (time & MINS_MASK) >> (32 - 5 - 6);
}

int unpack_secs(packed_time_t time)
{
    return (time & SECS_MASK) >> (32 - 5 - 6 - 6);
}

Now, if you are a bit disappointed because in the end we still had 4 bytes, consider the following: Almost two times can fit in a 4-byte variable, which means that in 4 bytes you could store 3 by correctly positioning the bits. Also, if you do not which to pack more than one time, we have 15 extra bits to add new information such as the time zone, whether it is in 24-hour format or 12-hour format.

Finally, here is some practice for you: Build a C program to pack a date-time. Date-time has month (1-12), day (1-31), year (1-5000), hour (0-23), minutes (0-59), seconds (0-59), time format (24-hr or 12-hr), timezone (up to 32 different timezones).

Compare your solution to the following:

struct date_time_t
{
    unsigned char  month;           // 1 byte
    unsigned char  day;             // 1 byte
    unsigned char  hour;            // 1 byte
    unsigned char  minutes;         // 1 byte
    unsigned char  seconds;         // 1 byte
    bool           is_24hr_format;  // 1 byte
    unsigned short year;            // 2 bytes
    char           timezone[4];     // 4 bytes
}; // Total is 12 bytes

char *date_time; // format: "mm/dd/yyyy hh/MM/ss TMZ f" This has a total of 25 bytes

How many bytes will the optimal solution occupy? month: 4 bits, day: 5 bits, year: 13 bits, hour: 5 bits, minutes: 6 bits, seconds: 6 bits, time format: 1 bit, timezone: 5 bits; total = 47 bits. 5 bytes + 4 bits, the nearest type is 8 bytes (unsigned long int). The optimal solution is 8 bytes and you have an extra 17 bits for whichever other information you want to include.

How does this help? Well, let's assume that you have a server with 1000 daily users, and each user makes at least 5 requests per day. In each of these requests, you are sending and receiving a date-time. What is the impact? Let's build a table with a few scenarios:

Well, perhaps saving 60 terabytes per year is not that important for a company as big as Google, but date-time is just one piece of data that consumes very little of the total amount of bytes sent; what if all the headers were packed? This will certainly save a few petabytes per year for Google, and perhaps a few gigabytes for us mortals.

String Encoding

In this section, we will use circular shifting to encode a string. I do not want to call this encryption because it is easy to break, but it is an easy way to hide information in plain sight. Hopefully, this will give you an idea of what is possible with bitwise operators.

First, have you noticed how the "char" type is 1 byte in C/C++? That's because the ASCII and UTF-8 character sets have 256 characters (0-255), so 8 bits is perfect because 2^8 = 256. In C/C++, the "char" type is an integer of 8 bits, however, in other languages such as Python and Java, characters are not integers, but they can be cast.

For our encoding, we want to perform a circular shift on each character. The number of bits by which we will shift will depend on the character before. However, the character shift will always be between 1-7. This will ensure that no information is lost and that we can decode the string later on. We will use a variable amount to shift, so we need a way to know by how much we shift each character in order to restore it later. If we make the number of bits in the shift as a function of the previous character, then we can always restore it. However, we must use a fixed bit shift for the first character as there is no previous character. The number of bits which we will shift is to be computed as (Remainder of ASCII value of char at i - 1 / 7) + 1. This will ensure a number always between 1 and 7. So the algorithm to encode a string is as follows:

1. Perform circular shift of first character by 5 bits
2. Iterate characters 2 to length of string
3. m = ASCII value of previous character (unencoded) % 7 + 1
4. character i: circular shift by m

This algorithm ensures that the encoded string is safe. That means that the null character is not encoded because 0 encoded by any amount is 0 (null character). Also, no other character will ever produce the null character. The downside is that character 255 (FFx) is also never encoded.

Let's code that encoding function in C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CIRC_LSHIFT(x, n)  (x << n) | (x >> (8 - n))
#define M_SHIFT(x)         (x % 7) + 1
#define FIRST_SHIFT        5

char *encode_str(char *str);

int main()
{
    char str[] = "Hello, there!";

    printf("%s\n", encode_str(str));

    return 0;
}

char *encode_str(char *str)
{
    char *encoded_str = NULL;
    int i;

    if (strlen(str) > 0)
    {

        encoded_str = (char *)malloc(strlen(str) + 1);
        encoded_str[0] = CIRC_LSHIFT(str[0], FIRST_SHIFT);

        for (i = 1; i < strlen(str); i++)
        {
            int m = M_SHIFT((unsigned char)str[i - 1]);
            encoded_str[i] = CIRC_LSHIFT((unsigned char)str[i], m);
        }
        encoded_str[i] = '\0';
    }
     
    return encoded_str;
}

If you run the above code, chances are you will see a string that you cannot understand, so the only way to see if it worked, is to write a decode function, so let's complete the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CIRC_LSHIFT(x, n)  (x << n) | (x >> (8 - n))
#define CIRC_RSHIFT(x, n)  (x >> n) | (x << (8 - n))
#define M_SHIFT(x)         (x % 7) + 1
#define FIRST_SHIFT        5

char *encode_str(char *str);
char *decode_str(char *str);

int main()
{
    char str[] = "Hello, there!";
    char *encoded = encode_str(str);

    printf("Encoded: %s\n", encoded);
    printf("Decoded: %s\n", decode_str(encoded));

    return 0;
}

char *encode_str(char *str)
{
    char *encoded_str = NULL;
    int i;

    if (strlen(str) > 0)
    {

        encoded_str = (char *)malloc(strlen(str) + 1);
        encoded_str[0] = CIRC_LSHIFT(str[0], FIRST_SHIFT);

        for (i = 1; i < strlen(str); i++)
        {
            int m = M_SHIFT((unsigned char)str[i - 1]);
            encoded_str[i] = CIRC_LSHIFT((unsigned char)str[i], m);
        }
        encoded_str[i] = 0;
    }
     
    return encoded_str;
}

char *decode_str(char *str)
{
    char *decoded_str = NULL;
    int i;

    if (strlen(str) > 0)
    {
        decoded_str = (char *)malloc(strlen(str) + 1);
        decoded_str[0] = CIRC_RSHIFT((unsigned char)str[0], FIRST_SHIFT);

        for(i = 1; i < strlen(str); i++)
        {
            int m = M_SHIFT((unsigned char)decoded_str[i - 1]);
            decoded_str[i] = CIRC_RSHIFT((unsigned char)str[i], m);
        }

        decoded_str[i] = 0;
    }

    return decoded_str;
}

As you can see in the code, when shifting a character (or getting its m value), we cast it as "unsigned char". If it were to be "signed char" or simply "char", it would have a range from -128 to 127. Negative numbers get stored a little different than positive numbers, so that would affect the shifting operations. If you'd like to learn how the negative numbers are stored, google "2's complement in binary" and you should obtain a few results.

This has been a long but worthwhile journey! I hope you can agree with me. Hopefully, you are on your way to using these bitwise operations in your next projects!

If you enjoyed this tutorial, please do not forget to comment and share it! You may also contact me at any point for any reason by using the contact page.