How to find out how many bits are set (equal 1) in the product of two integers [closed]

by

The question asks for an algorithm. The problem can be solved without holding a complete product, by computing each bit at a time, starting with bit 0.

Bit C0 is found from the product of A0 * B0 and is either 0 or 1.

Bit C1 is found from the sum of the products A0 * B1 + A1 * B0 and remembering any carry.

Bit C2 is found from the sum of carry + A0 * B2 + A1 * B1 + A2 * B0 and so on.

As you go, you sum the single product bits, which gives the required answer: number of set bits.

More Related Contents:

  1. Mixing two arrays by alternating elements two by two
  2. C++ – Find numbers between first and last negative numbers in Array
  3. Program stopped working, when tried to run
  4. How to replace all occurrences of a character in string?
  5. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  6. Calculating pow(a,b) mod n
  7. Rotating a point about another point (2D)
  8. Create Random Number Sequence with No Repeats
  9. Fast ceiling of an integer division in C / C++
  10. Getting the actual length of a UTF-8 encoded std::string?
  11. Search for a struct item in a vector by member data
  12. Splitting a string by a character
  13. C++ Efficiently Calculating a Running Median [duplicate]
  14. Most efficient/elegant way to clip a number?
  15. The intersection of two sorted arrays
  16. Finding nearest point in an efficient way
  17. sine wave that slowly ramps up frequency from f1 to f2 for a given time
  18. Fast n choose k mod p for large n?
  19. Inverting a 4×4 matrix
  20. Print 2-D Array in clockwise expanding spiral from center
  21. Why would anyone use set instead of unordered_set?
  22. std::back_inserter for a std::set?
  23. How to rotate a N x N matrix by 90 degrees? [closed]
  24. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  25. Why there is no std::copy_if algorithm?
  26. LRU implementation in production code
  27. Is it possible to implement lock free map in C++
  28. priority queue with limited space: looking for a good algorithm
  29. How can I test whether a number is a power of 2?
  30. Checking if all elements of a vector are equal in C++

Leave a Comment