C Puzzles

yet another place for C puzzles

Tuesday, December 19, 2006

bit count

Write an efficient C program to count the number of bits set in an
unsigned integer.


i/p     o/p
====    ===
0(00)    0
1(01)    1
2(10)    1
3(11)    2
.....  ...

Ans:


int count_bit_set(unsigned int b)
{
    int count =0;
    while(b) {
       b = b & (b-1);
       count++;
    }
    return count;
}

posted by yetanother.softwarejunk # 4:00 PM

Comments:

print_bits(int num)
{
int bits=0;
while(num)
{
if(num & 1) bits++;
n >>= 1;
}
printf("\nNumber of ones is %d\n",bits);
}

This will work ... for more efficiany we can do like

if(num & 1) bits++;
if(num & 2) bits++;
if(num & 4) bits++;
if(num & 8) bits++;

then
shift dirctly by four
n>>=4

This will reducess the shifting

Rahul Ugale(Calsoft,Pune)

# posted by

Anonymous : 1:15 PM, December 31, 2006

//b -> input number
//a - >the result
for (a = 0; b; b >>= 1)
{
a += b & 1;
}

# posted by

Anonymous : 9:12 PM, February 06, 2007

another efficient version which works
in o(no of bits set)

count(unsigned int x)
{
int count=0;
while(x)
{

count++;
x=x&(x-1)
}
}

# posted by

Vijay : 3:58 PM, April 24, 2008

C Puzzles

Tuesday, December 19, 2006

bit count

Archives