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

Related articles: