1

I found this problem in a test and could not solve it: given two arbitrary numbers, how can the number of 1 bits in the binary representation of their product be computed without computing the product itself? The asymptotic complexity of the solution must be O(log(A+B)), where A and B are the given factors.

For example, if A and B are 3 and 7 then the product is 21. The binary representation of 21 is 10101, which has three 1 bits, so the answer is 3.

Can anyone suggest how to do this?

John Bollinger
  • 160,171
  • 8
  • 81
  • 157
late_riser
  • 133
  • 10
  • possible duplicate of [How to count the number of set bits in a 32-bit integer?](http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer) – John Bollinger Nov 25 '14 at 17:28
  • @JohnBollinger definitely not – harold Nov 25 '14 at 17:30
  • @harold how not? You compute the product, and you count the bits set in it. The bit counting can be done in constant time and space for a given data type, which is even better than the requested complexity bound. – John Bollinger Nov 25 '14 at 17:35
  • 1
    @JohnBollinger if that was the answer, OP would already know it. Also the data type can't be constant-length, otherwise the whole problem doesn't exist in the first place. – harold Nov 25 '14 at 17:37
  • @John Bollinger: Pls see the EDIT. – late_riser Nov 26 '14 at 03:09
  • How can I delete the unwanted line "This question may already have an answer here:" someone added in the first place of my question? – late_riser Nov 26 '14 at 03:13

2 Answers2

0

I was asked the same question in an interview, and this is what I have submitted and all the testcases were passed. I hope this is the solution you are looking for. The complexity of built-in function bin(n) is O(log(n)) and that of count() function is O(n) This code is in Python3:

    def checkBinSet(a, b):
        output = a*b
        if output == 0:   # when the product is 0 just return 0
            return 0
        else:   
            binResult = bin(output)[2:]  # in this case bin(n) returns output as '0b10101', remove the 0b from the output using [2:], you will get the binary bits only '10101'
            return binResult.count("1")  # looking for the count of 1s in the binResult. You can also replace the count() function using loop and then count the number of 1s and increase the counter
    result = checkBinSet(3,7)
    print(result)    # output is 3
Farhat Jahan
  • 13
  • 6
0

I countered this question in an interview. Here let me share my solution and it passed the test case in codility.

    public int solution(int a, int b) {
        int count =0;
        int c =0;
        while (a > 0 || c>0) {
            int temp = (a % 2)*b+c;
            if(temp %2 ==1) count++;
            c = temp >>1;
            a = a >> 1;
        }
        System.out.println(" one count is "+count);
        return count;
    }
jason zhai
  • 96
  • 2
  • 3