Explanation of an algorithm to set, clear and test a single bit

Question

Hey, in the Programming Pearls book, there is a source code for setting, clearing and testing a bit of the given index in an array of ints that is actually a set representation.

The code is the following:

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1+ N/BITSPERWORD];

void set(int i)
{
    a[i>>SHIFT] |= (1<<(i & MASK));
}

void clr(int i)
{
    a[i>>SHIFT] &= ~(1<<(i & MASK));
}

int test(int i)
{
    a[i>>SHIFT] & (1<<(i & MASK));
}

Could somebody explain me the reason of the SHIFT and the MASK defines? And what are their purposes in the code?

I've already read the previous related question.

Answer 1

From Here (General answer to get this thread started)

A bit mask is a value (which may be stored in a variable) that enables you to isolate a specific set of bits within an integer type.

Normally the masked will have the bits you are interested in set to 1 and all the other bits set to 0. The mask then allows you to isolate the value of the bits, clear all the bits or set all the bits or set a new value to the bits.

Masks (particularly multi-bit ones) often have an associated shift value which is the amount the bits need shifting left so that the least significant masked bit is shifted to the least significant bit in the type.

For example using a 16 bit short data type suppose you wanted to be able to mask bits 3, 4 and 5 (LSB is number 0). You mask and shift would look something like

#define MASK 0x0038
#define SHIFT 3

Masks are often assigned in hexadecimal because it is easier to work with bits in the data type in that base as opposed to decimal. Historically octal has also been used for bit masks.

If I have a variable, var, that contains data that the mask is relevant to then I can isolate the bits like this

var & MASK

I can isolate all the other bits like this

var & ~MASK

I can clear the bits like this

var &= ~MASK;

I can clear all the other bits like this

var &= MASK;

I can set all the bits like this

var |= MASK;

I can set all the other bits like this

var |= ~MASK;

I can extract the decimal value of the bits like this

(var & MASK) >> SHIFT

I can assign a new value to the bits like this

var &= ~MASK;
var |= (newValue << SHIFT) & MASK;

Answer 2

VonC posted a good answer about bitmasks in general. Here's some information that's more specific to the code you posted.

Given an integer representing a bit, we work out which member of the array holds that bit. That is: Bits 0 to 31 live in a[0], bits 32 to 63 live in a[1], etc. All that i>>SHIFT does is i / 32. This works out which member of a the bit lives in. With an optimising compiler, these are probably equivalent.

Obviously, now we've found out which member of a that bitflag lives in, we need to ensure that we set the correct bit in that integer. This is what 1 << i does. However, we need to ensure that we don't try to access the 33rd bit in a 32-bit integer, so the shift operation is constrained by using 1 << (i & 0x1F). The magic here is that 0x1F is 31, so we'll never left-shift the bit represented by i more than 31 places (otherwise it should have gone in the next member of a).

Answer 3

When You want to set a bit inside the array, You have to

1. seek to the right array index and
2. set the appropriate bit inside this array item.

There are BITSPERWORD (=32) bits in one array item, which means that the index i has to be split into two parts:

• rightmost 5 bits serve as an index in the array item and
• the rest of the bits (leftmost 28) serve as an index into the array.

You get:

• the leftmost 28 bits by discarding the rightmost five, which is exactly what i>>SHIFT does, and
• the rightmost five bits by masking out anything but the rightmost five bits, which is what i & MASK does.

I guess You understand the rest.

Answer 4

Bitwise operation and the leading paragraphs of Mask are a concise explanation, and contain some pointers for further study.

Think of an 8-bit byte as a set of elements from an 8-member universe. A member is IN the set when the corresponding bit is set. Setting a bit more then once doesn't modify set membership (a bit can have only 2 states). The bitwise operators in C provide access to bits by masking and shifting.

Answer 5

The code is trying to store N bits by an array, where each element of the array contains BITSPERWORD (32) bits.

Thus if you're trying to access bit i, you need to calculate the index of the array element stores it (i/32), which is what i>>SHIFT does.

And then you need to access that bit in the array element we just got.

(i & MASK) gives the bit position at the array element (word). (1<<(i & MASK)) makes the bit at that position to be set.

Now you can set/clear/test that bit in a[i>>SHIFT] by (1<<i & MASK)).

You may also think i is a 32 bits number, that bits 6~31 is the index of the array element stores it, bits 0~5 represents the bit position in the word.