C/C++代码优化之整型除以2的指数并四舍五入 - quarryman - D1h.Net第一号博客
返回主页

采石工

随笔 - 13  文章 - 0  评论 - 29

C/C++代码优化之整型除以2的指数并四舍五入

前几天 QQ 群里一位好友提出来一个问题: "整型(有正有负)除以2的指数结果四舍五入, 应该如何优化呢", 当时做了答, 发表在这里, 并做些许修订, 希望对大家有用.

引子

前几天 QQ 群里一位好友提出来一个问题: "整型(有正有负)除以2的指数结果四舍五入, 应该如何优化呢", 当时做了答, 发表在这里, 并做些许修订, 希望对大家有用.

符号约记

下取整函数的定义: \(\left\lfloor x \right\rfloor = \max \left\{ {z \in \mathbb{Z}:z \leqslant x} \right\}\)

上取整函数的定义: \(\left\lceil x \right\rceil = \min \left\{ {z \in \mathbb{Z}:z \geqslant x} \right\}\)

四舍五入取整函数的定义: \(\left[\kern-0.15em\left[ x \right]\kern-0.15em\right] = \left\{ {\begin{array}{*{20}{c}} {\left\lfloor {x + 0.5} \right\rfloor }&{x > 0} \\ {\left\lceil {x - 0.5} \right\rceil }&{x \leqslant 0} \end{array}} \right.\)

正文

问题: 整型(有正有负)除以2的指数结果四舍五入, 应该如何优化呢?

问题转化为: 将 \(\left[\kern-0.15em\left[ {\frac{m}{2^k}} \right]\kern-0.15em\right]\) 转化为向下取整 (以便能够使用移位运算) 的形式,其中 \(m\) 为整数, \(k\) 为非负整数.

答: 因为 \(\left[\kern-0.15em\left[ {\frac{m}{n}} \right]\kern-0.15em\right] = \left\{ {\begin{array}{*{20}{c}} {\left\lfloor {\frac{m}{n} + \frac{1}{2}} \right\rfloor = \left\lfloor {\frac{1}{n}\left( {m + \left\lfloor {\frac{n}{2}} \right\rfloor } \right)} \right\rfloor }&{mn \geqslant 0} \\ {\left\lceil {\frac{m}{n} - \frac{1}{2}} \right\rceil = \left\lceil {\frac{1}{n}\left( {m - \left\lfloor {\frac{n}{2}} \right\rfloor } \right)} \right\rceil }&{mn < 0} \end{array}} \right.\), 其中 \(m, n\) 均为整数, \(n \neq 0\).

特别地, 设 \(n = 2^k\) ( \(k\) 为非负整数) 时, 当 \(k=0\) 时, \(\left[\kern-0.15em\left[ m \right]\kern-0.15em\right] = m\);
\(k>0\) 时, \(\left[\kern-0.15em\left[ {\frac{m}{{{2^k}}}} \right]\kern-0.15em\right] = \left\{ {\begin{array}{*{20}{c}} {\left\lfloor {\frac{m}{{{2^k}}} + \frac{1}{2}} \right\rfloor = \left\lfloor {\frac{1}{{{2^k}}}\left( {m + \left\lfloor {\frac{{{2^k}}}{2}} \right\rfloor } \right)} \right\rfloor = \left\lfloor {\frac{{m + {2^{k - 1}}}}{{{2^k}}}} \right\rfloor }&{m \geqslant 0} \\ {\left\lceil {\frac{m}{{{2^k}}} - \frac{1}{2}} \right\rceil = \left\lceil {\frac{1}{{{2^k}}}\left( {m - \left\lfloor {\frac{{{2^k}}}{2}} \right\rfloor } \right)} \right\rceil = \left\lceil {\frac{{m - {2^{k - 1}}}}{{{2^k}}}} \right\rceil }&{m < 0} \end{array}} \right.\).

又因为 \(\left\lceil {\frac{m}{n}} \right\rceil = \left\{ {\begin{array}{*{20}{c}} {\left\lfloor {\frac{{m + n - 1}}{n}} \right\rfloor = \left\lfloor {\frac{{m - 1}}{n}} \right\rfloor + 1}&{n > 0} \\ {\left\lfloor {\frac{{m + n + 1}}{n}} \right\rfloor = \left\lfloor {\frac{{m + 1}}{n}} \right\rfloor + 1}&{n < 0} \end{array}} \right.\),

所以 \(\left\lceil {\frac{{m - {2^{k - 1}}}}{{{2^k}}}} \right\rceil = \left\lfloor {\frac{{m - {2^{k - 1}} + {2^k} - 1}}{{{2^k}}}} \right\rfloor = \left\lfloor {\frac{{m + {2^{k - 1}} - 1}}{{{2^k}}}} \right\rfloor\).

综上, \(\left[\kern-0.15em\left[ {\frac{m}{{{2^k}}}} \right]\kern-0.15em\right] = \left\{ {\begin{array}{*{20}{c}} m&{k = 0} \\ {\left\lfloor {\frac{{m + {2^{k - 1}}}}{{{2^k}}}} \right\rfloor }&{k > 0,m \geqslant 0} \\ {\left\lfloor {\frac{{m + {2^{k - 1}} - 1}}{{{2^k}}}} \right\rfloor }&{k > 0,m < 0} \end{array}} \right.\).

上式可以很方便地转写为只包含加减和位运算的C/C++代码.

int div_exp2(int x, unsigned char k) { assert( (k >= 0) && (k < INT_BITS)); if (k == 0) return x; int tail = x >> (INT_BITS - 1); int exp2_k_1 = 1 << (k - 1); // 当 x >=0 时, bias = 1 << (k - 1) // 当 x < 0 时, bias = (1 << (k - 1)) - 1 // 这时 k > 0, 所以 bias >= 0 恒成立. int bias = tail + exp2_k_1; // 当 (x >= 0) && (x + bias < 0) 时, 表明 x + bias 在 int 取值范围内溢出, // 而其在 unsigned int 取值范围内不会溢出, 所以将其转化为 unsigned int 进行运算. if ((x >= 0) && (x + bias < 0)) { return int(((unsigned int)(x + bias)) >> k); } else { return (x + bias) >> k; } } 

下面尝试合并 div_exp2 函数的最后的条件语句. 利用 "算术右移" 和 "逻辑右移" 的关系, 可以将 :

int(((unsigned int)(x + bias)) >> k); 

转换为

int mask = ~(-1 << (INT_BITS - k)); return ((x + bias) >> k) & mask; 

于是得到合并后的语句:

// 当 (x >= 0) && (x + bias < 0) 时, 由于 tail = 0, condition = -1, 所以 mask = ~(-1 << (INT_BITS - k)), 等效于上面的代码. // 其他情况下, mask = -1, ((x + bias) >> k) & mask 等效于 (x + bias) >> k. int condition = (x + bias) >> (INT_BITS - 1); int mask = ~( (-1 << (INT_BITS - k) ) & ~tail & condition); return ((x + bias) >> k) & mask; 

所以, 最终得到:

int div_exp2(int x, unsigned char k) { assert( (k >= 0) && (k < INT_BITS)); if (k == 0) return x; int tail = x >> (INT_BITS - 1); int exp2_k_1 = 1 << (k - 1); // 当 x >=0 时, bias = 1 << (k - 1) // 当 x < 0 时, bias = (1 << (k - 1)) - 1 // 这时 k > 0, 所以 bias >= 0 恒成立. int bias = tail + exp2_k_1; // 当 (x >= 0) && (x + bias < 0) 时, 表明 x + bias 在 int 取值范围溢出, // 而其在 unsigned int 取值范围内不会溢出, 所以将其转化为 unsigned int 进行运算. int condition = (x + bias) >> (INT_BITS - 1); int mask = ~( (-1 << (INT_BITS - k) ) & ~tail & condition); return ((x + bias) >> k) & mask; } 

测试代码

#include <stdlib.h> #include <time.h> #include <stdio.h> #include <limits.h> #include <assert.h> const int INT_BITS = 32; double div_exp2_float(int x, unsigned char k) { assert( (k >= 0) && (k < INT_BITS)); unsigned int den = 1 << k; return double(x) / den; } int div_exp2_plain(int x, unsigned char k) { assert( (k >= 0) && (k < INT_BITS)); unsigned int den = 1 << k; if (x > 0) { return int(double(x) / den + 0.5); } else { return int(double(x) / den - 0.5); } } int div_exp2(int x, unsigned char k) { assert( (k >= 0) && (k < INT_BITS)); if (k == 0) return x; int tail = x >> (INT_BITS - 1); int exp2_k_1 = 1 << (k - 1); // 当 x >=0 时, bias = 1 << (k - 1) // 当 x < 0 时, bias = (1 << (k - 1)) - 1 // 这时 k > 0, 所以 bias >= 0 恒成立. int bias = tail + exp2_k_1; // 当 (x >= 0) && (x + bias < 0) 时, 表明 x + bias 在 int 取值范围溢出, // 而其在 unsigned int 取值范围内不会溢出. 所以将其转化为 unsigned int 进行运算. int condition = (x + bias) >> (INT_BITS - 1); int mask = ~( (-1 << (INT_BITS - k) ) & ~tail & condition); return ((x + bias) >> k) & mask; } int random(int lower, int upper) { if (lower > upper) { int temp = lower; lower = upper; upper = temp; } return rand() % (upper - lower + 1) + lower; } int main() { int k = 5; printf("=========================\n"); for (int i = 0; i < 100; ++i) { int x = random(-1111, 11111); float val = div_exp2_float(x, k); int val1 = div_exp2_plain(x, k); int val2 = div_exp2(x, k); if (val1 != val2) { printf("%d / 2^%d: %.2f, %d, %d\n", x, k, val, val1, val2); } else { // printf("Pass\n"); printf("%d / 2^%d: %.2f, %d, %d\n", x, k, val, val1, val2); } } printf("=========================\n"); printf("%f\n", div_exp2_float(INT_MIN, 31)); printf("%f\n", div_exp2_float(INT_MIN + 1, 31)); printf("%f\n", div_exp2_float(INT_MAX, 31)); printf("%d\n", div_exp2_plain(INT_MIN, 31)); printf("%d\n", div_exp2_plain(INT_MIN + 1, 31)); printf("%d\n", div_exp2_plain(INT_MAX, 31)); printf("%d\n", div_exp2(INT_MIN, 31)); printf("%d\n", div_exp2(INT_MIN + 1, 31)); printf("%d\n", div_exp2(INT_MAX, 31)); return 0; } 

版权声明

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

posted @ 2020-05-24 12:09  quarryman  阅读(...)  评论(...编辑  收藏
Copyright © 2020 quarryman
Powered by .NET Core on Kubernetes

问答 28u iTmz.Net 3q科技 A8团队1 A8团队2 A8团队3 A8备