## Microsoft Interview Question Developer Program Engineers

- 0of 0 votes
How to count the number of ones in the a number's representation. If the number is too large and how would you speeden up using parallel processing or any other technique?

**Country:**India

one correctio:- n(typ)

no3 must be :- no&((2^8 -1)<<16)

generic

no x = no&((2^8 -1)<<8*(x-1))

#include<iostream>

using namespace std;

int main()

{

int n,count=0;

cin>>n;

while(n!=0)

{

count++;

n=n&(n-1);

// cout<<n<<endl;

}

cout<<count;

return(0);

}

without parallel processing naive method is :-

simply % 2 to increase the count of 1 and then divide by 2(basically checking the last bit of the no till Most significant bit comes to last bit)

With parallel processing ideal logic must be divide total no bits that your no can have into different set and parallel process each one of them

- krbchd on July 29, 2012 Edit | Flag Replyfor eg if you have a 64 bit no divide 64 bit into 8 set of 8 bits

no1 = no&(2^8-1 <<0)

no2 = no&((2^8-1) << 8)

no3 = no&((2^801) << 16).

.

.

so on till no8

now for each no calculate separately in each processor the no of 1's and then add them.

..