Question

Write a function: def solution(A, 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 an 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. Copyright 2009-2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Answer 1

def solution(A, B):

result = 0

while B > 0:

result += A & 1

A >>= 1

B >>= 1

return result

This solution focuses on correctness.

Some notes:

A & 1 performs a bitwise AND of A and 1. This checks if the least significant bit of A is 1.

A >>= 1 performs arithmetic right shift of A by 1 bit. This divides A by 2.

We continually divide A and B by 2 until B reaches 0.

At each step, we increment result if A & 1 evaluates to 1, meaning the least significant bit of A is 1.

So this counts the number of 1 bits in the binary representation of A * B.

Time complexity: O(log n) since we halve A and B in each iteration of the loop.

Space complexity: O(1)