C++ 整形除法学习笔记

· · 算法·理论

@Lynkcat : 向0取整怎么你了 || @喵仔牛奶 : 除法向 0 取整也他妈是神人了，给又我创了一次。

不黑向 0 取整了。

整除与取模

大家都知道，C++ 中的除法是向 0 取整的。具体地，用 \text{div}(x,y) 表示 C++ 中 x/y 的值，有：

\text{div}(x,y)=\begin{cases}\lceil x/y\rceil&x/y<0\\\lfloor x/y\rfloor&x/y\ge 0\end{cases}

来看看 x%y 的值是什么。用 \text{mdl}(x,y) 表示 C++ 中 x%y 的值。大家肯定都知道 x\bmod y=x-y\times\lfloor\frac{x}{y}\rfloor，实际上，\text{mdl}(x,y) 也是这样的：

\text{mdl}(x,y)=x-y\times\text{div}(x,y)

我们可以发现一件事：

\begin{aligned} \text{div}(x,y)=&\begin{cases}\lceil x/y\rceil&x/y<0\\\lfloor x/y\rfloor&x/y\ge 0\end{cases}\\ =&\begin{cases}-\lceil (-x)/y\rceil&(-x)/y>0\\-\lfloor (-x)/y\rfloor&(-x)/y\le 0\end{cases}\\ =&-\text{div}(-x,y) \end{aligned} \begin{aligned} \text{div}(x,y)=&\begin{cases}\lceil x/y\rceil&x/y<0\\\lfloor x/y\rfloor&x/y\ge 0\end{cases}\\ =&\begin{cases}-\lfloor x/(-y)\rfloor&x/(-y)>0\\-\lceil x/(-y)\rceil&x/(-y)\le 0\end{cases}\\ =&-\text{div}(x,-y) \end{aligned}

也就是说，\text{div}(x,y) 拥有和 x/y 相似的美好性质，正负号可以在 x,y 之间和外面随便跑。

结合这个，还有：

\begin{aligned} \text{mdl}(x,y)=&x-y\times\text{div}(x,y)\\ =&x+y\times\text{div}(-x,y)\\ =&-(-x-y\times\text{div}(-x,y))\\ =&-\text{mdl}(-x,y) \end{aligned} \begin{aligned} \text{mdl}(x,y)=&x-y\times\text{div}(x,y)\\ =&x-(-y)\times\text{div}(x,-y)\\ =&\text{mdl}(x,-y) \end{aligned}

也就是说，x%y 可以看成 x 去掉符号对 \lvert y\rvert 取模，最后再把符号加回去。

还可以发现以下三个结论，证明简单，略去：

下取整实现

好吧，那我们要如何在 C++ 中算 \lfloor x/y\rfloor 呢？

floor(1.0*x/y) 是一种办法，但是值域很大时可能会出一些神秘问题，而且常数较大。我们希望有一种简单的只使用整数 +-*/% 的写法。

一种写法是 x/y-(x%y&&(x<0)!=(y<0))，意义就是当 x/y 不是整数且 x/y 为负数时额外减去 1。

其实还有更短的写法：x/y-(x%y*y<0)。当 x%y*y 不为 0 时，根据之前的结论（x%y 不为 0 时它的正负号和 x 相同），它的正负号和 x*y 的正负号相同，因此可以判断。但是这种写法当 y^2 大于值域时可能溢出，谨慎使用。

当 y 是正数时，可以写成 x/y-(x%y<0)。这和第二种写法等价，只是省去了 *y，不会溢出。

至于上取整，只需要将上面式子的 - 改为 +、< 改为 > 即可。

二进制右移

想必大家都看到过类似 (l+r)>>1 的写法，这个也可以下取整。

那么，x>>k 是否就等于 \lfloor\frac{x}{2^k}\rfloor 呢？

在 C++ 中，负数是用补码存储的。而对负数右移时，在最高位补的是 `1`。可以发现，`x>>k` 实际上等于 `~(~x>>k)`。 `~x` 等于 $-x-1$，因此 `x>>k` 等于 $-\lfloor\frac{-x-1}{2^k}\rfloor-1$，推一下： $$ \begin{aligned} -\lfloor\frac{-x-1}{2^k}\rfloor-1=&-(\lfloor\frac{-x-1}{2^k}\rfloor+1)\\ =&-\lfloor\frac{-x+2^k-1}{2^k}\rfloor\\ =&\lceil\frac{x-2^k+1}{2^k}\rceil\\ =&\lfloor\frac{x}{2^k}\rfloor\\ \end{aligned} $$ 因此，可以通过 `x>>k` 来简便地求出 $x$ 除以 $2^k$ 下取整的值。