# 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. ## Viewing and Counting Set Bits in an Integer

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. 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. 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. Yet another way of counting set bits would be
Code:
`while (x && (x &= (x-1)) >= 0) i++;`

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

6. 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. 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. Originally Posted by Adak
Right you are. The question asked was

"Is there a multiple of 15 with less than 4 bits set to 1?"
Nope!
Originally Posted by Adak
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. You don't have this page bookmarked do you?: Bit Twiddling Hacks

10. Originally Posted by 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.
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