bit-manipulation - 是否可以编写一个没有控制流和严格按位运算的两个整数相加的函数？

Question

我误解了一道题，说用位运算将两个整数相加。我没有使用任何控制流程，也做不到。放弃后，我找到的所有解决方案都使用控制流来实现这一点，无论是 if、while、for、递归等， .有不能\不能完成的证明吗？

Answer 1

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

像这样(只是稍微测试了一下)(为了避免 C-purists 的愤怒，我将调用此 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-Stone adder (O(log n) 延迟加法器电路之一)在软件中也非常容易实现(在硬件中你必须处理很多电线，软件没有这个问题)。

例如:(使用 my website 验证)

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);
}