CareerCup

000
001
010
011
100
101
110
111

no of 1s count in 3 digit nos ( from 0 to 7 ) = pow(2, 3-1 ) * (3) = 12

no of 1s count in 4 digit no.s ( from 0 to 15 ) = pow(2, 4-1 ) * (4) = 32

if 4th digit is 1, which means number is greater than 7,
1s count = 3 digit 1s count + add how many times current 4th bit is 1 ( this is equal to num % 7).



int NoOfONEs(int num)
{
int i =1, count =0 ;

if( num & 1 )
{
count ++;
}

while ( i < 32)
{
if ( num & ( 1<< i ) )
{
count + = pow(2, i-1 ) * (i ) + num % (pow(2, i ) )+ 1 ;
}

i++;
}

return count;
}

for each bit, divide the number into 3 parts: high now low
for example: 110110, if we are processing the third bit, 110->high,1->now,10->low, (i=2)
Let's see how many ways we can make the bit now to "1"
If now is 1, when the higher part is less than high, the lower part can be 00...0--11...1, so that is high*(1<<i).. when the higher part is high, the lower part can be 000--low, so that is low+1;
If now is 0, the higher part can only be less than high, so that is high*(1<<i)

int count(int n)
{
int a[40],len=0,tmp=n;
while(n)
{
a[len++]=n&1;
n>>=1;
}
int low=0,high=tmp>>1,ans=0;
for(int i=0;i<len;i++)
{
ans+=high*(1<<i);
if(a[i]==1)
{
ans+=low+1;
low+=(1<<i);
}
high>>=1;
}
return ans;
}

c(pow(2, k)) = 2*c(pow(2, k-1)) + k-1

Given below is the code. Basically, imagine each bit position to be a periodic impulse train of periods 2, 4, 8, 16, 32 .... So the period of the impulse train at 8th bit is 2^i. A 1 appears in the train only when atleast 50% of a period is complete. So the number of ones 25% completed period is 0 but no of ones in a 75% period is 0.25*(no of ones in full period). With that in mind, given below is the solution

package org.axecapone.programming;

public class NoOfOnes {
	
	private int val = 0;
	
	public NoOfOnes(int i) {
		val = i;
	}
	
	public int countOnes() {
		int copy = val + 1;
		int divisor = 2;
		int count = 0;
		while(divisor <= copy) {
			count += (copy/divisor)*(divisor>>1);
			if(copy%(float)divisor - (divisor>>1) > 0)
				count += ((copy%(float)divisor) - (divisor>>1));
			
			divisor = divisor<<1;
		}
		
		if(copy%(float)divisor - (divisor>>1) > 0)
			count += ((copy%(float)divisor) - (divisor>>1));

		return count;
	}
	
	public static void main(String[] args) {
		NoOfOnes test = new NoOfOnes(7);
		System.out.println(test.countOnes());
	}

}

unsigned int countSetBit(unsigned int n)
{
	unsigned int v = 0;
	for (unsigned int bit = 1; bit <= n; bit <<= 1)
		v += ((n>>1)&~(bit-1)) + ((n&bit) ? (n&((bit<<1)-1))-(bit-1) : 0);
	return v;
}

Solution with complexity logn

int x=n+1;
int p=(int)(Math.log(x)/Math.log(2));
int ones=x/2;
int f,q;
for(int i=1;i<=p;i++)
{
f=(int)Math.pow(2,i);
q=x/f;
if(q==1)
ones=ones+(x%f);
else if(q%2==0)
ones=ones+(q/2)*f;
else
ones=ones+(q/2)*f+(x%f);
}

{{
int f(int n) {
if(!n)
return 0;
if(n==1)
return 1;
int l=log2(n);
return f(pow(2,l)-1)+n-pow(2,l)+1+f(n-pow(2,l));
}

int main() {
for(int i=0;i<16;i++)
cout<<f(i)<<endl;
}
}}

int floor_of_log(int n)
{ int i = 0;
 while(n/2 >0)
   { i++;
    n /= 2
   }
 return i;
}
int f(int n)
{ 
   int x,y;
  if (n == 1)
  return 1;
  else
     {    x=floor_of_log(n);
          y=pow(2,x);
          return f(y)+(n-y)+f(n-y-1);
     }
}

/*corrected*/

int floor_of_log(int n){ int i = 0; while(n/2 >0)   { i++;    n /= 2   } return i;}int f(int n){    int x,y;  if (n == 1)  return 1;  else     {    x=floor_of_log(n);          y=pow(2,x) - 1;          return f(y)+(n-y)+f(n-y-1);     }}