Problems with a bit array

Question

I have macros which initialize a bit array. In typeBitVector_t name[0] I store its size, everything else I use for the actual sieve of eratosthenes. That's why I always increment index/LIMIT by 1. This is the code:

typedef unsigned long typeBitVector_t;
#define LIMIT (8*sizeof(unsigned long))
#define createArray(name,size) \
    typeBitVector_t name[1 + size/LIMIT + ((size%LIMIT) != 0)] = {size, 0};    
#define whatSize(name) \
    name[0]
#define setBitValue(name, index, value) \
    (name[(index/LIMIT)+1] = (value)) ? (name[(index/LIMIT)+1] |= (1<<(index%LIMIT))) : (name[(index/LIMIT)+1] &= ~(1<<(index%LIMIT)));
#define returnBitValue(name, index) \
    (name[(index/LIMIT)+1] & (1<<(index%LIMIT))) ? 1 : 0

int main(void)
{
    createArray(myArray,100);
    unsigned long bounds = (unsigned long) sqrt(100);

    for(int i = 2; i <= bounds; i++)
    {
        if((returnBitValue(myArray,i)) == 0)
        {
            for(int j = i; i * j <= bounds; j++)
            {
                setBitValue(myArray, i*j, 1);
                printf("The bit on index %d has the value %d\n", i*j, returnBitValue(myArray, i*j));
            }
        }
    }

    printf("\nTest out of the cycle\nThe bit on index %d has the value %d\n", 8, returnBitValue(myArray, 8));
}

I enclose the output of this program:

$ ./program
The bit on index 4 has the value 1
The bit on index 6 has the value 1
The bit on index 8 has the value 1
The bit on index 10 has the value 1
The bit on index 9 has the value 1

Test out of the cycle
The bit on index 8 has the value 0

So the sieve is working "fine" in the cycle (it now lists every non prime value between 2 and 10) but out of the cycle it's reset? Where is the problem?

Answer 1

returnBitValue(myArray, i*j)

Expands to

(name[(i*j/LIMIT)+1] & (1<<(i*j%LIMIT))) ? 1 : 0

Which is different from what you probably intended:

(name[((i*j)/LIMIT)+1] & (1<<((i*j)%LIMIT))) ? 1 : 0

So at the very least you will need to add parantheses around index in the macro expansion. But it will still break if you try to do something like

returnBitValue(myArray, i++)

so better don't use macros at all if you can avoid it (although I understand that it seems to be a specific condition to not use functions in this case).

You also have some more problems in setBitValue:

(name[((index)/LIMIT)+1] = (value)) ? (... |= ...) : (... &= ...)

You probably meant

name[((index)/LIMIT)+1] = (value) ? (... | ...) : (... & ...)

You also have a potential integer overflow: 1 has type int, but you treat it as a long. Use 1L instead.

Answer 2

indexing bit value error. Correct to (name[index / 8] & (1<<(index % 8)))

index / 8 is byte in array[0..Size], index % 8 is bit in that byte