FJYBioCS 2021-11-06 13:55 采纳率: 100%
浏览 155
已结题

C语言通过位运算实现取模运算

这是一道课后习题,原题如下:

定义函数unsigned mod(unsigned a, unsigned b, unsigned c); 功能是计算并返回ab%c的结果。要求考试a, b, c的范围是大于0且小于 2^31,程序不能使用64位整型(如:long long类型或__int64)求解。
问题:a
b可能溢出(超出32位unsigned int型的表示范围)。为解决此问题,可用如下算法。
设unsigned型变量b的每个二进制位为xi (i=0,1, …, 31),i=0为最低位,i=31为最高位,则

img


上式中,axi的结果或者为a或者为0;
2运算可用左移1位操作实现(小于2^31的整数2结果一定小于2^32, 不会发生溢出);
%c的结果是小于c的,而c小于2^31,它与a求和也不会发生溢出。
编写完整程序,用迭代法实现上述算法。
要求测试b的每个二进制xi位为1或0的操作必须采用位运算实现。
输入提示:"Input unsigned integer numbers a, b, c:\n"
输入格式:"%u %u %u"
输出格式:"%u
%u%%%u=%u\n"

我的代码如下:

#pragma warning(disable:4996)
#include <stdio.h>

unsigned mod(unsigned a, unsigned b, unsigned c) {
    unsigned sum = a * ((b >> 30) & 1);
    for (int i = 29; i >= 0; i--) {
        sum = (sum << 1) % c + a * ((b >> i) & 1);
    }
    return sum % c;
}

int main() {
        //此部分用于实现题目要求
    unsigned a, b, c;
    printf("Input unsigned integer numbers a, b, c:\n");
    scanf("%u %u %u", &a, &b, &c);
    printf("%u*%u%%%u=%u\n", a, b, c, mod(a, b, c));
    
        //此部分用于检验答案是否正确
    unsigned long long ab, bb, cb;
    ab = a;
    bb = b;
    cb = c;
    printf("%llu*%llu%%%llu=%llu", ab, bb, cb, ab * bb % cb);
}

遇到的问题

在处理较小的数据时,一切正常。但当处理较大数据时,如2147483647*2147483647/3,就会得到错误的答案。

另外我是根据题目的公式写的代码,不是很清楚具体原理。

  • 写回答

3条回答 默认 最新

  • CSDN专家-link 2021-11-06 14:07
    关注

    unsigned sum = a * ((b >> 30) & 1);
    改为
    unsigned long long sum = a * ((b >> 30) & 1);

    否则表达式中的 sum << 1 会溢出的

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 11月14日
  • 已采纳回答 11月6日
  • 修改了问题 11月6日
  • 修改了问题 11月6日
  • 展开全部

悬赏问题

  • ¥15 生成的QRCode圖片加上下載按鈕
  • ¥15 板材切割优化算法,数学建模,python,lingo
  • ¥15 科来模拟ARP欺骗困惑求解
  • ¥100 iOS开发关于快捷指令截屏后如何将截屏(或从截屏中提取出的文本)回传给本应用并打开指定页面
  • ¥15 unity连接Sqlserver
  • ¥15 图中这种约束条件lingo该怎么表示出来
  • ¥15 VSCode里的Prettier如何实现等式赋值后的对齐效果?
  • ¥15 流式socket文件传输答疑
  • ¥20 keepalive配置业务服务双机单活的方法。业务服务一定是要双机单活的方式
  • ¥50 关于多次提交POST数据后,无法获取到POST数据参数的问题