Bit Manipulation Tips & Tricks (part 2)

Hello and welcome to the second part of "Bit Manipulation Tips & Tricks." If you haven't read the first part yet, here is the link of you. Read it! :)

1. Turning a bit off without affecting other bits

Turning a bit off means to change 1 bits (on) to 0 bits (off) and if the bits are already off then they'll stay off. This can be accomplished by using the ~, << and & operators. Here is the genera formula:

turnBitOff (int bitString, int bitPosition)
{
  return bitString & ~(1 << bitPosition);
}

• bitString: is the set of bits we want to change. For instance, we want to turn off a bit in the bit string 1110.
• bitPosition: is the position of the bit in the bit string that we want to turn off. For instance, we want to turn off the 3rd bit (bold) in 1110. Then, the bit position is 3.
• 1 is just our help bit string. Its binary value is 0001.

We can now do an example to see how our formula. To turn off the 3rd bit of the bit string 1100, we do this: 1100 & ~(0001 << 3) = 1100 & ~(1000) = 1100 & 0111 = 0100. It works! :)

2. Turning a bit on without affecting other bits

If we can turn a bit off, then can we turn a bit on? Of course, we can. It's just the matter of replacing the & operator with the || operator and getting rid of the ~ operator. Here is the formula:

turnBitOn (int bitString, int bitPosition)
{
  return bitString || (1 << bitPosition);
}

To convince ourselves that this works, we should do two examples. To turn on the 2nd bit of bit string 1011 off, we do this: 1011 || (0001 << 2) = 1111 || (0100) = 1011 || 0100 = 1111. It works! How about trying to turn a bit on even if it's already on? So, to turn on the 3rd bit of bit string 1111 (which is already on), we follow the formula: 1111 || (0001 << 3) = 1111 || 1000 = 1111. As you can see, noting changed because the bit has already on.

3. Keeping track of boolean values of a data set using bits

Let's say we have an array of pictures and we want to keep track of them to see which one is in stock and which one is out of stock. How do we keep track of those pictures with least amount of memory? We can use a bit string.

If we have an array of 4 pictures to keep track of, we will have a bit string of 4 bits 0000. Whichever element is in stock will have its corresponding bit on. For instance, if picture no. 0 is in stock then the 0th bit is on, resulting in the bit string of 0001. If picture no. 3 is in stock then the 3rd bit is on, resulting in the bit string of 0100. If all pictures are in stock then all bits are on -> 1111.

We use the picture selling business as an example for convenience, but this technique can be applied to many different situations. For instance, we can use it to keep track of repeating letters in a word instead of using a hash table.

To make this whole scheme work, we need to employ the 1st and 2nd technique above. We also need a way to check to see if a bit is on or off to find out if a picture is in stock or no. Therefore, we will use a technique discussed in the first part of this tutorial. It is to check if a bit is on or off. If you don't remember, here is the formula for that technique:

int isAvailable (int bitString, int targetNum)
{
  return bit_string & (1 << targetNum);
}

Let's go back to our example. We have the bit string of 0001 that represents our stock. And, we want to know if picture no. 3 is in stock or not. By applying the formula, we can see that:

• 1 = 0001 is our helper string and targetNum = 3 because we need to know about picture no. 3
• bit_string & (1 << targetNum) = 0001 & (0001 << 3) = 0001 & 1000 = 0000 = 0 (in decimal)
• return 0 means not in stock while any number > 0 means in stock :)

If the picture is in stock again, we just have to turn the bit on to 1 by using the "turning on a bit" technique. Moreover, to indicate a picture is out of stock, we use the "turning off a bit" technique.

As you can see, if we use this method for keeping track of a large quantity of data, we can save a lot of memory space because bits are well bits they take the least amount of memory! Besides, computers are faster at executing bit operations.

Thanks for reading this part. And keep checking back, we'll have more fun with bits :)