Thread: Bit wise oeperators adition , subtraction , division and multiplication

Originally Posted by nkrao123@gmail.

without by heart is there any easy systematic way to do all those things?

Sure, it's the same as learning multiplication normally: if you can understand how (and why) multiplication works, it's easier than memorizing a table. And/or it makes memorizing the table easier.

So you found the algorithm:

Code:

int product (int a, int b) {
	unsigned int x, y, product = 0;
	int sign = 1;

	if (a < 0) {
		sign *= -1;
		x = -a;
	} else x = a;
	if (b < 0) {
		sign *= -1;
		y = -b;
	} else y = b;

	while (y > 0) {
		if (y & 1) product += x;
		x <<= 1;
		y >>= 1;
	}

	return sign*product;
}

Th purpose of the preliminary bit with setting sign is because signed integers use the highest bit to indicate negativity. If you shift a signed integer value around, its signedness will be affected. We need to use unsigned numbers which are pure power of 2 bit values, but we also need to restore the signedness of the product at the end. So if one but not both of the factors are negative, sign will be -1. Pretty simple.

Now to the real question: how does the part in red work?

Let's use 10 * 10, which takes 4 passes thru the loop, as an example. Ten in binary is 1010. Every time you shift left, you are multiplying by 2. Everytime you shift right, you are dividing by two (and rounding down, because the Least Significant Bit = 1 and it is shifted off).

On the first pass, y & 1 == false, so "product" is still 0, y is shifted right to become 5, and x is shifted left to become 20.

On the second pass, y & 1 == true, so product becomes 20, y becomes 2, and x becomes 40.

On the third pass, y & 1 == false, so product remains 20, y becomes 1, and x becomes 80.

On the fourth pass, y & 1 == true, so product becomes 100, y becomes 0, and x becomes 160.

That's how, but it doesn't explain why this "duplicates" what we think of as multiplication. But remember, shifting left is multiplication, by two, aka squaring or raising to the power of 2. "y & 1" just tests to see if the lowest bit in y is set. What that function does is take every bit set in y and add the corresponding power of 2 value of x. If the first bit is set, we add just x. If the second bit is set, we add x^2. If the third bit is set, we add x^4.

I would never have thought that algorithm up myself and my mathematical vocabulary is limited, so my explanation might be incomplete, but hopefully that still sheds some light.