Code to find next highest power of 2

Compiling + output

[~/temp/astropy-64bit-power-of-2 @Manodeeps-MacBook-Pro] gcc -std=gnu11 -O2 -Wall -Wextra test.c 
test.c: In function 'naive_p2':
test.c:227:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(result < n) {
                  ^
[~/temp/astropy-64bit-power-of-2 @Manodeeps-MacBook-Pro] ./a.out 
Running in 64 bit mode
Checking overflow bug
nbytes = 9223372036854775807 nextp2 = -9223372036854775808  (unsigned) nextp2 = 9223372036854775808
nbytes = -1 nextp2 = 1  (unsigned) nextp2 = 1
nbytes = 0 nextp2 = 1  (unsigned) nextp2 = 1
nbytes = 1 nextp2 = 1  (unsigned) nextp2 = 1
nbytes = 2 nextp2 = 2  (unsigned) nextp2 = 2
nbytes = 3 nextp2 = 4  (unsigned) nextp2 = 4
nbytes = 4 nextp2 = 4  (unsigned) nextp2 = 4
nbytes = 5 nextp2 = 8  (unsigned) nextp2 = 8
nbytes = 6 nextp2 = 8  (unsigned) nextp2 = 8
nbytes = 7 nextp2 = 8  (unsigned) nextp2 = 8
nbytes = 8 nextp2 = 8  (unsigned) nextp2 = 8
nbytes = 9 nextp2 = 16  (unsigned) nextp2 = 16
nbytes = 10 nextp2 = 16  (unsigned) nextp2 = 16
nbytes = 11 nextp2 = 16  (unsigned) nextp2 = 16
nbytes = 12 nextp2 = 16  (unsigned) nextp2 = 16
nbytes = 13 nextp2 = 16  (unsigned) nextp2 = 16
nbytes = 14 nextp2 = 16  (unsigned) nextp2 = 16
nbytes = 15 nextp2 = 16  (unsigned) nextp2 = 16
nbytes = 16 nextp2 = 16  (unsigned) nextp2 = 16
nbytes = 17 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 18 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 19 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 20 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 21 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 22 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 23 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 24 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 25 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 26 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 27 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 28 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 29 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 30 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 31 nextp2 = 32  (unsigned) nextp2 = 32
nbytes = 32 nextp2 = 32  (unsigned) nextp2 = 32
Testing with 4294967295 numbers...
0%.........10%.........20%.........30%.........40%.........50%.........60%.........70%.........80%.........90%.........100% done. Time taken =     8 mins   20 secs
Testing with 4294967295 numbers......PASSED

next_power_of_2.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <inttypes.h>
#include <limits.h>
#include <math.h>
#include <sys/time.h>



/* Beginning of code for printing progress-bar */
#ifndef MAXLEN
#define MAXLEN 1000
#endif


static double SMALLPRINTSTEP;
static char PROGRESSBARSTRING[MAXLEN];
static int beg_of_string_index;
static double percent=0;
static int END_INDEX_FOR_PERCENT_DONE[101];
struct timeval tstart;


/*
  I like this particular function. Generic replacement for printing
  (in meaningful units) the actual execution time of a code/code segment.

  The function call should be like this:

  ---------------------------
  struct timeval t_start,t_end;
  gettimeofday(&t_start,NULL);
  do_something();
  gettimeofday(&t_end,NULL);
  print_time(t_start,t_end,"do something");
  ---------------------------

  if the code took 220 mins 30.1 secs
  -> print_time will output `Time taken to execute `do something' = 3 hours 40 mins 30.1 seconds


  (code can be easily extended to include `weeks' as a system of time unit. left to the reader)
*/


char * get_time_string(struct timeval t0,struct timeval t1)
{
  const size_t MAXLINESIZE = 1024;
  char *time_string = calloc(sizeof(char), MAXLINESIZE);
  double timediff = t1.tv_sec - t0.tv_sec;
  double ratios[] = {24*3600.0,  3600.0,  60.0,  1};

  if(timediff < ratios[2]) {
      snprintf(time_string, MAXLINESIZE,"%6.3lf secs",1e-6*(t1.tv_usec-t0.tv_usec) + timediff);
  }  else {
      double timeleft = timediff;
      size_t curr_index = 0;
      int which = 0;
      while (which < 4) {
          double time_to_print = floor(timeleft/ratios[which]);
          if (time_to_print > 1) {
              timeleft -= (time_to_print*ratios[which]);
              char units[4][10]  = {"days", "hrs" , "mins", "secs"};
              char tmp[MAXLINESIZE];
              snprintf(tmp, MAXLINESIZE, "%5d %s",(int)time_to_print,units[which]);
              const size_t len = strlen(tmp);
              const size_t required_len = curr_index + len + 1;
              if(MAXLINESIZE < required_len) {
                  fprintf(stderr, "buffer overflow will occur: string has space for %zu bytes while concatenating requires at least %zu bytes\n",
                          MAXLINESIZE, required_len);
                  return NULL;
              }
              strcpy(time_string + curr_index, tmp);
              curr_index += len;
          }
          which++;
      }
  }

  return time_string;
}


void init_my_progressbar(const int64_t N,int *interrupted)
{
    if(N <= 0) {
        fprintf(stderr,"WARNING: N=%"PRId64" is not positive. Progress bar will not be printed\n",N);
        SMALLPRINTSTEP = 0.0;
    } else {
        //set the increment
        SMALLPRINTSTEP = 0.01 * N;

        //pre-fill the progress bar string
        //first the 0%
        int index=0;
        snprintf(&(PROGRESSBARSTRING[index]),MAXLEN-index,"%s","0%");
        index+=2;
        END_INDEX_FOR_PERCENT_DONE[0] = index;
        for(int i=1;i<100;i++) {
            if(i%10 == 0) {
                snprintf(&(PROGRESSBARSTRING[index]),MAXLEN-index,"%02d%%",i);
                index += 3;
            } else {
                PROGRESSBARSTRING[index++] = '.';
            }
            END_INDEX_FOR_PERCENT_DONE[i] = index;
        }

        //end with 100%
        snprintf(&(PROGRESSBARSTRING[index]),MAXLEN-index,"%s","100%");
        index+=4;
        END_INDEX_FOR_PERCENT_DONE[100] = index;
        PROGRESSBARSTRING[index+1] = '\0';

    }
    *interrupted=0;
    beg_of_string_index=0;
    gettimeofday(&tstart, NULL);
}

void my_progressbar(const int64_t curr_index,int *interrupted)
{
    if(SMALLPRINTSTEP > 0.0 )   {
      if(*interrupted == 1) {
        fprintf(stderr,"\n");
        *interrupted = 0;
        beg_of_string_index = 0;
      }

      percent = (curr_index+1)/SMALLPRINTSTEP;//division is in double -> C has 0-based indexing -- the +1 accounts for that.
      int integer_percent = (int) percent;

      if (integer_percent >= 0 && integer_percent <= 100)  {
        /*        for(int i=beg_of_string_index;i<END_INDEX_FOR_PERCENT_DONE[integer_percent];i++) */
        /*            fprintf(stderr,"%c",PROGRESSBARSTRING[i]); */

        fprintf(stderr,"%.*s",END_INDEX_FOR_PERCENT_DONE[integer_percent]-beg_of_string_index,&(PROGRESSBARSTRING[beg_of_string_index]));
        beg_of_string_index = END_INDEX_FOR_PERCENT_DONE[integer_percent];
      }
    }
}

void finish_myprogressbar(int *interrupted)
{
  struct timeval t1;
  gettimeofday(&t1, NULL);
  char * time_string = get_time_string(tstart, t1);
  if(SMALLPRINTSTEP > 0.0) {
    if(*interrupted == 0)   {
      if(percent < 100.0) {
        fprintf(stderr,"100%% done.");
      } else {
        fprintf(stderr," done.");
      }
    } else {
      fprintf(stderr,"\n%s done.",PROGRESSBARSTRING);
      *interrupted=0;
    }
  } else {
    fprintf(stderr," done.");
  }
  fprintf(stderr," Time taken = %s\n", time_string);
  free(time_string);

  beg_of_string_index = 0;
  snprintf(PROGRESSBARSTRING,MAXLEN,"%s"," ");
}
/* End of code for printing progress-bar */




ssize_t next_power_of_2(ssize_t n)
{

    /* Calculate the next-highest power of two */
    if(n <= 1) {
        return 1;
    }

#if 0
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    if(sizeof(ssize_t) > 4) {
        n |= n >> 32;
    }
    n++;
#else
    n--;
    const size_t numbits = sizeof(ssize_t)*CHAR_BIT - 1;/* remove one for the sign-bit */
    size_t shift = 1, totbits = 0;
    while(totbits < numbits) {
        n |= n >> shift;
        totbits += shift;
        shift *= 2;
    }
    n++;
#endif


    return n;
}


//Taken from https://stackoverflow.com/a/3974138
void printBits(size_t const size, void const * const ptr)
{
    unsigned char *b = (unsigned char*) ptr;
    unsigned char byte;

    for (int i=size-1;i>=0;i--) {
        for (int j=7;j>=0;j--) {
            byte = (b[i] >> j) & 1;
            fprintf(stderr,"%u", byte);
        }
    }
    fprintf(stderr," ");
}

size_t naive_p2(const ssize_t n)
{
    if(n <= 1) return 1;
    size_t result = 1;
    while(result < n) {
        result *= 2;
    }
    return result;
}



int test_next_power_of_2(ssize_t N)
{
    N = (N < 0) ? SSIZE_MAX:N;
    fprintf(stderr,"Testing with %zd numbers...\n", N);
    int interrupted = 0;
    init_my_progressbar(N, &interrupted);
    for(ssize_t n=0;n<N;n++) {
        my_progressbar(n, &interrupted);
        const ssize_t nextp2 = next_power_of_2(n);
        const ssize_t naivep2 = naive_p2(n);
        if(naivep2 != nextp2) {
            fprintf(stderr,"Error: Failed for nbytes = %zd. Got %zd instead of correct answer = %zd\n",
                    n, nextp2, naivep2);
            fprintf(stderr,"n = %zd binary = ", n);
            printBits(sizeof(ssize_t), (void *) &n);

            fprintf(stderr," nextp2 = %zd binary = ", nextp2);
            printBits(sizeof(ssize_t), (void *) &nextp2);
            fprintf(stderr,"\n");
            return EXIT_FAILURE;
        }
    }
    finish_myprogressbar(&interrupted);
    fprintf(stderr,"Testing with %zd numbers......PASSED\n", N);
    return EXIT_SUCCESS;
}


int main(int argc, char **argv)
{

    (void) argc, (void) argv;
    if(sizeof(ssize_t) == 4) {
        fprintf(stderr,"Running in 32 bit mode\n");
    } else {
        fprintf(stderr,"Running in 64 bit mode\n");
    }

    fprintf(stderr,"Checking overflow bug\n");
    ssize_t nbytes = SSIZE_MAX;
    ssize_t nextp2 = next_power_of_2(nbytes);
    fprintf(stderr,"nbytes = %zd nextp2 = %zd  (unsigned) nextp2 = %zu\n",
            nbytes, nextp2, (size_t) nextp2);

    for(nbytes=-1;nbytes<33;nbytes++) {
        nextp2 = next_power_of_2(nbytes);
        fprintf(stderr,"nbytes = %zd nextp2 = %zd  (unsigned) nextp2 = %zu\n",
                nbytes, nextp2, (size_t) nextp2);
    }

    return test_next_power_of_2(UINT_MAX);
}