Multiplication by Bitshifting [duplicate]

[drcula112]

I have the following method written:\[code\]public static int hash2(String key, int tableSize) { int hashVal = 0; for(int i=0; i<key.length();i++) { hashVal = 37 * hashVal + key.charAt(i); } System.out.println(hashVal); hashVal %= tableSize; if(hashVal < 0){ hashVal += tableSize; } return hashVal;}\[/code\]I have been tasked with rewriting the for loop without using any multiplication or division. My only tools are addition and shifting of 16-bit binary numbers.I realize that I need to somehow multiply hashVal by 37, and then add key.charAt(i) to this value. I have tried that multiple ways:\[code\] for(int i=0; i<key.length();i++) { hashVal2 = hashVal2<<19 - hashVal2; hashVal2 += key.charAt(i); }\[/code\]or\[code\] for(int i=0; i<key.length();i++) { hashVal2 = hashVal2<<18 + hashVal2; hashVal2 += key.charAt(i); }\[/code\]or\[code\] for(int i=0; i<key.length();i++) { for(int j=0; j<37;j++) { hashVal2 += hashVal2; } hashVal2 += key.charAt(i); }\[/code\]But none of these end up returning the same values for hashVal (or hashVal2) as the original method. Am I misunderstanding bit shifting, or is something with the loop the culprit? Not sure what else to try.