C/C++程式碼優化之求兩個整型的平均值
- 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}}\), 其中 \(u_i,v_i\in\left\{ 0, 1 \right\}\).
\(\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}}\), 其中 \(u_i,v_i\in\left\{ 0, 1 \right\}\).
\(\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\lfloor {\left( {x + y} \right)/2} \right\rfloor\) 都可以用 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協議。
如果你對本文有疑問或建議，歡迎留言！轉載請保留版權聲明！
如果你覺得本文不錯, 也可以用微信讚賞一下哈.
