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

l7wslrjt 于 12个月前发布在其他

关注(0)|答案(2)|浏览(160)

在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溢出。）
例如，以下代码实现了函数，但它不是溢出安全的：

long r = x % y;
if ((x ^ y) < 0 && r != 0) {
      return r + y;
}

return r;

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

c++

来源：https://stackoverflow.com/questions/77742932/implement-modulus-operator-as-a-function-implementation-that-is-overflow-safe

2条答案

按热度按时间

wlp8pajw1#

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

static inline long safe_modulus_long(long x, long y) {
    if (y == 0) {
        // division by zero: return a 0 modulus
        return 0;
    }
    if (x == LONG_MIN && y == -1) {
        // division overflow: the modulus is actually 0
        return 0;
    }
    long r = x % y;
    if (r < 0) {
        if (y > 0)
            r = y + r;
        else
            r = -(y - r);
    }
    return r;
}

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

static inline long long safe_modulus_llong(long long x, long long y) {
    [...] // same implementation as above using LLONG_MIN
}

static inline int safe_modulus_int(int x, int y) {
    [...] // same implementation as above using INT_MIN
}

static inline unsigned long long safe_modulus_ullong(unsigned long long x, unsigned long long y) {
    return y ? x % y : 0;
}

static inline unsigned long safe_modulus_ulong(unsigned long x, unsigned long y) {
    return y ? x % y : 0;
}

static inline unsigned int safe_modulus_long(unsigned int x, unsigned int y) {
    return y ? x % y : 0;
}

#define SAFE_MUDULUS(x, y)  _Generic((x) % (y),        \
    unsigned long long int: safe_modulus_ullong(x, y), \
    long long int:          safe_modulus_llong(x, y),  \
    unsigned long int:      safe_modulus_ulong(x, y),  \
    long int:               safe_modulus_long(x, y),   \
    unsigned int:           safe_modulus_uint(x, y),   \
    int:                    safe_modulus_int(x, y))

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

static inline long long safe_modulus(long long x, long long y) {
    if (y == 0) {
        // division by zero: return a 0 modulus
        return 0;
    }
    if (x == LLONG_MIN && y == -1) {
        // division overflow: the modulus is actually 0
        return 0;
    }
    long long r = x % y;
    if (r < 0) {
        if (y > 0)
            r = y + r;
        else
            r = -(y - r);
    }
    return r;
}

static inline long safe_modulus(long x, long y) {
    if (y == 0) {
        // division by zero: return a 0 modulus
        return 0;
    }
    if (x == LONG_MIN && y == -1) {
        // division overflow: the modulus is actually 0
        return 0;
    }
    long r = x % y;
    if (r < 0) {
        if (y > 0)
            r = y + r;
        else
            r = -(y - r);
    }
    return r;
}

static inline int safe_modulus(int x, int y) {
    if (y == 0) {
        // division by zero: return a 0 modulus
        return 0;
    }
    if (x == INT_MIN && y == -1) {
        // division overflow: the modulus is actually 0
        return 0;
    }
    int r = x % y;
    if (r < 0) {
        if (y > 0)
            r = y + r;
        else
            r = -(y - r);
    }
    return r;
}

static inline unsigned long long safe_modulus(unsigned long long x, unsigned long long y) {
    return y ? x % y : 0;
}

static inline unsigned long safe_modulus(unsigned long x, unsigned long y) {
    return y ? x % y : 0;
}

static inline unsigned int safe_modulus(unsigned int x, unsigned int y) {
    return y ? x % y : 0;
}

型

赞(0）回复(0）举报 12个月前

vkc1a9a22#

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

long safe_mod(long x, long y)
{
    if (x == LONG_MIN && y == -1) {
        return 0;
    } else if (x > LONG_MIN && x < 0 && y == LONG_MIN) {
        return -x;
    } else {
        long r = x % y;
        if ((x ^ y) < 0 && r != 0) {
            return r + y;
        }
        return r;
}

字符串

赞(0）回复(0）举报 12个月前

我来回答

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

2条答案

相关问题

热门标签

最新问答