Bitwise Ops and Its Applications

Bitwise Operations

Let's go over some basics. The most basic bitwise operations are |, &, ~, ^, and their respective assignment versions: |=, &=, ^=.

| is the OR operation. It will perform the OR of two (2) operands.
& is the AND operation. It will perform the AND of two (2) operands.
^ is the XOR operation. It will perform the XOR of two (2) operands.
~ is the "tilde" operation. It will flip the bits of a given integral type.

(Also, << and >> are left and right shifts)

Therefore, we can use integral types to perform these bitwise operations under.
I will assume everyone knows what the basic bitwise operations actually do.

Therefore, to go over why something like this would be useful. It is handy to keep track of lists without keeping bigger or larger datastructures, especially when the data is small. Meaning, that you just want to keep track of the indexes or numbers that are in or out of the list. With that said, using bitwise on integral types is ideal.

The basic knowledge is to look at the bits as indexes within an array for a given integral type. Then to include number i, you include bit i to the integral type. This is easy. To do that, you just bitwise-OR the integral type with the ith-bit being set. To do so, you would need to use the left shift (<<) operator. This is very useful. To unset or excludle a bit within a set you need a trick to take it from the list. There are many ways to do this; however, many of them need checks in order to not modify the actual integral type if that bit is NOT even in there. Therefore, an easy way to do this is the bitwise-AND the integral type with all bits set to 1 except the ith-bit. After this knowledge, now we know how to implement a bitset or set using an integral type without using a big datastructure. Since it is just overhead if you only are concerned with storing numbers. However, using integral types is limitd because currently the largest integral type is a uint64_t, which holds only 64 bits meaning the number range from 0 - 63. But the implementation follows:

uint64_t bitset = 0; // free all the bits within this integral type

// include the i-th bit
void include(int i)
{
   biset |= (1<<i);
}

// exclue the i-th bit
void exclude(int i)
{
   bitset &= ~(1<<i);
}

Bitwise operations are used heavily within orgranizing massive amounts of data - bitset tree structures. Also, with file systems and organizing data.