7 Replies - 903 Views - Last Post: 15 June 2019 - 02:25 PM

#1 livium   User is offline

  • D.I.C Addict

Reputation: 0
  • View blog
  • Posts: 551
  • Joined: 21-December 08

Number of 1s in a multiplication

Posted 14 June 2019 - 01:38 PM

I know how to find the nimber of 1s of the binary representation of a number. But I saw an interview question asking the number of 1s of AxB. Why do they ask this? You just multiply the numbers and then find out the 1s of the resulting number. Is there a catch?

This post has been edited by livium: 14 June 2019 - 01:39 PM

Is This A Good Question/Topic? 0
  • +

Replies To: Number of 1s in a multiplication

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6968
  • View blog
  • Posts: 23,683
  • Joined: 05-May 12

Re: Number of 1s in a multiplication

Posted 14 June 2019 - 04:07 PM

It's actually an interview question targeted for people who are more into assembly, or very low level C -- low level as in bit twiddling level C coding.

Most C programmers would simply do the multiplication and count the number of bits in the result.

On the other hand, very low level programmer will at one point or another have read and taken to heart (and memory) Hacker's Delight which has many tricks for figuring out stuff like this. An alternate source of information would be Bit Twiddling Hacks
Was This Post Helpful? 2
  • +
  • -

#3 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6968
  • View blog
  • Posts: 23,683
  • Joined: 05-May 12

Re: Number of 1s in a multiplication

Posted 14 June 2019 - 04:49 PM

As a trivial example, if A or B is simply a power of 2, then the number of 1's is the number of 1's in the other number (assuming that overflow doesn't happen). This is because when multiplying by a power of 2, the bits just get shifted so you don't have to worry about any of the bits flipping because you won't have any intermediate additions.
Was This Post Helpful? 1
  • +
  • -

#4 livium   User is offline

  • D.I.C Addict

Reputation: 0
  • View blog
  • Posts: 551
  • Joined: 21-December 08

Re: Number of 1s in a multiplication

Posted 14 June 2019 - 10:14 PM

Thank you. But what if one of the numbers is not a power of 2?
So there is no easy solve to this problem.
I'll have to study whole books for this interview question...

This post has been edited by livium: 14 June 2019 - 10:15 PM

Was This Post Helpful? 0
  • +
  • -

#5 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6968
  • View blog
  • Posts: 23,683
  • Joined: 05-May 12

Re: Number of 1s in a multiplication

Posted 15 June 2019 - 06:24 AM

I suspect that the question is not meant to see if you can come up with an exact mathematical answer, but to see if you understand how binary multiplication works and see how you think about breaking down the problem. Good technical interview questions probe at analysis, problem solving, communication, and general breadth of knowledge. They don't assume depth of knowledge (unless the job listing specifically asked for it and the candidate listed it on their resume).
Was This Post Helpful? 1
  • +
  • -

#6 livium   User is offline

  • D.I.C Addict

Reputation: 0
  • View blog
  • Posts: 551
  • Joined: 21-December 08

Re: Number of 1s in a multiplication

Posted 15 June 2019 - 12:46 PM

It is actually a coding test and one needs to solve the problem by writing code. It is not about talking.
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6968
  • View blog
  • Posts: 23,683
  • Joined: 05-May 12

Re: Number of 1s in a multiplication

Posted 15 June 2019 - 01:02 PM

As a coding test, the most efficient solution is just multiply and count the bits of the product. Anything else will require you to count the bits of the multiplier and multiplicand. That will take more code and time for very little gain.
Was This Post Helpful? 1
  • +
  • -

#8 livium   User is offline

  • D.I.C Addict

Reputation: 0
  • View blog
  • Posts: 551
  • Joined: 21-December 08

Re: Number of 1s in a multiplication

Posted 15 June 2019 - 02:25 PM

Thank you !!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1