位移乘法迴路

Question

我有以下方法寫入：

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

我一直負責重寫for循環，而無需使用任何乘法或除法。我唯一的工具是添加和移位16位二進制數字。

我意識到我需要以某種方式將hashVal乘以37，然後將key.charAt（i）添加到此值。我已嘗試多種方法：

for(int i=0; i<key.length();i++) { 
     hashVal2 = hashVal2<<19 - hashVal2; 
     hashVal2 += key.charAt(i); 
    } 

或

for(int i=0; i<key.length();i++) { 
     hashVal2 = hashVal2<<18 + hashVal2; 
     hashVal2 += key.charAt(i); 
    } 

或

for(int i=0; i<key.length();i++) { 
     for(int j=0; j<37;j++) { 
      hashVal2 += hashVal2; 
     } 
     hashVal2 += key.charAt(i); 
    } 

但所有這些最終成爲原始方法返回的hashVal（或hashVal2）相同的值。我誤解了位移，還是與循環的罪魁禍首？不知道還有什麼要嘗試。

Answer 1

37乘以相同加入2某些權力：

x * 37 == x * (32 + 4 + 1) 

這告訴你如何移位，因爲：

32 == 2
4 = = 2
1 == 2

最後，x * 2 ⁱ ==（x < < i）對於所有的i。所以要乘以37，你可以計算

(x << 5) + (x << 2) + (x) 

其餘的練習應該是相當簡單的。

Answer 2

左移1位將使數字乘以2. 所以乘以37將37轉換爲二進制。這將是100101

Number * 2^5 + Number * 2^2 + Number * 2^0 
Number << 5 + Number << 2 + Number 

For循環應該是這樣的：

for(int i=0; i<key.length();i++) { 
    hashVal = (hashVal << 5) + (hashVal << 2) + hashVal + key.charAt(i); 
}