C bit array macros, could anyone explain me how these work?

Question

I'm trying to implement sieve of erathostenes for school project and I've decided to do so using bit arrays. While I was searching for materials, I came across these 3 macros, they work flawlessly, but I can't really read(understand) them.

#define ISBITSET(x,i) ((x[i>>3] & (1<<(i&7)))!=0)
#define SETBIT(x,i) x[i>>3]|=(1<<(i&7));
#define CLEARBIT(x,i) x[i>>3]&=(1<<(i&7))^0xFF;

Could you please explain to me at least one of them in detail, I have very basic knowledge about bitwise operations in C (basically I know they "exist").

Will this work on another architecture using different endianness? Thanks in advance.

Answer 1

xis array of chars. i is an index of bits. since every char is 8 bits, the last 3 bits of i define the bit in the char, and the rest bits define the char in the array.

i>>3 shift i 3 bits to the right, so you get the part that tell you which char, so x[i>>3] is the char that contain the bit indexed byi.

i&7 is the last 3 bits of i (since 710==1112), so it's the index of the bit in the char. 1<<(i&7) is a char (truly it's int, but in this context you can ignore the difference), that has the bit indexed by i on, and the rest bits off. (the mask of the bit)

char&mask is the common way to check if bit is on.

char|=mask is the common way to turn bit in.

char&=~mask is the common way to turn bit off, and if mask is char, then ~mask==mask^0xFF.

I don't think that these macros are endiannes-depend. (if you got x by converting int[] to *char, it's a different story)

Answer 2

First off, those macros assume evilly that CHAR_BIT == 8, and i >> 3 is actually i / 8. (So really this code should say i / CHAR_BIT.) This first expression computes the byte which contains your desired bit, and is thus the array index in your array x (which should be an array of unsigned char!).

Now that we've selected the correct byte, namely x[i >> 3] (or x[i / CHAR_BIT] in your own, better code), we have to do the bit-fiddling. Again, i & 7 really wants to be i % CHAR_BIT, and it extracts only the remainder of your bit count that gives you the offset within the byte.

Example. Requesting the 44th bit with i = 43, and assuming CHAR_BIT = 8, i / CHAR_BIT is 5, so we're in the sixth byte, and i % CHAR_BIT is 3, so we're looking at the fourth bit of the sixth byte.

The actual bit-fiddling itself does the usual stuff; e.g. testing for a given bit performs bit-wise AND with the appropriate bit pattern (namely 1 << k for the kth bit); setting the bit uses bit-wise OR, and zeroing it requires something a tiny bit more involved (think about it!).