10.4. Sum and Difference of Population Counts of Two Words

To compute pop(x) + pop(y) (if your computer does not have the population count instruction), some time can be saved by using the first two executable lines of Example 10-1 on x and y separately, and then adding x and y and executing the last three stages of the algorithm on the sum. After the first two lines of Example 10-1 are executed, x and y consist of eight 4-bit fields, each containing a maximum value of 4. Thus x and y may safely be added, because the maximum value in any 4-bit field of the sum would be 8, so no overflow occurs. (In fact, three words may be combined in this way.)

This idea also applies to subtraction. To compute pop(x) – pop(y), use: ^[22]

^[22] y denotes the one's-complement of y, which in C is written ~y.