I'll try to give you an idea of how digital circuits are designed to solve digital processing problems by using the problems you pose: how do CPUs implement additions and multiplications.
Firstly, lets get the direct question out of the way: how does a programming language efficiently evaluate multiplications and additions. The answer is simple, they compile them into multiply and add instructions. For example, the following code:
a = 1 + 1;
b = a * 20;
is simply compiled to something like:
ADD 1 1 a
MUL a 20 b
(note, that the above assembly is for an imaginary CPU that doesn't exist, for simplicity's sake).
At this point you realize that the above answer simply shifts the problem and solve it by hardware magic. The follow-up question is obviously how does that hardware magic work?
Lets look at the simpler problem first: addition.
First we do a familiar problem, adding in regular base 10 numbers:
The first step would be to add 7 and 8. But this results in 15 which is more than a single digit. So we carry the 1:
Now we add 1, 1 and 2 together:
So from this we get the following rules:
when the result of addition is more than one digit, we keep the least significant digit and carry the most significant digit forward
if we have a digit carried forward into our column we add it along with the numbers we're adding
Now it's time to interpret the rules above in base 2 - boolean algebra.
So in boolean algebra, adding 0 and 1 together = 1. Adding 0 and 0 = 0. And adding 1 and 1 = 10 which is more than one digit so we carry the 1 forward.
From this we can construct a truth table:
a b | sum carry
0 0 | 0 0
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1
From this, we can construct two circuits/boolean equations - one for the output of sum and one for the output of carry. The most naive way is to simply list out all the inputs. Any truth table, no matter how big and complex can be restated in this form:
(AND inputs in first row) OR (AND of inputs in second row) OR ...
This is basically the sum of products form. We only look at outputs that result in a 1 and ignore the 0s:
sum = (NOT a AND b) OR (a AND NOT b)
Let's replace the AND OR and NOT with programming language symbols to make that easier to read:
sum = (!a & b) | (a & !b)
Basically, we've converted the table like so:
a b | sum equation
0 0 | 0
0 1 | 1 (!a & b)
1 0 | 1 (a & !b)
1 1 | 0
This can be directly implemented as a circuit:
a ------------| |
\ | AND |-. ____
\ ,-NOT--|_____| \ | |
\/ `--| OR |----- sum
/\ _____ ,--|____|
/ `-NOT--| | /
/ | AND |-`
Observant readers would at this point notice that the above logic can actually be implemented as a single gate - an XOR gate which conveniently has the behavior required by our truth table:
a ------------| |
| XOR |---- sum
But if your hardware doesn't provide you with an XOR gate, the steps above is how you'd go about defining and implementing it in terms of AND, OR and NOT gates.
How you'd go about converting logic gates to actual hardware depends on the hardware you have. They can be implemented using various physical mechanisms as long as the mechanism provides some sort of switching behavior. Logic gates have been implemented with everything from jets of water or puffs of air (fluidics) to transisitors (electronics) to falling marbles. It's a big topic in its own right so I'm going to just gloss it over and say that it's possible to implement logic gates as physical devices.
Now we do the same for the carry signal. Since there is only one condition where the carry signal is true, the equation is simply:
carry = a & b
So carry is simple:
a ------------| |
| AND |---- carry
Combining them together we get what's known as the half adder:
a ------;-----| |
| | XOR |---- sum
| | _____
| '-----| |
| | AND |---- carry
The equations for the above circuit by the way looks like this:
sum = a ^ b
carry = a & b
The half adder is missing something. We've implemented the first rule - if the result is more than one digit than carry forward, but we haven't implemented the second rule - if there is a carry add it together with the numbers.
So to implement a full adder, an adding circuit that can add numbers that are more than one digit, we need to define a truth table:
a b c | sum carry
0 0 0 | 0 0
0 0 1 | 1 0
0 1 0 | 1 0
0 1 1 | 0 1
1 0 0 | 1 0
1 0 1 | 0 1
1 1 0 | 0 1
1 1 1 | 1 1
The equation for sum is now:
sum = (!a & !b & c) | (!a & b & !c) | (a & !b & !c) | (a & b & c)
We can go through the same process to factor out and simplify the equation and interpret it as a circuit etc. as we've done above but I think this answer is getting overly long.
By now you should get an idea of how digital logic is designed. There are other tricks I've not mentioned such as Karnaugh maps (used to simplify truth tables) and logic compilers such as espresso (so that you don't have to factor boolean equations by hand) but the basic is basically what I've outlined above:
Decompose the problem until you can work at single bit (digit) level.
Define the outputs you want using a truth table.
Convert the table to a boolean equation and simplify the equation.
Interpret the equation as logic gates.
Convert your logic circuit to real hardware circuits by implementing logic gates.
That's how fundamental (or rather, low-level) problems are really solved - lots and lots of truth tables. The real creative work is in the breaking down of a complex task such as MP3 decoding to bit level so that you can work on it with truth tables.
Sorry I don't have the time to explain how to implement multiplication. You can try taking a crack at it by figuring out rules of how long multiplication works then interpreting it in binary then try to break it down to truth tables. Or you can read Wikipedia: http://en.wikipedia.org/wiki/Binary_multiplier