C language to achieve bitmap bitmap code sharing
- 2020-04-02 02:39:10
- OfStack
In fact, we use each element to represent a 32-bit binary string, so that the element can retain information about whether 32 adjacent Numbers exist or not, and the array range drops to 10000000/32. For example, for the number 89256, since 89256 mod 32=2789... 8, so we should set the eighth bit of the 32-bit string in a[2789] (starting with the lowest bit) to 1.
#define WORD 32
#define SHIFT 5 ////If I move 5 bits to the left, that's the same thing as multiplying by 32, and if I move to the right, that's the same thing as dividing by 32
#define MASK 0x1F //31 in hexadecimal
#define N 10000000
int bitmap[1 + N / WORD];
void set(int i) {
bitmap[i >> SHIFT] |= (1 << (i & MASK));
}
void clear(int i) {
bitmap[i >> SHIFT] &= ~(1 << (i & MASK));
}
int test(int i) {
return bitmap[i >> SHIFT] & (1 << (i & MASK));
}
Implement sorting (cannot be repeated) :
int main(void) {
FILE *in = fopen("in.txt", "r");
FILE *out = fopen("out.txt", "w");
if (in == NULL || out == NULL) {
exit(-1);
}
int i = 0;
int m;
for (i = 0; i < N; i++) {
clear(i);
}
while (!feof(in)) {
fscanf(in, "%d", &m);
printf("%d/n", m);
set(m);
}
printf("abnother");
for (i = 0; i < N; i++) {
if (test(i)) {
printf("%d/n", i);
fprintf(out, "%d/n", i);
}
}
fclose(in);
fclose(out);
return EXIT_SUCCESS;
}