计算机取余/取整

我们常常认为，C语言里，整数除法是使用的“下取整”除法，因为：4 / 3 = 1。
但是，-4 / 3 = -1.3333，他的下取整应该是-2。但是，为什么程序输出了 -1？？？

实际上，对整数的除法，对于无法除尽的情况，我们会将他转换成：（可以除尽）
、、（即，交给计算机的两个数a/ b，其实他是可以除尽的！！）
DIV( a, b); a = k * b + r，即k = (a - r) / b
减去“余数r”后， (a - r)这个数，一定是可以被b整除的！！
所有的除法，不管结果是多少，必须满足： a = k * b + r

而问题的关键在于：这个“余数r” 怎么求？
r = a - k*b，这肯定是不行的，因为此时k正是需要求的数 k是未知的。
r = a % b，这是求余数的算法。

比如，-4 / 3。
-4 = -1 * 3 + -1 和 -4 = -2 * 3 + 2
这两种结果，也许你会认为是：除法“上取整、下取整”的结果。
其实在计算机里，上下取整的结果，是要根据 “余数”来计算的。
因为：k = (a - r) / b。（先求出余数r，才能求出结果k）

而，C语言对 %的定义，是一种称为： Truncate取余。

首先，先介绍： Truncate取整。
就像上面看的到，在C语言里：

整数除法对1.333 会取到 1 （即下取整）
整数除法对-1.333 会取到 -1 （即上取整）

所谓 Truncate（截断、去除），即将（小数点后的数值）直接扔掉！！！
这就导致了：（正数是下取整小了）（负数是上取整大了）即，结果会向 0 靠拢

所以，C/Java语言的整数除法，是使用的是： Truncate除法
即k = (a - r) / b
让（k 是 Truncate除法）成立的前提条件，取决于： 余数r的值！！

你会发现：

k = (a - r) / b，因为r = a%b，即k = (a - a%b) / b他的结果，就是Truncate除法

所以，你去记忆 C语言里，a%b的规则，其实是没用的。
因为，-4 % 3，他既可以是-1，也可以是2，都是合法的。

而对%结果的定义，他是要根据：k = (a - a%b) / b是Truncate除法，而反推出来的！！！
所以，反推出来的结果（也即C语言对%的定义是）：
、、4%3 = 1 -4%3 = -1 4%-3 = 1 -4%-3 = -1
、、注意，这个规则，千万不要去“死记硬背”！！！因为取余，本来就很灵活，没有一个唯一的规则。
、、比如，当你要计算： r = 4 % -3 = ?时： k = (4 - r) / -3，根据Truncate除法 r = -1.333 = -1
、、故，-1 = (4 - r) / -3，得： r = 1。
即：先根据Truncate除法手算出结果k，再根据k = (a - a%b) / b，去反推出a%b的结果

下取整、上取整

但有些情况，我们并不能使用 Truncate除法，而是“下取整”除法（即，-1.333 应该是-2“这才是下取整” ）

此时，我们就需要 “手写” 一个下取整的算法floor。（对于上取整ceil，对floor + 1即可）

对于下取整，我们也去遵循：k = (a - a%b) / b的规则。
但是，要重新定义：a%b规则。他的规则，也是根据k = (a - a%b) / b)是下取整，而反推出来的。

//  [4 % 3 = 1] [-4 % 3 = 2] [4 % -3 = -2] [-4 % -3 = -1]
//	该MOD函数， 完全是根据floor规则，而反推出来的。
template <typename _T>
_T MOD( _T _a, _T _mod){
    if( _mod >= 0){
        return ((_a % _mod) + _mod) % _mod;
    }
    return -((-_mod - MOD( (_a % _mod), -_mod)) % -_mod);
}

//  [1.33 = 1] [-1.33 = -2]
template <typename _T>
_T FLOOR( _T _numer, _T _deno){
    if( _deno == 0){
        EXIT;
    }
	if( _numer % _deno == 0){
		return _numer / _deno;
	}
    return ( _numer - MOD( _numer, _deno)) / _deno;
}

//  [1.33 = 2] [-1.33 = -1]
template <typename _T>
_T CEIL( _T _numer, _T _deno){
    if( _deno == 0){
        EXIT;
    }
	if( _numer % _deno == 0){
		return _numer / _deno;
	}
	return FLOOR( _numer, _deno) + 1;
}

二分

首先，先思考二分问题。
[1, 2, 3, 3, 3, 3, 4, 5]
[_, _, a, _, _, b, _, _]

如果要找a，则是： r = mid；
如果要找b，则是： l = mid；

根据这两种情形，得到： r = mid, l = mid + 1; 和 l = mid, r = mid - 1;

我们的二分算法，不断的缩小区间，最终，他一定会经历：l = a, r = a+1;这个阶段
而且他是二分的最后阶段（即，不会有下一次二分，这次完就出结果了）当然，这算是一个事后结论，定理。

因为此时l + r = 奇数，不能整除2。
而根据“除法”的分类：下取整mid = l、上取整mid = r、truncate取整mid = l或r

情形1：r = mid, l = mid + 1; 。
、、、如果此时mid = r，则会导致r = mid = r，死循环
、、、即，这种情况，必须是： mid = l
情形2：r = mid, l = mid + 1; 。
、、、如果此时mid = r，则会导致r = mid = r，死循环
、、、即，这种情况，必须是： mid = l