c - 位数组的问题

Question

我有初始化位数组的宏。在 typeBitVector_t name[0] 中，我存储它的大小，以及我用于埃拉托色尼实际筛选的所有其他内容。这就是为什么我总是将 index/LIMIT 递增 1。这是代码:

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));
}

我附上这个程序的输出:

$ ./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

所以筛子在循环中工作“正常”(它现在列出了 2 到 10 之间的每个非质数)但在循环之外它被重置了？问题出在哪里？

Answer 1

returnBitValue(myArray, i*j)

展开为

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

这与您可能想要的不同:

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

因此，至少您需要在宏扩展中的 index 周围添加括号。但如果你尝试做类似的事情，它仍然会崩溃

returnBitValue(myArray, i++)

所以如果可以避免的话，最好不要使用宏(尽管我知道在这种情况下不使用函数似乎是一个特定条件)。

setBitValue 还有一些问题:

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

你可能是说

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

您还有一个潜在的整数溢出:1 的类型为 int，但您将其视为 long。请改用 1L。