c++ 将取模运算符实现为溢出安全函数实现

l7wslrjt  于 2024-01-09  发布在  其他
关注(0)|答案(2)|浏览(179)

在C中，%运算符是一个余数运算符（a % b产生 a − trunc（a/B）·B），但我想实现一个模运算符（a − floor（a/B）·B），它是溢出安全的。
特别是，mod(LONG_MIN, -1)应该有定义的行为并产生0。（对于二进制补码，C标准没有定义LONG_MIN % -1，因为它是通过引用除法定义的，LONG_MIN / −1溢出。）
例如，以下代码实现了函数，但它不是溢出安全的：

  1. long r = x % y;
  2. if ((x ^ y) < 0 && r != 0) {
  3.       return r + y;
  4. }
  6. return r;

字符串
在C++中有没有一种有效的方法来实现这一点，而不需要特殊的溢出检查？或者只有在方法的开头添加一个溢出检查才能做到这一点？

c++

2条答案

按热度按时间
wlp8pajw

wlp8pajw1#

当余数为负时，您所需要的就是（小心地）加上商值y。
以下是C11解决方案：

  1. static inline long safe_modulus_long(long x, long y) {
  2.     if (y == 0) {
  3.         // division by zero: return a 0 modulus
  4.         return 0;
  5.     }
  6.     if (x == LONG_MIN && y == -1) {
  7.         // division overflow: the modulus is actually 0
  8.         return 0;
  9.     }
  10.     long r = x % y;
  11.     if (r < 0) {
  12.         if (y > 0)
  13.             r = y + r;
  14.         else
  15.             r = -(y - r);
  16.     }
  17.     return r;
  18. }

字符串
您可以使用其他类型特定的函数和泛型宏来支持所有标准整型：

  1. static inline long long safe_modulus_llong(long long x, long long y) {
  2.     [...] // same implementation as above using LLONG_MIN
  3. }
  5. static inline int safe_modulus_int(int x, int y) {
  6.     [...] // same implementation as above using INT_MIN
  7. }
  9. static inline unsigned long long safe_modulus_ullong(unsigned long long x, unsigned long long y) {
  10.     return y ? x % y : 0;
  11. }
  13. static inline unsigned long safe_modulus_ulong(unsigned long x, unsigned long y) {
  14.     return y ? x % y : 0;
  15. }
  17. static inline unsigned int safe_modulus_long(unsigned int x, unsigned int y) {
  18.     return y ? x % y : 0;
  19. }
  21. #define SAFE_MUDULUS(x, y)  _Generic((x) % (y),        \
  22.     unsigned long long int: safe_modulus_ullong(x, y), \
  23.     long long int:          safe_modulus_llong(x, y),  \
  24.     unsigned long int:      safe_modulus_ulong(x, y),  \
  25.     long int:               safe_modulus_long(x, y),   \
  26.     unsigned int:           safe_modulus_uint(x, y),   \
  27.     int:                    safe_modulus_int(x, y))

型
对于C++，你可以使用重载来实现所有整型的safe_modulus：

  1. static inline long long safe_modulus(long long x, long long y) {
  2.     if (y == 0) {
  3.         // division by zero: return a 0 modulus
  4.         return 0;
  5.     }
  6.     if (x == LLONG_MIN && y == -1) {
  7.         // division overflow: the modulus is actually 0
  8.         return 0;
  9.     }
  10.     long long r = x % y;
  11.     if (r < 0) {
  12.         if (y > 0)
  13.             r = y + r;
  14.         else
  15.             r = -(y - r);
  16.     }
  17.     return r;
  18. }
  20. static inline long safe_modulus(long x, long y) {
  21.     if (y == 0) {
  22.         // division by zero: return a 0 modulus
  23.         return 0;
  24.     }
  25.     if (x == LONG_MIN && y == -1) {
  26.         // division overflow: the modulus is actually 0
  27.         return 0;
  28.     }
  29.     long r = x % y;
  30.     if (r < 0) {
  31.         if (y > 0)
  32.             r = y + r;
  33.         else
  34.             r = -(y - r);
  35.     }
  36.     return r;
  37. }
  39. static inline int safe_modulus(int x, int y) {
  40.     if (y == 0) {
  41.         // division by zero: return a 0 modulus
  42.         return 0;
  43.     }
  44.     if (x == INT_MIN && y == -1) {
  45.         // division overflow: the modulus is actually 0
  46.         return 0;
  47.     }
  48.     int r = x % y;
  49.     if (r < 0) {
  50.         if (y > 0)
  51.             r = y + r;
  52.         else
  53.             r = -(y - r);
  54.     }
  55.     return r;
  56. }
  58. static inline unsigned long long safe_modulus(unsigned long long x, unsigned long long y) {
  59.     return y ? x % y : 0;
  60. }
  62. static inline unsigned long safe_modulus(unsigned long x, unsigned long y) {
  63.     return y ? x % y : 0;
  64. }
  66. static inline unsigned int safe_modulus(unsigned int x, unsigned int y) {
  67.     return y ? x % y : 0;
  68. }

型

展开查看全部
赞(0）分享  回复(0）举报  2024-01-09
vkc1a9a2

vkc1a9a22#

只需为边界情况添加额外的检查：

  1. long safe_mod(long x, long y)
  2. {
  3.     if (x == LONG_MIN && y == -1) {
  4.         return 0;
  5.     } else if (x > LONG_MIN && x < 0 && y == LONG_MIN) {
  6.         return -x;
  7.     } else {
  8.         long r = x % y;
  9.         if ((x ^ y) < 0 && r != 0) {
  10.             return r + y;
  11.         }
  12.         return r;
  13. }

字符串

赞(0）分享  回复(0）举报  2024-01-09
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com