# Bit Count In Product

Bit Count In Product. Explain with examples:

Write a function:
int solution(int A, int B);
that, given two non-negative integers A and B, returns the number of bits set to 1 in the binary representation of the number A * B.
For example, given A = 3 and B = 7 the function should return 3, because the binary representation of A * B = 3 * 7 = 21 is 10101 and it contains three bits set to 1.
Assume that:
·   A and B are integers within the range [0..100,000,000].
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

The process of finding the set bits explained below
n =  9 (1001)
count = 0

Since 9 > 0, subtract by 1 and do bitwise & with (9-1)
n = 9&8  (1001 & 1000)
n = 8
count  = 1

Since 8 > 0, subtract by 1 and do bitwise & with (8-1)
n = 8&7  (1000 & 0111)
n = 0

count = 2

Since n = 0, return count which is 2 now

NOTE: The time Complexity:
O(logn)

Multiplication of two bits:

```unsigned
hash( char const* str )
{
unsigned hash = 0;
while ( * str != '\0' ) {
hash = 127 * hash + (unsigned char)* str;
++ str;
}
return hash;
}
```
Finding the set bit count: The below functions are used to get no of set bits in binary representation of passed binary no.
```int count_SetBits(unsigned int n)
{
unsigned int count = 0;
while(n)
{
count += n & 1;
n >>= 1;
}
return count;
}
```
/* Program to test function count_SetBits */
```int main()
{
int iHash = hash (“TEMP”);
printf ("%d", count_SetBits(iHash));
getchar ();
return 0;
}
```
In the better way see below code:
```int Cnt_SetBits(unsigned int value) {
int count;
for (count = 0; value != 0; count++, value &= value-1);
return count;
}
```
The code relies on the fact that the expression x &= x-1; removes the rightmost bit from xthat is set. We keep doing so until no more 1's are removed. This technique is described in K&R. This approach is superior because it doesn't depend on an integer's size - it's totally portable - and it tests every bit in a fairly efficient way (with the comparison value != 0). Also, you might want to replace 32 in main() with sizeof(int)*CHAR_BIT so that your code doesn't depend on an integer using 32 bits:
```#include
#include
int Cnt_SetBits(unsigned int);

int main()
{
unsigned int inVal;
short unsigned int Value_SetBit;
printf("Please Enter value (between 0 to 4,294,967,295) : ");
scanf("%u",&inVal);
Value_SetBit = Cnt_SetBits(inVal);

printf("\nThe Number has \"%d\" 1's and \"%zu\" 0's",Value_SetBit,sizeof(int)*CHAR_BIT-Value_SetBit);
return 0;
}

```