是否可以编写一个函数添加两个整数无控制流程,并严格按位运算? [英] 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屋!