不能通过进位传播价值 [英] Cant make value propagate through carry
本文介绍了不能通过进位传播价值的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
制作一个小的C ++大精度类，一切似乎工作不错，但添加，如果我添加0xffffffff和0x04在一起我得到0xffff0003当我应该得到0x0100000003。这是有问题的函数：
mpfl运算符+（const mpfl& lhs，const mpfl& rhs）
{
unsigned long i;
mpfl ret（0）;
mpfl trhs（rhs）;
for（i = lhs.nbytes; i> = 0; i--）
{
if（
（unsigned short）lhs.data [i] .data + （unsigned short）trhs.data [i] .data
>（unsigned short）255
）{
if（i> 0）
{
ret .data [i] .carry = 1;
ret.data [0] .carry = 0;
}
else
{
ret.data [0] .carry = 1;
}
}
else
ret.data [i] .carry = 0;
ret.data [i] .data = lhs.data [i] .data + trhs.data [i] .data;
if（i <1hs.nbytes）
{
if（ret.data [i] .data == 255&& ret.data [i + 1] .carry = = 1）
increment（& trhs，i + 1）;
ret.data [i] .data + = ret.data [i + 1] .carry;
}
if（i == 0）break;
}
return ret;
}
这里是指向完整源代码的链接很多）
- 标题： https://github.com/phyrrus9/mpfl/blob/master/mpfl.h
- class： https://github.com/phyrrus9/mpfl/blob/master/mpfl.cpp
- 驱动程式： https://github.com /phyrrus9/mpfl/blob/master/main.cpp
解决方案
您的代码对我来说很凌乱。我之前有很多次（浮动，固定，uint，模板，...），所以这里有一些提示：
-
大多数算法都是为这样的环境编写的。它会清理并加速你的代码。在某些情况下，我使用asm为此，但如果你不想 CPU 依赖你可以使用这个类别
ALU C ++源代码：
// ---------------- -------------------------------------------------- ---------
// --- ALU32 class 1.00 ----------------------------- -------------------------
// ------------------- -------------------------------------------------- ------
#ifndef _ALU32_h
#define _ALU32_h
// ------------------------ -------------------------------------------------- -
class ALU32
{
public：
BYTE cy;
ALU32（）{cy = 0; }
void inc（DWORD& c）; // 3.4ns + 0.2ns类调用
void dec（DWORD& c）; // 3.4ns + 0.2ns for class call
void add（DWORD& c，DWORD a，DWORD b）; // 6.3ns + 0.2ns for class call
void sub（DWORD& c，DWORD a，DWORD b）; // 5.0ns + 0.2ns for class call
void adc（DWORD& c，DWORD a，DWORD b）; // 7.4ns + 0.2ns for class call
void sbc（DWORD& c，DWORD a，DWORD b）; // 5.6ns + 0.2ns类调用
void mul（DWORD& ch，DWORD& cl，DWORD a，DWORD b）; // 11.0ns + 0.2ns for class call
void div（DWORD& c，DWORD& d，DWORD ah，DWORD al，DWORD b）; // 13.5ns + 0.2ns for class call
};
// -------------------------------------------- -------------------------------
void ALU32 :: inc（DWORD& c）{if（c == 0xFFFFFFFF）cy = 1; else cy = 0; c ++; }
void ALU32 :: dec（DWORD& c）{if（c == 0x00000000）cy = 1; else cy = 0; C - ; }
// ------------------------------------------- --------------------------------
void ALU32 :: add（DWORD& c，DWORD a， DWORD b）
{
c = a + b;
cy = DWORD（（（a& 1）+（b& 1））>> 1）;
cy = DWORD（（（a> 1）+（b> 1）+ cy）> 31）;
}
// --------------------------------------- ------------------------------------
void ALU32 :: sub（DWORD& c ，DWORD a，DWORD b）
{
c = ab;
if（a< b）cy = 1; else cy = 0;
}
// --------------------------------------- ------------------------------------
void ALU32 :: adc（DWORD& c ，DWORD a，DWORD b）
{
c = a + b + cy;
cy = DWORD（（（a& 1）+（b& 1）+ cy）> 1）;
cy = DWORD（（（a> 1）+（b> 1）+ cy）> 31）;
}
// --------------------------------------- ------------------------------------
void ALU32 :: sbc（DWORD& c ，DWORD a，DWORD b）
{
c = ab-cy;
if（cy）{if（a <= b）cy = 1; else cy = 0; }
else {if（a< b）cy = 1; else cy = 0; }
}
// -------------------------------------- -------------------------------------
void ALU32 :: mul（DWORD& ch，DWORD& cl，DWORD a，DWORD b）
{
DWORD _a，_b，_cl，_ch;
_a = a;
_b = b;
asm {
mov eax，_a
mov ebx，_b
mul ebx // H（edx），L（eax）= eax * ebx
mov _cl， eax
mov _ch，edx
}
cl = _cl;
ch = _ch;
}
// --------------------------------------- ------------------------------------
void ALU32 :: div（DWORD& c ，DWORD& d，DWORD ah，DWORD al，DWORD b）
{
DWORD _al，_ah，_b，_c，_d;
_al = al;
_ah = ah;
_b = b;
asm {
mov eax，_al
mov edx，_ah
mov ebx，_b
div ebx
mov _c，eax // eax = H edx），L（eax）/ ebx
mov _d，edx // edx = H（edx），L（eax）％ebx
}
c =
d = _d;
}
// --------------------------------------- ------------------------------------
#endif
// - -------------------------------------------------- -----------------------
-
mul和div仍然是 CPU 但它们可以很容易地重写为不是... -
DWORD是32位unsigned int
-
- 现在如果你想添加两个数组/ strong>
ALU32 alu;
DWORD a [N]，b [N]，c [N]; // a [0]是LSB，a [N-1]是MSB
alu.add（c [0]，a [0]，b [0]）;
for（int i = 1; i
好主意使用最大的基础你可以提高速度。如果你仍然需要8位 ALU ，这也可以很容易地重写，甚至简化，因为直接访问进位。您可以使用16位或32位变量，并从子结果中抽取
第9位直接进位。 -
您的问题（从评论中复制）
我的赌注是您的问题在这里：
if（i
if（ret.data [i] .data == 255&& amp; ret.data [i + 1] .carry == 1）increment（& trhs，i + 1）;
ret.data [i] .data + = ret.data [i + 1] .carry;
}
carry应该总是应用，但第一次上次）。
-
data [0]是 LSB 或 MSB （低/最高有效位/字节...）？
您必须从最低位开始添加
- strong>
p>但展位不正确。 -
Making a little C++ large precision class, and everything seems to work decent, but the add, if I add 0xffffffff and 0x04 together I get 0xffff0003 when I should get 0x0100000003. Here is the function with the issue:
mpfl operator+(const mpfl &lhs, const mpfl &rhs)
{
unsigned long i;
mpfl ret(0);
mpfl trhs(rhs);
for (i = lhs.nbytes; i >= 0; i--)
{
if (
(unsigned short)lhs.data[i].data + (unsigned short)trhs.data[i].data
> (unsigned short)255
) {
if (i > 0)
{
ret.data[i].carry = 1;
ret.data[0].carry = 0;
}
else
{
ret.data[0].carry = 1;
}
}
else
ret.data[i].carry = 0;
ret.data[i].data = lhs.data[i].data + trhs.data[i].data;
if (i < lhs.nbytes)
{
if (ret.data[i].data == 255 && ret.data[i + 1].carry == 1)
increment(&trhs, i + 1);
ret.data[i].data += ret.data[i + 1].carry;
}
if (i == 0) break;
}
return ret;
}
Here are links to the full source (github made this easier since there is a lot of it)
- header: https://github.com/phyrrus9/mpfl/blob/master/mpfl.h
- class: https://github.com/phyrrus9/mpfl/blob/master/mpfl.cpp
- driver: https://github.com/phyrrus9/mpfl/blob/master/main.cpp
解决方案
Your code is very messy to me. I did (long)num classes many times before (floating,fixed,uint,templated,...) so here are some hints:
Try to setup ALU architecture similar to real HW implementation.
Most algorithms are written for such environment. It will clean and speed up your code. In some cases I use asm for this but if you want to be not CPU dependent you can use this class of mine
ALU source in C++:
//--------------------------------------------------------------------------- //--- ALU32 class 1.00 ------------------------------------------------------ //--------------------------------------------------------------------------- #ifndef _ALU32_h #define _ALU32_h //--------------------------------------------------------------------------- class ALU32 { public: BYTE cy; ALU32() { cy=0; } void inc(DWORD &c); // 3.4ns +0.2ns for class call void dec(DWORD &c); // 3.4ns +0.2ns for class call void add(DWORD &c,DWORD a,DWORD b); // 6.3ns +0.2ns for class call void sub(DWORD &c,DWORD a,DWORD b); // 5.0ns +0.2ns for class call void adc(DWORD &c,DWORD a,DWORD b); // 7.4ns +0.2ns for class call void sbc(DWORD &c,DWORD a,DWORD b); // 5.6ns +0.2ns for class call void mul(DWORD &ch,DWORD &cl,DWORD a,DWORD b); // 11.0ns +0.2ns for class call void div(DWORD &c,DWORD &d,DWORD ah,DWORD al,DWORD b); // 13.5ns +0.2ns for class call }; //--------------------------------------------------------------------------- void ALU32::inc(DWORD &c) { if (c==0xFFFFFFFF) cy=1; else cy=0; c++; } void ALU32::dec(DWORD &c) { if (c==0x00000000) cy=1; else cy=0; c--; } //--------------------------------------------------------------------------- void ALU32::add(DWORD &c,DWORD a,DWORD b) { c=a+b; cy=DWORD(((a &1)+(b &1) )>> 1); cy=DWORD(((a>>1)+(b>>1)+cy)>>31); } //--------------------------------------------------------------------------- void ALU32::sub(DWORD &c,DWORD a,DWORD b) { c=a-b; if (a<b) cy=1; else cy=0; } //--------------------------------------------------------------------------- void ALU32::adc(DWORD &c,DWORD a,DWORD b) { c=a+b+cy; cy=DWORD(((a &1)+(b &1)+cy)>> 1); cy=DWORD(((a>>1)+(b>>1)+cy)>>31); } //--------------------------------------------------------------------------- void ALU32::sbc(DWORD &c,DWORD a,DWORD b) { c=a-b-cy; if (cy) { if (a<=b) cy=1; else cy=0; } else { if (a< b) cy=1; else cy=0; } } //--------------------------------------------------------------------------- void ALU32::mul(DWORD &ch,DWORD &cl,DWORD a,DWORD b) { DWORD _a,_b,_cl,_ch; _a=a; _b=b; asm { mov eax,_a mov ebx,_b mul ebx // H(edx),L(eax) = eax * ebx mov _cl,eax mov _ch,edx } cl=_cl; ch=_ch; } //--------------------------------------------------------------------------- void ALU32::div(DWORD &c,DWORD &d,DWORD ah,DWORD al,DWORD b) { DWORD _al,_ah,_b,_c,_d; _al=al; _ah=ah; _b=b; asm { mov eax,_al mov edx,_ah mov ebx,_b div ebx mov _c,eax // eax = H(edx),L(eax) / ebx mov _d,edx // edx = H(edx),L(eax) % ebx } c=_c; d=_d; } //--------------------------------------------------------------------------- #endif //---------------------------------------------------------------------------mulanddivare still CPU dependent, but they can be easily rewritten to not be...DWORDis 32 bitunsigned int
So now if you want to add two arrays (fixed size N):
ALU32 alu; DWORD a[N],b[N],c[N]; // a[0] is LSB and a[N-1] is MSB alu.add(c[0],a[0],b[0]); for (int i=1;i<N;i++) alu.adc(c[i],a[i],b[i]); // here c[] = a[] + b[]it is a good idea to use the biggest base you can to improve speed. If you still need 8 bit ALU this can be also easily rewritten and even simplified due to direct access to carry. You can use 16 or 32 bit variables and extract
9thbit as carry directly from sub-results (looks like you are doing it).Your problem (copied from comment)
My bet is that your problem is here:
if (i<lhs.nbytes) { if (ret.data[i].data == 255 && ret.data[i + 1].carry == 1) increment(&trhs, i + 1); ret.data[i].data += ret.data[i + 1].carry; }carry should be applied always but the first time (you do it always but the last time). This also reveals other possibility how is your number stored?
data[0]is the LSB or MSB (low/most significant bit/byte...)?
You have to start adding from lowest digits
- so either you just applying carry the other way around
- or you are adding from highest to lowest digits
but booth are incorrect.
这篇关于不能通过进位传播价值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
