CareerCup

only count the number of one.

public int countOnes(int value)
	{
		int counter = 0;
		while (value > 0)
		{
			value = value & (value - 1); //去掉最后一个1
			counter++;
		}
		return counter;
	}

Why not be keep a table of size 2^8.
Each entry in table will hold number of bits in the number with number as the index into the table entry.
Solution then will be like this -->
Each number is composed of consecutive bytes, say 4 bytes.
1) Get the size of memory location holding the number.
2) right shift 8 bits from the number and store them in a variable, say X
3) update the number with right shifted value or use another variable to store updated value, say Y
4) index into the table of size 2^ 8 using X.
5) Repeat step step 2 to 4 using Y.

Now the size of a number is constant (even if it is machine dependent). So run time of this algorithm will be O(1).

#include<stdio.h>
int main(){

int x=65536;
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF);
printf("%d",x);
}

this is O(1) I think.

Since we got enough space.

int a [32]={1,1,1.....32 1's};
no_bits=n&a[0]+n&a[1]+......n&a[31];
return no_bits;

There is no limit on memory. So just use a array map for each possibility.

In C# (this is the simplest solution but not O(1)):

public static int CountOnes(int value)
{
int counter = 0;
byte b = 1;

while (value>0)
{
if ((value & b) == b)
counter++;
value = value >> b;
}
return counter;
}

O (lg n) where is n = 32 for 32-bit integer. For loop, other are discussing is O(n). Hash table is surely is O(1), but it unfeasible for 4 billions values.

lg n solution for 64-bit number will take lg n = lg 64 = 6 arithmatics (does not justify 2^64 hash entries).

unsigned int count_ones(unsigned int a)
{
    a = (a & 0x55555555) + ((a >> 1) & 0x55555555));
    a = (a & 0x33333333) + ((a >> 2) & 0x33333333));
    a = (a & 0x0f0f0f0f) + ((a >> 4) & 0x0f0f0f0f);
    a = (a & 0x00ff00ff) + ((a >> 8) & 0x00ff00ff);
    a = (a & 0x0000ffff) + ((a >> 16) & 0x0000ffff);
}

It is always constant time. Your number can have at most as many bits as the architecture allows. It is not dependent upon how big or small the number is.