Bitwise Multiplication

This is just a small way to perform multiplication in Java that is close to what your computer actually does. Since computers can only understand 0 (off) and 1 (on), computer scientists had to develop smart ways to perform calculations.

Computers can only add numbers without performing tricks, so for fun I tried to program methods for multiplying, dividing, modulus and calculating square root. The results were slow to run methods. By using bitwise operators I was able to perform the calculations significantly faster.

Let's take a look at this method for performing bitwise multiplication in Java (keeping it simple not using decimal numbers):

Now examining the code we'll start at the first if statement as the while statement is self explanatory. By writing "if ((b & 1) != 0)" the computer will convert 'b' to a binary number and check the first bit if it's 0 or 1 (all odd numbers will be 1). So everyone loop where 'b' is an odd number the if statement will return true and we'll add the current number in 'a' to our result.

Next we have 2 statements outside the loop "a <<= 1;" and "b>>= 1;". These two statements convert our numbers to binary and then shift them 1 place to the left or right. Essentially this will double the number on a left shift and halve the number on a right shift. It's important to note that if a number halved gives a decimal result such as 5 / 2 = 2.5, the computer will then round that number down to 2.

A good way to see how the program works is by printing out the variables involved each loop. Let's examine the state of the variables multiplying 5 * 5:

Result: 5
Variable A: 10
Variable B: 2

---------------Next Loop------------

Result: 5
Variable A: 20
Variable B: 1

---------------Next Loop------------

Result: 25
Variable A: 40
Variable B: 0

---------------Next Loop------------


5 is added to the result the first loop because we check binary 5 (1001) for a starting 1 bit. The variable 'a' is then doubled and 'b' halved (rounded down to 2).

Next loop the result stays the same because we check binary 2 (0010) for a starting 1 bit (it fails the if statement). Once again the other variables are doubled and halved. The 3rd loop 'b' is an odd number again '0001' in binary meanining we add 'a' to result again giving us the final result.

The loop now ends since 'b' has now hit 0.

We could have just looped adding 5 every loop and decrementing 'b' until it hits 0 but this would be very ineffective and with large calculations take a long time to find the answer. The method using bitwise operators will perform almost any size calculation very quickly since we're doubling the number with every loop.

Thanks for your time and feel free to comment. Duane