共计 394 个字符,预计需要花费 1 分钟才能阅读完成。
明天在 leetcode 刷到一题:
https://leetcode-cn.com/probl…
要求计算 1 到 n 的和,不能用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句(A?B:C)。
这题有个很好的做法,即应用俄罗斯农民乘法,尽管这里因为不能用循环所以只能手动开展,然而俄罗斯农民乘法的思维是值得借鉴的。
俄罗斯农民乘法
有两个数 A 和 B 相乘,如果两个数十分大,乘积可能溢出,那么咱们能够将 B 二进制开展,枚举 B 的每一位,如果第 i 位是 1,那么和 A 相乘后果应该是 A * (1 << i) 也就是 A << i, 只有在每次运算的时候取模,最初后果再取模,就能够防止数值越界。
public static int quickMul(int a, int b){
int ans = 0;
while (b > 0){if((b & 1) == 1){ans += a;}
a <<= 1;
b >>= 1;
}
return ans;
}
正文完