C/CPP - 将浮点运算转换为整数运算

Question

我有以下c++函数（实现Bresenham's line algorithm），在书上看到

Computer Graphics From Pixels to Programmable Graphics Hardware By Alexey Boreskov, Evgeniy Shikin

其中一个函数使用浮点数，由于效率低下，本书提供了另一个仅使用整数运算的函数。

我很难理解为什么这两个是等价的，为什么我们在这里使用左移 <<，a<<1 不是简单地将 a 乘以 2 吗？

注意：我们假设点A:(xa,ya)和B:(xb,yb)有整数值。

浮动版本

void drawLine(int xa, int ya, int xb, int yb, int color) {
    float k = (float)(yb-ya)/(float)(xb-xa);
    float d = 2*k - 1
    int y = ya;

    putPixel(xa, ya, color); // paint the pixel (xa,ya) in color "color"

    for (int x = xa+1; x<=xb; x++) {
        if (d > 0) {
            d += 2*k + 2;
            y++;
        } else {
            d += 2*k;
        }
        putPixel(x, y, color);
    }
}

整数版本

void drawLine(int xa, int ya, int xb, int yb, int color) {
    int dx = xb - xa;
    int dy = yb -ya;
    int d = (dy<<1) - dx;
    int d1 = dy <<1;
    int d2 = (dy - dx) << 1;
    int y = ya;

    putPixel(xa, ya, color); // paint the pixel (xa,ya) in color "color"

    for (int x = xa+1; x<=xb; x++) {
        if (d > 0) {
            d += d2;
            y++;
        } else {
            d += d1;
        }
        putPixel(x, y, color);
    }
}

Answer 1

浮点代码用d做了四件事：

初始化d为2dy/dx−1，其中dy和dx分别是yb−ya和xb−xa.
判断d是否大于0。
将 2dy/dx+2 添加到 d.
将 2dy/dx 添加到 d.

在浮点数中，除以 dx 可能会产生非整数。为避免这种情况，我们通过将所有内容乘以 dx 来转换操作，得到：

初始化d为2dy−dx.
判断d是否大于0dx（等于0）。
将 2dy+2dx 添加到 d.
将 2dy 添加到 d。

我们很容易看出这四个等价的操作在除3之外的整数代码中实现。整数代码看起来是加上2dy−2dx 到 d。整数代码与 the Wikipedia page for Bresenham’s line algorithm 中显示的代码匹配。我怀疑浮点版的+是书上的错误

C/CPP - 将浮点运算转换为整数运算

C/CPP - Converting floating point arithmetic to integer arithmetic

c

c++

algorithm

floating-point

integer

浮动版本

整数版本