带着几分阵列问题 [英] Problems with a bit array
问题描述
我有一个初始化位阵列宏。在typeBitVector_t名称[0]我保存它的大小，一切我使用埃拉托色尼的实际筛。这就是为什么我总是以1递增指数/ LIMIT这是code：
的typedef unsigned long类型typeBitVector_t;
的#define LIMIT（8 * sizeof的（无符号长））
＃定义createArray（名称，大小）\\
typeBitVector_t名= {大小，0} [1 +尺寸/ LIMIT +（（大小％为限）！= 0）];
＃定义whatSize（名）\\
名称[0]
＃定义setBitValue（名称，索引值）\\
（名称[（索引/ LIMIT）+1] =（值））？ （名称[（索引/ LIMIT）+1] | =（1 <<;＆LT;（指数％为限）））：（名称[（索引/ LIMIT）+1]放大器; =〜（1 <<;＆LT;（指数％为限）））;
＃定义returnBitValue（名称，指数）\\
（名称[（索引/ LIMIT）+1]及（1 LT;≤（指数％为限）））？ 1：0INT主要（无效）
{
createArray（myArray的，100）;
无符号长的边界=（无符号长）的sqrt（100）; 的for（int i = 2; I＆LT; =界限;我++）
{
如果（（returnBitValue（myarray的，I））== 0）
{
对于（INT J =我;我* J＆LT; =界限; J ++）
{
setBitValue（myarray的，我*Ĵ，1）;
的printf（关于索引％的位的值为％d个\\ N，我*Ĵ，returnBitValue（myarray的，我* j）条）;
}
}
} 的printf（\\ NTEST出去索引％循环\\ n此位的值为％d个\\ N，8，returnBitValue（myarray的，8））;
}
我附上该程序的输出：
$ ./program
关于指数4位的值为1
关于指数6位的值为1
在指数8位的值为1
索引10位的值为1
在指数9位的值为1考出周期
在指数8位的值为0
所以筛在循环工作的精（它现在列出2和10之间的每一个非黄金价值），而是出于它的重置周期？问题出在哪里？
returnBitValue（myarray的，我* j）条
扩展到
（名称[（我*焦耳/ LIMIT）+1]及（1 LT;≤（我*Ĵ％为限）））？ 1：0
这是从不同的你可能是打算：
（名称[（（我* j）条/ LIMIT）+1]及（1 LT;≤（（我* j）条％为限）））？ 1：0
所以，最起码，你需要在宏展开周围添加首页圆括号。但它仍然将打破，如果你尝试做一些像
returnBitValue（myarray的，我++）
所以最好不要在所有的，如果你能避免它（虽然我明白，这似乎是一个特定的条件，在这种情况下不使用的功能）使用宏。
您也有一些更多的问题 setBitValue ：
（名称[（（索引）/ LIMIT）+1] =（值））？ （... | = ...）：（...＆放大器; = ...）
您大概意思
名称[（（指数）/ LIMIT）+1] =（值）？ （... | ...）（...＆安培; ...）
您也有一个潜在的整数溢出： 1 已键入 INT ，但你把它当作一个长。使用 1L 代替。
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?
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.
这篇关于带着几分阵列问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
