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++;
}

1 comment:

Vengeanz said...

I was also asked to in place swap to integers, which I'd do in the following way.

private static void InPlaceSwapInteger(BigInteger a, BigInteger b) {

System.out.println(String.format("a:= %d, b:= %d ", a, b));

b = (a = a.xor(b)).xor(b);
a = a.xor(b);

System.out.println(String.format("a:= %d, b:= %d ", a, b));
}