Thursday, August 12, 2010

Multiplying without the * key

I got asked, once, how to multiply two numbers without the '*' key on my keyboard working. My first reaction was "get a new keyboard" but apparently that didn't cut it in this hyper theoretical situation. Hence I came up with the following Java solution using BigIntegers

private static BigInteger shiftMultiply(final BigInteger a, final BigInteger b) {

BigInteger bBuff = new BigInteger(b.toString());

//now for the real calculation
BigInteger product = BigInteger.ZERO;
//for(int i = 0; i < requiredBitSize(b); i++) {
int bShift = 0;
while(bBuff.compareTo(BigInteger.ZERO) > 0)
{
if( bBuff.and(BigInteger.ONE).compareTo(BigInteger.ZERO) != 0) {
BigInteger aBuff = new BigInteger(a.toString());
int aShift = 0;
while(aBuff.compareTo(BigInteger.ZERO) > 0)
{
if( aBuff.and(BigInteger.ONE).compareTo(BigInteger.ZERO) != 0 ){
//product += bitMasks[bMaskPos + aMaskPos];
product = product.add(BigInteger.ONE.shiftLeft(bShift + aShift));
}

aBuff = aBuff.shiftRight(1);
aShift++;
}
}
bBuff = bBuff.shiftRight(1);
bShift++;
}