solution C Puzzle 8

solution C Puzzle #8

it has a fixed number of iterations,
since i goes from 0 to 4, and shift goes through the sequence 1, 2, 4,
8, and 16, regardless of the input. So the calculation has five fixed
stages, which have been rolled up into a loop for brevity. These five
stages limit it to counting up to 32 bits (2 to the power of 5). At
each stage, the following is evaluated:

x = (x & mask[i]) + ((x >> shift) & mask[i]);

The initial input value x is the word whose bits are to be counted,
and the output of each stage is fed as input to the next stage. I.e.
each stage does this:

x = F_i(x)

Where F_i is a function of x specific to stage i. Each F_i is
characterized by choice of mask and shift value. So the five stages
are basically:

count = F_4(F_3(F_2(F_1(F_0(x)))))

the chained application of five functions. Based on this, you should
be able to draw these stages as one big flow diagram (even down to the
detail of a combinatorial circuit).

Start with the abstracted version.

x ---- F_0 -- F_1 -- F_2 -- F_3 -- F_4 ----- count

Now zoom in on the F's and draw out how they work. What is F_0? It is
this:

F_0(x) = x & mask_0 + (x >> shift_0) & mask_0

where mask_0 is 0x55555555 and shift_0 is 1. So in other words:

F_0(x) = x & 0x55555555 + (x >> 1) & 0x55555555;

At the bit level, 0x33333333 is the bit pattern 0101010101010101. What
is going on in this expression? The left side of the + selects all of
the even bits in the input word x. The right side, selects all of the
odd bits, but shifts them one position to the right. Let's give letter
names to the 32 bits, using upper case for the lower 16:

let x = abcd efgh ijkl mnop ABCD EFGH IJKL MNOP

What is x & 01010101010101010101010101010101? To make it clearer,
let's use the underscore character to represent zero. When we bitwise-
and x with the 0x5555... bit pattern, we get:

_b_d _f_h _j_l _n_p _B_D _F_H _J_L _N_P

What about the right side? If we shift x one bit to the right, we get:

_abc defg hijk lmno pABC DEFG HIJK LMNO

The P bit falls off, and a zero is shifted in. What happens when we
and this with 0x5555...?

_a_c _e_g _i_k _m_o _A_C _E_G _I_K _M_O

And now these two quantities are added together, like this:

_b_d _f_h _j_l _n_p _B_D _F_H _J_L _N_P
+ _a_c _e_g _i_k _m_o _A_C _E_G _I_K _M_O

Note how there are zeros in every other column. These zeros mean that
there is no carry in the addition. For instance if adding P and O in
the least significant bit column produces a carry bit, that carry bit
will add to the two zeros in the second column. There will be no
further carry into the third column. So essentially, this addition is
really 16 independent additions withiin the 32 bit word, namely

_b _d _f
+ _a + _c +_e .... and so on

Do you see what is going on? The bits are being added together
pairwise to produce 16 partial results of two bits each:

bits 30 and 31: (a + b)
bits 28 and 29: (c + d)
bits 26 and 27: (e + f)

and so on.

In the next stage, the same pattern is repeated, but it's widened to a
two bit addition producing a four bit result. The masking pattern is
0x3333 which is 001100110011, and the shift is two. It pairs the two
bit groups together and adds them.

bits 28-31: ((a + b) + (c + d))
bits 24-27: ((e + f) + (g + h))

Ultimately, this process will yield the sum:

a + b + c + d + e + ... + p + A + B + ... + P

And this sum is, of course, the number of bits in the original word,
since each letter represents a bit, 0 or 1. The algorithm exploits the
ability of the machine to manipulate word quantities in order to
partially parallelize this addition.

That's approximately how you understand something. The level of detail
you have to go in drawing it out depends on your experience and mental
power. Someone very intelligent or experienced or both will recognize
the pattern instantly and just see what is going on without having to
write out the process.


Answer by my friend:

I'll try to demonstrate how to try this out yourself with a calculator.

Suppose we want to add 2347 to 1276, and at the same time add 8975 to 6532.
You can only use the '+' key one time, (and the '=' key once at the end).

You may want to try this out for yourself before reading on.




What you do is the following:

You type: aaaa0bbbb + cccc0dddd =

So, in our case, you type 234708975 + 127606532 =

The calculator responds with: 362315507.
You may note that 2347+1276=3623, and 8975+6532=15507.

The same trick can be done to add 4 1-digit numbers in one go:
You type a0b0c0d + e0f0g0h =

For example: 4020607 + 2070409 = 6091016. 4+2=6, 2+7=9, 6+4=10, 7+9=16


Now, to apply this trick to the problem of adding all digits in a number:

Suppose we want to know the sum of all digits in a number.
Let's take 97234923 as a random example.

First, we split it into two groups, masking out the even digits in one
group, and the odd digits in the other:

90204020 and 07030904

Then, shift the digits on the left side, and add the two numbers:

9020402 + 7030904 = 16051306 (9+7=16, 2+3=5, 4+9=13, 2+4=6)

Now, we have four two-digit numbers that we want to add, so we separate
again:

16001300 and 00050006

Shift the digits on the left side, and add the numbers:

160013 + 050006 = 210019 (16+5=21, 13+6=19)

And again:

210000 and 000019

becomes:
21 + 19 = 40

And there we have the total sum of the digits.


You can do the same trick with multiplication, but you have
to leave more room inbetween the digits:

Suppose you have four digits, a b c and d.
If you calculate a0b * c000d, the result will be:
ffgghhii, where ff = a*c, gg=b*c, hh=a*d and ii=b*d.
So that's four multiplications in a single go.