Viewing and Counting Set Bits in an Integer

This is a discussion on Viewing and Counting Set Bits in an Integer within the C Programming forums, part of the General Programming Boards category; Good, Bad, So-So? The question was, in positive multiples of 15, what bits are set to 1? Turbo C has ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868

    Viewing and Counting Set Bits in an Integer

    Good, Bad, So-So?

    The question was, in positive multiples of 15, what bits are set to 1?

    Turbo C has specific extensions for dealing with bits in a byte, but I was trying for a more standard C way of counting and displaying the set bits in an unsigned long of 4 bytes.

    Suggestions encouraged.

    Code:
    /*
    4,294,967,295 == ULONG_MAX
    
    */
    
    #include <stdio.h>
    //include <limits.h>  //for Turbo C only
    #define ULONG_MAX 4294967295  //for non Turbo C compilers
    
    int main() {
      int i, j, k, got1, cbits[33]; //cbits shows the bits, when displayed
      unsigned long n; 
      unsigned long a[33];      //power of 2 array
    
      printf("\n\n Sizeof(unsigned long): %d maximum unsigned long is: %lu",sizeof(unsigned long),ULONG_MAX);
      n=2;
      i=1;
      a[i]=i;
      /* build powers of 2 array for bit work */
      while(n < ULONG_MAX && n > 0) { 
        a[++i] = n;
        printf("\n n == %lu  i== %d", n, i);
        if(i % 22==0)  {
          printf("\n   press enter to continue");
          getchar();
        }
        n *= 2;
      }
    
      /* processing section */
      k=0;
      n=15;
      while(n < ULONG_MAX) {
        for(j=0;j<33;j++)         //clear the display array
          cbits[j]=0;
    
        for(i=1, got1=0;i<33;i++) {
          if(n & a[i]) {       //AND with the mask
            ++got1;          //got a 1 bit
            cbits[i] = 1;     //set the cbit index that represents the bit
          }
        }
        if((got1 == 4 ) || (got1 > 25))  {  //displays number, # of bits set, and bytes
          printf("\n#%6d: N %8lu has %d 1 bits: ", ++k, n, got1);
          for(j=32;j>0;j--) {
            printf("%d", cbits[j]);
            if((j % 8==1) ) //&& j < 32)
              putchar(' ');
          }
          if(k%22==0) {
            printf("\n hit enter to continue");
            getchar();
          }
        }
        n+=15;
      }
      printf("\n\n\t\t\t     press enter when ready");
      i = getchar();
      return 0;
    }

  2. #2
    Registered User
    Join Date
    Jul 2010
    Posts
    26
    Quote Originally Posted by Adak
    Code:
    if((got1 == 4 ) || (got1 > 25)){
    Unless I'm making some mistake reading the code, control will enter this loop if n has 4 bits set or more than 25 bits set. If this is correct, what is the significance of 4 and 25 here? Why do you print out the bits/bytes on the screen only when those specific condition(s) for got1 are met?

    I think another way of counting number of set bits in any 32 bit number num would be this:
    (Untested code, doesn't need the "power of 2 array")
    Code:
    int number_of_set_bits=0;
    int i=1;
    int cbits[33];
    while(num)
    {
        if(num & 1) 
        {
            //LSB of num is 1 (set).
             number_of_set_bits++; 
             cbits[i]=1;
        }
        else //LSB of num is 0 (unset)
            cbits[i]=0;
        num>>=1; //Right shift num 
        i++;
    }

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Right you are. The question asked was

    "Is there a multiple of 15 with less than 4 bits set to 1?"

    And I wanted to see the most bits set in a multiple of 15, as well. Just curious.

    Since it loops to > 4 billion, it's important not to have it print out all the bits for every multiple of 15, along the way.

    Thanks for your posted code, btw. I haven't tried it yet, but will give it a run through shortly, along with a few other bits of code to make this conversion.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Yet another way of counting set bits would be
    Code:
    while (x && (x &= (x-1)) >= 0) i++;

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Thank you! I thought there was a one line loop for this, but I couldn't find it.

  6. #6
    Registered User
    Join Date
    Jul 2010
    Posts
    26
    Code:
    And I wanted to see the most bits set in a multiple of 15, as well. Just curious.
    4294967295 (ULONG_MAX) is divisible by 15.

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    If you are after speed, some platforms have an instruction for population counting in hardware.

    If you don't want to write assembly, the easiest way is probably compiler intrinsics.

    I know GCC has one for bit counting, no idea about Turbo C. It will use the hardware instruction where available, and provide a fast software implementation otherwise, and you don't need to change your code at all.

  8. #8
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by Adak View Post
    Right you are. The question asked was

    "Is there a multiple of 15 with less than 4 bits set to 1?"
    Nope!
    Quote Originally Posted by Adak View Post
    And I wanted to see the most bits set in a multiple of 15, as well. Just curious.
    Depends on the sizeof type chosen viz., for an 8 byte long long it'd be 0xffffffffffffffff

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    You don't have this page bookmarked do you?: Bit Twiddling Hacks
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by cyberfish View Post
    If you are after speed, some platforms have an instruction for population counting in hardware.

    If you don't want to write assembly, the easiest way is probably compiler intrinsics.

    I know GCC has one for bit counting, no idea about Turbo C. It will use the hardware instruction where available, and provide a fast software implementation otherwise, and you don't need to change your code at all.
    Turbo C has some special instructions for bit work, but I wanted to make this more portable. I'm curious to see what it can do though, now.

    Assemby = dark pit with very little light. Intriguing stuff though.

    Thanks for the responses everyone, and the bit-twiddling web site.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21