无符号乘积的模

定义函数unsigned mod(unsigned a, unsigned b, unsigned c); 功能是计算并返回a*b%c的结果。要求考试a, b, c的范围是大于0且小于 231，程序不能使用64位整型(如：long long类型或__int64)求解。

问题：a*b可能溢出（超出32位unsigned int型的表示范围）。为解决此问题，可用如下算法。 

设unsigned型变量b的每个二进制位为xi (i=0,1, …, 31)，i=0为最低位，i=31为最高位，则, 所以

上式中，a*xi的结果或者为a或者为0；

*2运算可用左移1位操作实现（小于231的整数*2结果一定小于232, 不会发生溢出）；

%c的结果是小于c的，而c小于231，它与a求和也不会发生溢出。

编写完整程序，用迭代法实现上述算法。

要求测试b的每个二进制xi位为1或0的操作必须采用位运算实现。

输入提示："Input unsigned integer numbers a, b, c:\n"

输入格式："%u%u%u"

输出格式："%u*%u%%%u=%u\n"

代码如下

#include 

unsigned mod(unsigned a, unsigned b, unsigned c);

int main(void)
{
	unsigned int a, b, c;
	int sum;
	scanf("%u %u %u", &a, &b, &c);
	sum = mod(a, b, c);
	printf("%u*%u%%%u = %u",a,b,c,sum);

	return 0;
}

unsigned mod(unsigned a, unsigned b, unsigned c)
{
	unsigned int sum, mask = 1u << 31, xi;
	sum = ((a * ((b & mask) >> 31)) >> 1) % c;
	int i;
	for (i = 30, mask = 1u << 30; i >= 0; i--, mask >>= 1) {
		xi = a * ((b & mask) >> i);
		if (i == 0) {
			sum = ((sum + xi)) % c;
			break;
		}
		sum = ((sum + xi) << 1) % c;
	}
	return sum;
}