是否可以在没有控制流和严格按位运算的情况下编写一个将两个整数相加的函数？

Question

我误解了一个问题，说使用按位运算将两个整数相加。我没有使用任何控制流，也做不到。放弃后，我找到的所有解决方案都使用控制流来完成此操作，无论是if, while, for, 递归等。是否有不能\不能完成的证明？

Answer 1

对于固定长度的整数，您只需展开一个波纹进位加法器即可。在最坏的情况下，进位信号必须从最低有效位一直传播到最高有效位。

像这样（仅略作测试）（为了避免 C 纯粹主义者的愤怒，我将称此为 C# 代码）

int add_3bits(int x, int y)
{
    int c = x & y;
    x = x ^ y;
    y = c << 1;
    //
    c = x & y;  //  \
    x = x ^ y;  //  | for more bits, insert more of these blocks
    y = c << 1; //  /
    //
    // optimized last iteration
    return (x ^ y) & 7; // for more bits, change that mask
}

如果您对整数可以容纳的位数进行操作，那么最终您将不需要掩码。

显然，这不是很有效。对于 3 位，它很好，但是对于 32 位，它变得很长。一个Kogge酒店石加法器（在O（log n）的延迟加法器电路的一个）也非常容易在软件中实现（在硬件，你必须处理大量的电线，软件不存在这样的问题）。

例如：（使用我的网站验证）

static uint add_32bits(uint x, uint y)
{
    uint p = x ^ y;
    uint g = x & y;

    g |= p & (g << 1);
    p &= p << 1;

    g |= p & (g << 2);
    p &= p << 2;

    g |= p & (g << 4);
    p &= p << 4;

    g |= p & (g << 8);
    p &= p << 8;

    g |= p & (g << 16);

    return x ^ y ^ (g << 1);
}