title: bit shift multiplication loop
body: <p>I have the following method written:</p>
  
  <pre><code>public static int hash2(String key, int tableSize) {
      int hashVal = 0;
  
      for(int i=0; i&lt;key.length();i++) {
          hashVal = 37 * hashVal + key.charAt(i);
      }
  
      System.out.println(hashVal);
  
      hashVal %= tableSize;   
      if(hashVal &lt; 0){
          hashVal += tableSize;
      }
  
      return hashVal;
  }
  </code></pre>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <pre><code>    for(int i=0; i&lt;key.length();i++) {
          hashVal2 = hashVal2&lt;&lt;19 - hashVal2;
          hashVal2 += key.charAt(i);
      }
  </code></pre>
  
  <p>or</p>
  
  <pre><code>    for(int i=0; i&lt;key.length();i++) {
          hashVal2 = hashVal2&lt;&lt;18 + hashVal2;
          hashVal2 += key.charAt(i);
      }
  </code></pre>
  
  <p>or</p>
  
  <pre><code>    for(int i=0; i&lt;key.length();i++) {
          for(int j=0; j&lt;37;j++) {
              hashVal2 += hashVal2;
          }
          hashVal2 += key.charAt(i);
      }
  </code></pre>
  
  <p>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.</p>