Resource(s) for learning bitwise operation?

Question

I was recently asked a question, "how do you multiply without using the multiplication operator, without any sort of looping statements or explicit addition" and realized I wasn't familiar with bitwise operation at all.

There is obviously wikipedia but I need something with more of an explanation geared toward a newbie. There's also this hack guide but I'm not at the level of grasping it yet.

I don't mind if you point out a chapter in a book, as I have access to a good library through Safari Books and other resources.

Answer 1

Knuth, Volume 2 - Seminumerical Algorithms

Answer 2

The crux of this comes down to a "half adder" and a "full adder". A half adder adds two bits of input to produce a single-bit result, and a single-bit carry. A full adder adds three bits of input (two normal inputs plus a carry from a lower bit) to produce a single-bit result and a single-bit carry.

In any case, the result is based on a truth table for addition. For a half adder, that is: 0+0=0, 0+1=1, 1+0=1, 1+1=0+carry.

So, the "normal" part of the result is the XOR of the inputs. The "carry' part of the result is the AND of the inputs. A full adder is pretty much the same, but left as the infamous "exercise for the reader".

Putting those together, you use a half-adder for the least significant bit, and full adders for the other bits to add N bits of input.

Once you can do addition, there are a couple of ways of doing multiplication. The easy (and slow) way to multiply NxM is to add N to itself M times. The faster (but somewhat more difficult to understand) way is to shift and add. For example, Nx5 = Nx4 + Nx1. You can produce NxB, where B = 2^L by shifting N left by L bits.