Viewing and Counting Set Bits in an Integer

[Adak]

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.

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

[qwertylurker]

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")

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

[Adak]

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.

[itCbitC]

Yet another way of counting set bits would be

while (x && (x &= (x-1)) >= 0) i++;

[Adak]

Thank you! I thought there was a one line loop for this, but I couldn't find it.

[qwertylurker]

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.

[cyberfish]

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.

[itCbitC]

Right you are. The question asked was

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

Nope!

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

[iMalc]

You don't have this page bookmarked do you?: Bit Twiddling Hacks

[Adak]

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.