()位运算实现位向量有关问题
(求助)位运算实现位向量问题C/C++ code#include stdio.h#define BITSPERWORD 32#define SHIFT 5#define
(求助)位运算实现位向量问题
C/C++ code#include <stdio.h>#define BITSPERWORD 32#define SHIFT 5#define MASK 0x1F#define N 10000000int a[1 + N/BITSPERWORD];void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }int main(){ int i; for (i = 0; i < N; i++) clr(i); while (scanf("%d", &i) != EOF) set(i); for (i = 0; i < N; i++) if (test(i)) printf("%d\n", i); return 0;}
主要没理解到set(), clr(), test()的精髓，高手给指点下：
1. 为什么定义数组a[]时，要用1+N/32, 而不是1+N？
2. a[i>>SHIFT]疑问：比如给定i=26,右移5位( 0x00011010>>5 )后,i = 0x00000001 = 1， 成了a[1]？
3. （1<<(i & MASK))疑问：同2，i=26(即i = 0x00011010), (i & 0x00011111) = 0x00011010(也是26), 那1<<(i&MASK)不就成了1左移26位？成0了，那么最后的a[i>>SHIFT] |= (1<<(i & MASK)); 这个或操作不是就没意义了吗？
是我哪个地方理解出问题了，把问题弄这么畸形了
[解决办法]1.因为作者认为int是32位的，所以每个int能表示32个数，但是这种假设是危险的。
2.>>5等价于/32，26>>5其结果应该是0
3.作者假定的int是32位的，不是8位的字节。那么1<<26应该的二进制应该是00000100 00000000 00000000 00000000=0x04000000
另外0x应该是用来表示16进制的，不是用来修饰二进制的。
