**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

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:

Post a Comment