是否可以编写一个函数添加两个整数无控制流程，并严格按位运算？ [英] Is it possible to write a function adding two integers without control flow and strictly bitwise operations?

问题描述

我误解了一个问题，说要加用位运算两个整数。我没有使用任何控制流，不能做到这一点。放弃，所有的解决方案后，我发现使用控制流来完成这个不管它是一个如果，，而，为，递归等，。是否有证据证明是可以\\无法实现？

I misunderstood a question that said to add two integers using bitwise operations. I did not use any control flow and could not do it. After giving up, all the solutions I found use control flow to accomplish this whether it be an if, while, for, recursion, etc,. Is there a proof that is can\cannot be accomplished?

推荐答案

有关固定长度的整数，你可以解开一个波进位加法器。在最坏的情况下，进位信号具有从至少显著位一路传播到最显著位

For a fixed length integer, you can just unroll a ripple carry adder. In the worst case, a carry signal has to propagate all the way from the least significant bit to the most significant bit.

这样的（只是稍微测试）（避免C-纯粹主义者的愤怒，我会打电话给这个C＃code）

Like this (only slightly tested) (to avoid the C-purists' wrath, I will call this C# code)

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
}

如果你这样做了许多位作为整数将举行，您将不再需要在最后的面具。

If you do it for as many bits as your integer will hold, you won't need the mask in the end.

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

That's not very efficient, clearly. For 3 bits it's fine, but for 32 bits it becomes quite long. A Kogge-Stone adder (one of the O(log n) delay adder circuits) is also surprisingly easy to implement in software (in hardware you have to deal with a lot of wires, software doesn't have that problem).

例如：（使用验证<一个href=\"http://haroldbot.cloudapp.net/?q=let%20p%20%3D%20x%20%5E%20y%2C%20g%20%3D%20x%20%26%20y%2C%20p2%20%3D%20p%20%26%20%28p%20%3C%3C%201%29%2C%20g2%20%3D%20g%20%7C%20%28p%20%26%20%28g%20%3C%3C%201%29%29%2C%20p3%20%3D%20p2%20%26%20%28p2%20%3C%3C%202%29%2C%20g3%20%3D%20g2%20%7C%20%28p2%20%26%20%28g2%20%3C%3C%202%29%29%2C%20p4%20%3D%20p3%20%26%20%28p3%20%3C%3C%204%29%2C%20g4%20%3D%20g3%20%7C%20%28p3%20%26%20%28g3%20%3C%3C%204%29%29%2C%20p5%20%3D%20p4%20%26%20%28p4%20%3C%3C%208%29%2C%20g5%20%3D%20g4%20%7C%20%28p4%20%26%20%28g4%20%3C%3C%208%29%29%2C%20g6%20%3D%20g5%20%7C%20%28p5%20%26%20%28g5%20%3C%3C%2016%29%29%20in%20x%20%5E%20y%20%5E%20%28g6%20%3C%3C%201%29\"相对=nofollow>我的网站）

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

这篇关于是否可以编写一个函数添加两个整数无控制流程，并严格按位运算？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！