Bitmasking. Managing data in a compact way.

Suppose you are given a situation where you have to produce some output which depends on various arguments(flags) that the user provides.

For ex, lets say you are given a number and you are asked to do some tests on it:

1. Is the number postive?
2. Is the magnitude(number) odd?
3. Is the magnitude(number) prime?

You are also asked to save all the test results in memory so that you can pass it to other functions if required.

A simple implementation would be:

#include <stdio.h>

// fill in the code
int checkPos(int x){ };
int checkOdd(int x){ };
int checkPrime(int x){ };

int main(void) {
	int isPos, isOdd, isPrime;
	int x;
	printf("Enter a number: ");
	scanf("%d", &x);

	isPos = checkPos(x);
	isOdd = checkOdd(x);
	isPrime = checkPrime(x);
	
}

So here, we have saved the answer to each result in 3 int variables. So basically, it takes up 12 bytes(96 bits) just to store 3 results. It has a large memory footprint and there is actually a better way to acheive the same result by utilising individual bits of an integer variable to represent the result.

We can make a 8 bit unsigned int (uint8_t) and utilise each individual bit of that integer to store a binary result(Notice that the answer to all the questions is binary Yes/No).

#include <stdio.h>

// fill in the code
int checkPos(int x){ };
int checkOdd(int x){ };
int checkPrime(int x){ };

int main(void) {
	uint8_t flags = 0;
	int x;
	printf("Enter a number: ");
	scanf("%d", &x);
}

Here, bitwise representation of flags is just : 00000000

We can use the 3 right most bits to store the result of the questions. For example, if x is postive and odd but not prime, then flag should be:

00000011

last bit: isPositive?

second last bit: isOdd?

third last bit: isPrime?

The methods that we will be using to change individual bits of flags is called Bitmasking.

Lets see some common Bitmask operations:

1. Turning ON bits

To turn on a bit in any particular location is basically changing that bit value to 1. We will use the bitwise OR for that.

In the above case, since x is postive, we need to turn of the last bit. Take the bitwise OR of flags and a number whose last bit is 1 and all other bits are 0.

flags = flags | (1<<0)

So here,

flags --> 00000000
(1<<0)--> 00000001
========================== OR
flags --> 00000001

Similarly, for turning on the second last bit:

flags = flags | (1<<1)

So here,

flags --> 00000000
(1<<1)--> 00000010
========================== OR
flags --> 00000010

We can also turn on multiple bits at the same time:

flags = flags | (1<<0) | (1<<1)

flags --> 00000000
(1<<0)--> 00000001
(1<<1)--> 00000010
========================== OR
flags --> 00000011

2. Turning OFF bits

We can turn off bits, by using the bitwise AND and ~(bitwise complement) operators.

Suppose, the current state of flags is 00000011 and we want to turn off the second last bit.

flags = flags & ~(1<<1)

flags -->  00000011
~(1<<1)--> 11111101
========================== AND
flags -->  00000001

3. Toggling bits

Toggling bits basically means to toggle(inverse) the state of a particular bit. If the bit is ON, turn it OFF and vice versa.

It can be acheived by using the XOR operator.

Suppose we want to toggle the second last bit of 00000011

flags = flags ^ (1<<1)

flags -->  00000011
(1<<1)-->  00000010
========================== XOR
flags -->  00000001

Now, lets toggle the third last bit:

flags = flags ^ (1<<2)

flags -->  00000001
(1<<2)-->  00000100
========================== XOR
flags -->  00000101

4. Querying the status of bits.

Now that we know how to mask individual bits, its also important to know how to actually query the state of bit in a particular location.

We use the AND operator for this. Lets say our flag is 00000111

We need to know the state of third last bit.

query = flags & (1<<2)

flags -->  00000111
(1<<2)-->  00000100
========================== AND
query -->  00000100

By comparing query with (1<<2), we can know the state:

if (query == (1<<2)){
// third last bit is ON.
}

Using all the above bitmasking functions, we can write a cleaner code with less memory footprint. Our original code would look like:

#include <stdio.h>
#include <stdint.h>

#define ISPOS (1<<0)
#define ISODD (1<<1)
#define ISPRIME (1<<2)

// fill in the code such 
// that each function returns 
// corresponding macro.
int checkPos(int x){
	if (x > 0)
		return ISPOS;
	else
		return 0;
};

int checkOdd(int x){ };
int checkPrime(int x){ };

int main(void) {
	uint8_t flags = 0;
	int x;
	printf("Enter a number: ");
	scanf("%d", &x);

	flags |= checkPos(x) | checkOdd(x) | checkPrime(x);

}