Tuesday, 19 July 2016

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.

Answer:
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;
 }

No comments: