java - 位移乘法循环

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⁰

最后，对于所有 i，x * 2ⁱ == (x << i) 。因此，要将 x 乘以 37，您可以计算

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

练习的其余部分应该相当简单。