代码优化之整型除以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\) .

又因为 \(\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++代码.

const int INT_BITS = 32;

int div_exp2(int x, unsigned char k)
{
    if (k == 0) return x;
    int tail = x >> (INT_BITS - 1);
    return (x + (1 <> k;
}

测试代码

#include 
#include 
#include 

int div_exp2_plain(int x, unsigned char k)
{
    int den = 1 < 0)
    {
        return int(float(x) / den + 0.5);
    }
    else
    {
        return int(float(x) / den - 0.5);
    }
}

const int INT_BITS = 32;

int div_exp2(int x, unsigned char k)
{
    if (k == 0) return x;
    int tail = x >> (INT_BITS - 1);
    return (x + (1 <> k;
}


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 < 10000; ++i)
    {
        int x = random(-1111, 11111);
        int val1 = div_exp2_plain(x, k);
        int val2 = div_exp2(x, k);
        if (val1 != val2)
        {
            float val = float(x) / (1 << k);
            printf("%d / 2^%d: %.2f, %d, %d\n", x, k, val, val1, val2);
        }
        else
        {
            // printf("Pass\n");
        }
    }
    printf("=========================\n");
    return 0;
}

版权声明