4

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.

Tomas Pruzina
  • 8,397
  • 6
  • 26
  • 39

3 Answers3

5

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)

unwind
  • 391,730
  • 64
  • 469
  • 606
asaelr
  • 5,438
  • 1
  • 16
  • 22
4

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!).

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • It will work for `CHAR_BIT>8` (but not use all bits), and even if `CHAR_BIT<8`, `x` can be `int[]` – asaelr Feb 12 '12 at 12:23
  • @asaelr: Well, depends on the specification, I suppose, whether you want a tight bitfield or just "some bits somewhere". For a tight bitfield, `x` essentially has to be an array of `unsigned char`s; or we should modify it to `CHAR_BIT * sizeof(x)` for the general case. – Kerrek SB Feb 12 '12 at 12:31
  • @asaelr so when I use f.e. 4B integer (int32_t), it will use just first byte of each integer? That does not seem right, I wanna do something like int32_t *sieve= malloc( (max_index % 32 == 0 ? max_index/32 : max_index/32 +1) * sizeof(int32_t)); Working with chars will make it simplier, but I guess it does not matter much. – Tomas Pruzina Feb 12 '12 at 12:33
  • @AoeAoe: Indeed, you will only use the first byte with my code, and only the first eight bit with your code, of each array element. Multiply by `sizeof(x)` to use the entire element. (`sizeof` returns the size in bytes.) – Kerrek SB Feb 12 '12 at 12:36
  • http://stackoverflow.com/questions/2098149/what-platforms-have-something-other-than-8-bit-char – Karoly Horvath Feb 12 '12 at 12:37
  • @KerrekSB I guess you meant `CHAR_BIT*sizeof(*x)`. @AoeAoe your code access the first 8 bits of every element. if the element is not `char`, and you want to access all its bits, use `CHAR_BIT*sizeof(*x)`. BTW, you can write just `(max_index+31)/32`, and `sizeof(int32_t)` is always 4. – asaelr Feb 12 '12 at 12:40
  • Thank you all for valueable comments, I mark this one as "solving" and will upvate asaelr's answer. Thanks again. – Tomas Pruzina Feb 12 '12 at 12:42
-1
#define ISBITSET(x,i) (((x)[(i) / CHAR_BIT] & (1u << ((i) % CHAR_BIT))) != 0)
#define SETBIT(x,i) (x)[(i) / CHAR_BIT] |= (1u << ((i) % CHAR_BIT);
#define CLEARBIT(x,i) (x)[(i) / CHAR_BIT] &= ~(1u << ((i) % CHAR_BIT))
  • Always put parenthesis around macro arguments
  • always prefer unsigned types for bit operations
  • (1u << CHAR_BIT) is 256 for 8 bit platforms
  • there was an exra ; after the last macro
wildplasser
  • 43,142
  • 8
  • 66
  • 109
  • 3
    How does this explain *at least one of them in detail* ? – cnicutar Feb 12 '12 at 12:14
  • I don't intend to do the work of the teacher. I just wanted to point out the trivial errors that are present in this exercise. – wildplasser Feb 12 '12 at 15:16
  • 1
    I was merely remarking your answer is useful but doesn't *answer* the question. – cnicutar Feb 12 '12 at 15:19
  • I don't care about downvotes. I just don't like doing *wrong* homework exercises for lazy people. I probably spent more time on the *wrong* answer than the OP did on his cut&paste job. – wildplasser Feb 12 '12 at 15:25