问题描述
小艾是产自中国的一个移位寄存器，他最近很苦恼，他和他的同事吵架了，他们无法合作导致无法完成乘法操作，因为他自己只会通过移位完成乘2的乘法和除以2的除法，所以他无法完成复杂乘法。小艾的女朋友又比较笨，死活学不会乘法，小艾的女朋友不愿看他继续消沉下去，决定和小艾来一次说走就走的旅行，他们选择去俄罗斯看冰雪大世界，旅途中，小艾依然心不在焉，一位俄罗斯农民伯伯看出小艾有心事，便自动和小艾聊起了天，得知小艾是因为这点小事苦恼，农民伯伯说他有办法帮助小艾重回巅峰，小艾顿时来了精神，赶忙向农民伯伯请教。农民伯伯点起一支烟，眯着眼睛开始讲解……谁说完成乘法一定要复杂的操作，你和你女朋友就可以完成了，小艾存一个数n，你女朋友存一个数m，如果小艾存的是偶数，则小艾右移一位（除2），你女朋友左移一位（乘2），如果小艾存的是奇数，则小艾先减一再右移一位，将你女朋友保存的值传给累加器兄弟，然后你女朋友左移一位（乘2）。一直重复上述过程，直到小艾等于0。此时累加器中的值就是乘法的结果。
算法描述
举例
算法分析
在整个计算的过程中都是乘以2和除以2的操作，这种操作在计算机中可以直接使用移位计算，效率非常高。因此，这个算法对计算机的整数计算是很有实际意义的！
算法用途
1、用在大数相乘取模的情况，可以防止大数相乘溢出。
2、当我们使用int类型做快速乘运算时就相当于模2^32（假设 int类型是 4位）。
代码实现
// C++ int russian_peasant_multiplication(int n, int m) { int ans = 0;// 保存乘法结果 while (n > 0) { if (n & 1) {// 判断奇偶 ans += m; } n >>= 1;// n除以2 m <<= 1;// m乘以2 } return ans;// 返回乘法结果 }
————————————————
版权声明：本文为CSDN博主「Acx7」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
