CareerCup

Isnt this a favorite question?

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}

Excellent link showing different ways of solving the problem

http://www-db.stanford.edu/~manku/bitcount/bitcount.html

One more recursive method:

unsigned int bitCount( unsingned int data)
{
if(data & 1 == 1)
return (1 + bitCount(data>>=1));
else
return (bitCount(data>>=1));
}

unsigned int bitCount(unsingned int data)
{
int count=0;
while(data)
{
count++;
data = data & (data-1);
}
return count;
}

unsigned int BitCount( usigned int x)
{
x= ((x&0xAAAA)>>1)+(x&0x5555);
x= ((x&0xCCCC)>>2)+(x&0x3333);
x= ((x&0xF0F0)>>4)+(x&0x0F0F);
x= ((x&0xFF00)>>8)+(x&0x00FF);

}

in above program, 'return x;' is missing.

unsigned int bitcount ( unsigned int x )
{
unsigned int max_count = sizeof(int),count = 0;
unsigned int base = 1;

while ( x & base && count <= max_count)
{
/* increase count , and shift base bit */
count++;
base << 1;
}

return count;
}

int bitcount(unsigned int x)
{
int num = 0;

while (x)
{
if (x & 1 == 1) or x = x&(x-1);
{ num++; num++;
}
x = x>>1;
}
return num;
}

How abt using quicksort and incrementing static variable if there is swap between two bits..time complexity will be lesser!!

?

private static count = 0;
public int CountOnIntegers(int someInteger)
{

while (someInteger != 0)
{
if ((someInteger & 1) == 1)
count++;
someInteger = someInteger >> 1;
}


return count;
}

I won't write out the code (cuz I'm lazy) but I have a very different approach to this that would be much faster than the above methods - but there's definitely a memory trade off.

Preinitialize an array of length 256 bytes. Initialize each element of the array with the number of bytes for that index. For example:

array[0] = 0; // because '0' has 0 ON bits
array[1] = 1; // because '1' has 1 ON bit
array[2] = 1; // because '2' has 1 ON bit
array[3] = 2; // because '3' has 2 ON bits
...
array[255] = 8; // because '255' has 8 ON bits

Then take your 32 bit integer and break it into 4 8-bit pieces. Use each piece as an index into the above array. Add up the 4 values. Bam! You're done. You could also preinitialize an array of length 65536 and break your 32 bit integer into 2 16-bit pieces. Hell, you could preinitialize an array of length 4294967296 and just use the original number as an index into the array.

unsigned int numberOfOnBit(int n)
{
if(n == 0)
return 0;
unsigned c = 0;
while(n != 1)
{
n = n >> 1;
c++;
}
return c;
}

Xuka,

which bit ar you checking? And when does 'n' will be 1. ?

int no_of_onbit(int val)
{
while(val)
{
val = val & (val-1);
count++;
}

return count;
}

short count_on_bits(int number)
{
	short count = 0;
	short bit_count = 0;
	while(sizeof(int)*8 > bit_count) {
		if(number & 1) {
			count++;
		}
		number >>= 1;
		bit_count++;
	}
	return count;
}

int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}

I had the same idea as John ( mentioned in an earlier post), and here's the code.

/* number of bits set to 1 for 0 - 15 */
int numBits = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};

int numBitsSet(unsigned x)
{
int ii = 0, mask = 0x000F;
for(ii = 0; ii < 4; ii++)
{
s = ii * 4; /* to shift mask by 4 bits each iteration */
count += numBits[(mask<<s) & x];
}

return count;
}

What most of the algorithms here is doing is counting the number of on bits which is undoubtedly trivial.. The actual question was how can u tell the no. of ON bits in a number without counting..

int count_ones(int num) {
int count = 0;
while(num) {
count++;
num = num & (num-1);
}
}

int numOnBits(int num){

	int count =0;
	while(num>0){
		if(num ^ ((num>>1)<<1))
			count++;
		num = num>>1;
	}

	return count;

}

#include<stdio.h>
main()
{ int i,j,n,s=0;
printf("Enter the input\n");
scanf("%d",&n);
while(n>0)
{ if(n&1==1)
s++;
n=n>>1;
}
printf("The no of ON bits are %d\n",s);
}