Как использовать бит-массив

Question

Я написал код для класса, чтобы найти простые числа.

Учитель говорит, что мне нужно пересмотреть свой код ниже требования:

1. использовать битовый массив для хранения простого числа проверки. Битовый массив также будет находиться в куче.
2. Максимальное значение цельного числа без знака 32-бит (UINT_MAX) используется для максимального размера простого числа, которое вы хотите проверить.

Я не хочу полного ответа, так как это my домашнее задание.

Но может ли кто-нибудь дать некоторые подсказки, чтобы помочь мне начать?

Я новичок в C, поэтому мне сложно понять, как это исправить.

#include <stdio.h> 
#include <stdlib.h> 
#include <unistd.h> 
#include <pthread.h> 
#include <getopt.h> 
#include <ctype.h> 
#include <stdint.h> 

//function to set all non-primes to 0 
void *zero_multiples(void *threadid); 

//global variables 
int m = 0;     //nums[] array size 
int c = 0;     //number of threads 
long int *nums = NULL;  //array of numbers 
int *done_sw = NULL;  /* indicates that all threads are complete */ 
int *did_work_sw = NULL; /* indicates which threads actually did work */ 

int main (int argc, char *argv[]) 
{ 
    pthread_t *threads = NULL;    /* threads structure */ 
    int rc;         /* return code for pthread_create() */ 

    int command = 0;      /* command line arguments */ 
    int i = 0, k = 0;      /* for loops */ 


    int debug_level = 0;     /* used for verbose messaging to screen */ 
    int done_sw_main = 0;     /* used to check if all the threads have finished */ 
    int did_work_howmany = 0;    /* tallies how many threads actually did work */ 

    int n_primes = 0;      /* tallies the number of primes found */ 


    while((command = getopt(argc, argv, "m:c:v")) != EOF) 
    { 
     switch(command) 
     { 
      case 'm': m = strtol(optarg, (char **) NULL, 10); 
       break; 

      case 'c': c = strtol(optarg, (char **) NULL, 10); 
       break; 

      case 'v': debug_level++; 
       break; 
     } 
    } 

    //print n and c 
    if(debug_level) 
     printf("m=%d, c=%d\n", m, c); 

    //allocate nums[] 
    nums = (long int *)malloc(m * sizeof(long int)); 
    if(nums == NULL) 
    { 
     fprintf(stderr, "nums out of memory!\n"); 
     exit(EXIT_FAILURE); 
    } 

    //population nums[] array from 1 to n 
    for(i=1; i<m; i++) 
    { 
     nums[i]=i+1;   //start at index 1 because the number '1' can be zeroed out 
    } 

    //allocate the threads[] array 
    threads = (pthread_t *)malloc(c * sizeof(pthread_t)); 
    if (threads == NULL) 
    { 
     fprintf(stderr, "Threads: memory allocation error\n"); 
     exit(EXIT_FAILURE); 
    } 

    //allocate done_sw array 
    done_sw = (int *)malloc(c * sizeof(int)); 
    if(done_sw == NULL) 
    { 
     fprintf(stderr, "done_sw Out of memory!\n"); 
     exit(EXIT_FAILURE); 
    } 

    //allocate did_work_sw[] array 
    did_work_sw = (int *)malloc(c * sizeof(int)); 
    if(did_work_sw == NULL) 
    { 
     fprintf(stderr, "did_work_sw Out of memory!\n"); 
     exit(EXIT_FAILURE); 
    } 

    //create threads and run zero_multiples 
    for(i=0; i < c; i++) 
    { 
     if(debug_level>1) 
      printf("Creating thread %d\n", i); 

     //create thread to run zero_multiples() 
     rc = pthread_create(&threads[i], NULL, zero_multiples, (void *)(intptr_t)i); 
     if (rc) 
     { 
      printf("ERROR; return code from pthread_create() is %d\n", rc); 
      exit(-1); 
     } 
    } 


    //main program wait until all threads are complete 
    //exit only when all threads have set their done_sw 
    while(done_sw_main < c) 
    { 
     done_sw_main = 0; 
     for(i=0; i<c; i++) 
     { 
      done_sw_main = done_sw_main + done_sw[i]; //count how many threads are done 
     } 
    } 

    //count number of threads that did work 
    did_work_howmany = 0; 
    for(i=0; i<c; i++) 
    { 
     did_work_howmany = did_work_howmany + did_work_sw[i]; 
    } 

    //count the number of primes found 
    if(debug_level) 
    { 
     n_primes = 0; 
     for(k=0; k < m; k++) 
     { 
      if(nums[k] != 0) 
      {n_primes++;} //primes are all the non 0 numbers remaining in nums[] 
     } 
     printf("n_primes=%d\n", n_primes); 
    } 

    //stop timer 
    status=gettimeofday(&tv_2,0); 

    //calculate elapsed time 
    timeval_subtract(&result,&tv_2,&tv_1); 

    //report results 
    printf("%d %d %d %d\n", m, c, did_work_howmany, n_primes); 

    //all done 
    pthread_exit(NULL); 
} 


//Function that each thread executes to zero out multiples of primes they find 
void *zero_multiples(void *threadid) 
{ 
    int prime = 0; //current prime 
    int i_prime= 0; //current prime index in nums[] 
    int i, k;  /* for looping */ 

    /* Each thread reads nums[] up to sqrt(n) 
    If a positive number is encountered, it is prime: 
    the number is negated, and all multiples are zeroed 
    then continues looping looking for positive (prime) numbers */ 
    for(i = 0; i*i <= m; i++) /* read nums[] until locate a positive number or until sqrt(n) */ 
    { 
     prime = nums[i]; 
     i_prime = i; 

     if(prime>0) //if locate a positive number, it must be prime 
     { 
      did_work_sw[(int)(intptr_t) threadid]=1; /* indicates that this thread did some work */ 
      nums[i_prime] = -nums[i_prime]; /* set current prime to negative */ 
      for (k = i_prime + prime; k < m; k = k + prime) /* mark multiples to 0 */ 
      { 
       nums[k] = 0; 
      } 
     } 
    } 

    done_sw[(int) (intptr_t) threadid]=1; //indicate that this thread is complete -- no more primes left 

    pthread_exit(NULL); 
} 

Answer 1

Не уверен, если это поможет, но here являются битовые, сделанные в массив. Вот базовое поле бит:

struct 
{ 
    type [member_name] : width ; 
};