C语言中long long型向零取整三除法的合规计算方法
带溢出安全的 long long 求和除以3(向零取整)实现
我们的实现严格遵循给定约束:所有操作基于C标准明确定义的行为,不触发未定义效应,禁用unsigned long long类型与更宽的数值类型,最终结果等价于数学上计算(x + y + z)/3后向零取整,其中x、y为long long类型,z为int类型。
直接写法的核心问题
如果直接编写(x + y + z)/3作为返回值,存在两个不符合要求的缺陷:
- 带符号
long long的加法溢出属于C标准定义的未定义行为,当x+y超出long long取值范围时,结果没有明确定义 - C99及后续标准已明确规定整数除法的商为向零取整,与题目要求的
trunc行为完全一致,因此只要保证加法过程无溢出,除法逻辑本身是符合要求的
实现思路
- 无溢出的溢出判断:利用带符号整数加法的固有特性做安全比较
- 当两个数符号相反,或其中一个数为0时,相加结果永远不会超出
long long范围,可直接运算 - 当两个正数相加时,仅当
x > LLONG_MAX - y时会发生溢出(该比较过程本身无溢出,完全安全) - 当两个负数相加时,仅当
x < LLONG_MIN - y时会发生溢出(该比较过程本身无溢出,完全安全)
- 当两个数符号相反,或其中一个数为0时,相加结果永远不会超出
- 溢出场景的拆分计算
- 两个正数相加溢出时,真实和可拆分为固定边界值
2^63与一个范围内的偏移值,预先把2^63拆为3的整数倍加余数,避免直接计算2^63引发的溢出 - 两个负数相加溢出时,真实和可拆分为固定边界值
LLONG_MIN与一个范围内的偏移值,同样预先拆分LLONG_MIN的3倍商与余数
- 两个正数相加溢出时,真实和可拆分为固定边界值
- 最小化中间值存储:由于最终需要除以3,不需要保存完整的和,仅需累加两部分值即可:
- 已经是3的倍数的商部分
- 剩余的绝对值不超过
int范围的余数部分,最后将余数与z相加后做一次安全的除以3操作
完整实现代码
#include <limits.h> // 基于64位long long边界预计算的固定拆分值 // 2^63 = 3 * Q_POS + R_POS,其中R_POS为余数 #define Q_POS 3074457345618258602LL #define R_POS 2LL // LLONG_MIN(-2^63) = 3 * Q_NEG + R_NEG,其中R_NEG为余数 #define Q_NEG (-3074457345618258603LL) #define R_NEG 1LL long long trunc_div3(long long x, long long y, int z) { long long q_s1 = 0; long long r_s1 = 0; if (x > 0 && y > 0) { // 两个正数,判断是否溢出 if (x > LLONG_MAX - y) { // 正溢出场景:真实和 = 2^63 + t long long t = x - (LLONG_MAX - y) - 1; q_s1 = Q_POS; // 单独处理rem溢出的边界值 if (t == LLONG_MAX - 1) { q_s1 += Q_POS; r_s1 = R_POS; } else { long long rem = R_POS + t; q_s1 += rem / 3; r_s1 = rem % 3; } } else { // 无溢出,直接计算 long long s1 = x + y; q_s1 = s1 / 3; r_s1 = s1 % 3; } } else if (x < 0 && y < 0) { // 两个负数,判断是否溢出 if (x < LLONG_MIN - y) { // 负溢出场景:真实和 = LLONG_MIN + d long long d = x - (LLONG_MIN - y); q_s1 = Q_NEG; long long rem = R_NEG + d; q_s1 += rem / 3; r_s1 = rem % 3; } else { // 无溢出,直接计算 long long s1 = x + y; q_s1 = s1 / 3; r_s1 = s1 % 3; } } else { // 符号相反或含0,永远不会溢出 long long s1 = x + y; q_s1 = s1 / 3; r_s1 = s1 % 3; } // 加z,z为int类型,完全在long long范围内,无溢出风险 long long total_r = r_s1 + (long long)z; return q_s1 + total_r / 3; }
注意事项
- 代码中所有比较、加减法操作均未触发带符号整数溢出,全部为C标准明确定义的行为
- 整个流程未使用
unsigned long long类型,也未使用超过long long宽度的类型 - 若目标平台的
long long不是64位宽度,仅需重新计算对应位宽下的Q_POS、R_POS、Q_NEG、R_NEG四个常量即可,逻辑无需改动
内容的提问来源于stack exchange,提问作者deniskalistrat
相关产品推荐
相关产品推荐

