代码优化之求两个整型的平均值

  • 2020 年 5 月 29 日
  • 笔记

在 C/C++ 中, 直接利用 (x + y) >> 1 来计算 \(\left\lfloor {\left( {x + y} \right)/2} \right\rfloor\) (两个整数的平均值并向下取整)以及直接利用 (x + y + 1) >> 1 来计算 \(\left\lceil {\left( {x + y} \right)/2} \right\rceil\) (两个整数的平均值并向上取整)的结果可能有误, 因为 (x + y) >> 1(x + y + 1) >> 1 中的 x + y 可能会发生数值溢出. 而 \(\left\lfloor {\left( {x + y} \right)/2} \right\rfloor\)\(\left\lceil {\left( {x + y} \right)/2} \right\rceil\) 的结果是不可能数值溢出的, 这就引发我们思考可不可能通过某种方式来规避平均值计算中的数值溢出.

方式一

利用如下公式

\(\begin{align}
\left\lfloor {\left( {x + y} \right)/2} \right\rfloor = \left\lfloor {x/2} \right\rfloor + \left\lfloor {y/2} \right\rfloor + \left\lfloor {\left( {x\bmod 2 + y\bmod 2} \right)/2} \right\rfloor \hfill \\
\left\lceil {\left( {x + y} \right)/2} \right\rceil = \left\lfloor {x/2} \right\rfloor + \left\lfloor {y/2} \right\rfloor + \left\lceil {\left( {x\bmod 2 + y\bmod 2} \right)/2} \right\rceil \hfill \\
\end{align}\)

下面是对上述两式的证明:
\(\begin{align}
\left\lfloor {\left( {x + y} \right)/2} \right\rfloor &= \left\{ {\begin{array}{*{20}{c}}
{m + n}&{x = 2m,y = 2n} \\
{m + n}&{x = 2m + 1,y = 2n} \\
{m + n}&{x = 2m,y = 2n + 1} \\
{m + n + 1}&{x = 2m + 1,y = 2n + 1}
\end{array}} \right. \\
&= \left\lfloor {x/2} \right\rfloor + \left\lfloor {y/2} \right\rfloor + \left\lfloor {\left( {x\bmod 2 + y\bmod 2} \right)/2} \right\rfloor \\
\end{align}\)

\(\begin{align}
\left\lceil {\left( {x + y} \right)/2} \right\rceil &= \left\{ {\begin{array}{*{20}{c}}
{m + n}&{x = 2m,y = 2n} \\
{m + n + 1}&{x = 2m + 1,y = 2n} \\
{m + n + 1}&{x = 2m,y = 2n + 1} \\
{m + n + 1}&{x = 2m + 1,y = 2n + 1}
\end{array}} \right. \\
&= \left\lfloor {x/2} \right\rfloor + \left\lfloor {y/2} \right\rfloor + \left\lceil {\left( {x\bmod 2 + y\bmod 2} \right)/2} \right\rceil \\
\end{align}\)

其中 \(m,n\) 均为整数.

借用上面的公式可以 \(\left\lfloor {\left( {x + y} \right)/2} \right\rfloor\) 转化为如下的 C/C++ 代码 (据说这段代码还被申请了专利):

(x >> 1) + (y >> 1) + (x & y & 1);

可以将 \(\left\lceil {\left( {x + y} \right)/2} \right\rceil\) 转化为如下的 C/C++ 代码:

(x >> 1) + (y >> 1) + ((x | y) & 1);

这两段代码都不会发生数值溢出.

方式二

设 x 和 y 只能取 0 和 1 值, 则:

x y x + y x ^ y x & y x | y 2*(x & y) + (x ^ y) 2*(x | y) – (x ^ y)
0 0 0 0 0 0 0 + 0 = 0 0 – 0 = 0
0 1 1 1 0 1 0 + 1 = 1 10 – 1 = 1
1 0 1 1 0 1 0 + 1 = 1 10 – 1 = 1
1 1 10 0 1 1 10 + 0 = 10 10 – 0 = 10

注意上表中的 10 是二进制下的 10, 即十进制下的 2, & 是逻辑与操作, | 是逻辑或运算, ^ 是逻辑异或操作.

由上表可见 x + y = 2*(x & y) + (x ^ y) = 2*(x | y) - (x ^ y).

无符号整型

对于无符号整型, 设 \(x = \sum\nolimits_{i = 0}^{n – 1} {{u_i}{2^i}}\)\(y = \sum\nolimits_{i = 0}^{n – 1} {{v_i}{2^i}}\).

\(\begin{align}
x + y &= \sum\nolimits_{i = 0}^{n – 1} {{u_i}{2^i}} {\text{ + }}\sum\nolimits_{i = 0}^{n – 1} {{v_i}{2^i}} \\
&= \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i} + {v_i}} \right){2^i}} \\
&= \sum\nolimits_{i = 0}^{n – 1} {\left( {2 \times \left( {{u_i}\& {v_i}} \right) + \left( {{u_i} \wedge {v_i}} \right)} \right){2^i}} \\
&= 2\sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}\& {v_i}} \right){2^i}} + \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i} \wedge {v_i}} \right){2^i}} \\
\end{align}\)

\(\begin{align}
\left\lfloor {\left( {x + y} \right)/2} \right\rfloor &= \left\lfloor {\sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}\& {v_i}} \right){2^i}} + \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i} \wedge {v_i}} \right){2^{i – 1}}} } \right\rfloor \\
&= \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}\& {v_i}} \right){2^i}} + \sum\nolimits_{i = 1}^{n – 1} {\left( {{u_i} \wedge {v_i}} \right){2^{i – 1}}} \\
\end{align}\)

上式用 C/C++语言可以表示为:

(x & y) + ((x ^ y) >> 1);

\(\begin{align}
x + y &= \sum\nolimits_{i = 0}^{n – 1} {{u_i}{2^i}} {\text{ + }}\sum\nolimits_{i = 0}^{n – 1} {{v_i}{2^i}} \\
&= \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i} + {v_i}} \right){2^i}} \\
&= \sum\nolimits_{i = 0}^{n – 1} {\left( {2 \times \left( {{u_i}|{v_i}} \right) – \left( {{u_i} \wedge {v_i}} \right)} \right){2^i}} \\
&= 2\sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}|{v_i}} \right){2^i}} – \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i} \wedge {v_i}} \right){2^i}} \\
\end{align}\)

\(\begin{align}
\left\lceil {\left( {x + y} \right)/2} \right\rceil &= \left\lceil {\sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}|{v_i}} \right){2^i}} – \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i} \wedge {v_i}} \right){2^{i – 1}}} } \right\rceil \\
&= \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}|{v_i}} \right){2^i}} – \sum\nolimits_{i = 1}^{n – 1} {\left( {{u_i} \wedge {v_i}} \right){2^{i – 1}}} \\
\end{align}\)

上式用 C/C++ 语言可以表示为:

(x | y) - ((x ^ y) >> 1);

有符号整型

对于有符号整型, 设 \(x = – {u_{n – 1}}{2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {{u_i}{2^i}}\)\(y = – {v_{n – 1}}{2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {{v_i}{2^i}}\).

\(\begin{align}
x + y &= – {u_{n – 1}}{2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {{u_i}{2^i}} – {v_{n – 1}}{2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {{v_i}{2^i}} \\
&= – \left( {{u_{n – 1}} + {v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {\left( {{u_i} + {v_i}} \right){2^i}} \\
&= – \left( {2 \times \left( {{u_{n – 1}}\& {v_{n – 1}}} \right) + \left( {{u_{n – 1}} \wedge {v_{n – 1}}} \right)} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {\left( {2 \times \left( {{u_i}\& {v_i}} \right) + \left( {{u_i} \wedge {v_i}} \right)} \right){2^i}} \\
&= 2\left( { – \left( {{u_{n – 1}}\& {v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}\& {v_i}} \right){2^i}} } \right) + \left( { – \left( {{u_{n – 1}} \wedge {v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {\left( {{u_i} \wedge {v_i}} \right){2^i}} } \right) \\
\end{align}\)

\(\begin{align}
\left\lfloor {\left( {x + y} \right)/2} \right\rfloor &= \left\lfloor {\left( { – \left( {{u_{n – 1}}\& {v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}\& {v_i}} \right){2^i}} } \right) + \left( { – \left( {{u_{n – 1}} \wedge {v_{n – 1}}} \right){2^{n – 2}} + \sum\nolimits_{i = 0}^{n – 2} {\left( {{u_i} \wedge {v_i}} \right){2^{i – 1}}} } \right)} \right\rfloor \\
&= \left( { – \left( {{u_{n – 1}}\& {v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}\& {v_i}} \right){2^i}} } \right) + \left( { – \left( {{u_{n – 1}} \wedge {v_{n – 1}}} \right){2^{n – 2}} + \sum\nolimits_{i = 1}^{n – 2} {\left( {{u_i} \wedge {v_i}} \right){2^{i – 1}}} } \right) \\
\end{align}\)

上式用 C/C++ 语言可以表示为:

(x & y) + ((x ^ y) >> 1);

\(\begin{align}
x + y &= – {u_{n – 1}}{2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {{u_i}{2^i}} – {v_{n – 1}}{2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {{v_i}{2^i}} \\
&= – \left( {{u_{n – 1}} + {v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {\left( {{u_i} + {v_i}} \right){2^i}} \\
&= – \left( {2 \times \left( {{u_{n – 1}}|{v_{n – 1}}} \right) – \left( {{u_{n – 1}} \wedge {v_{n – 1}}} \right)} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {\left( {2 \times \left( {{u_i}|{v_i}} \right) – \left( {{u_i} \wedge {v_i}} \right)} \right){2^i}} \\
&= 2\left( { – \left( {{u_{n – 1}}|{v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}|{v_i}} \right){2^i}} } \right) – \left( { – \left( {{u_{n – 1}} \wedge {v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 2} {\left( {{u_i} \wedge {v_i}} \right){2^i}} } \right) \\
\end{align}\)

\(\begin{align}
\left\lceil {\left( {x + y} \right)/2} \right\rceil &= \left\lceil {\left( { – \left( {{u_{n – 1}}|{v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}|{v_i}} \right){2^i}} } \right) – \left( { – \left( {{u_{n – 1}} \wedge {v_{n – 1}}} \right){2^{n – 2}} + \sum\nolimits_{i = 0}^{n – 2} {\left( {{u_i} \wedge {v_i}} \right){2^{i – 1}}} } \right)} \right\rceil \\
&= \left( { – \left( {{u_{n – 1}}|{v_{n – 1}}} \right){2^{n – 1}} + \sum\nolimits_{i = 0}^{n – 1} {\left( {{u_i}|{v_i}} \right){2^i}} } \right) – \left( { – \left( {{u_{n – 1}} \wedge {v_{n – 1}}} \right){2^{n – 2}} + \sum\nolimits_{i = 1}^{n – 2} {\left( {{u_i} \wedge {v_i}} \right){2^{i – 1}}} } \right) \\
\end{align}\)

上式用 C/C++ 语言可以表示为:

(x | y) - ((x ^ y) >> 1);

综合

综合上面的分析, 可见对于有符号整型和无符号整型,

\(\left\lceil {\left( {x + y} \right)/2} \right\rceil\) 都可以用 C/C++ 语言表示为:

(x & y) + ((x ^ y) >> 1);

\(\left\lceil {\left( {x + y} \right)/2} \right\rceil\) 都可以用 C/C++ 语言表示为:

(x | y) - ((x ^ y) >> 1);

参考:

版权声明

版权声明:自由分享,保持署名-非商业用途-非衍生,知识共享3.0协议。
如果你对本文有疑问或建议,欢迎留言!转载请保留版权声明!
如果你觉得本文不错, 也可以用微信赞赏一下哈.