C中的按位符号除法算法

Question

好吧,说实话,这实际上是我的作业,我必须实现一个算法,必须能够划分两个值而不用它们的绝对值来进行除法.它还必须找出其余部分.

被除数是绝对值较大的除数,分压器的绝对值较小.

我做了很多谷歌搜索,但大多数例子只涵盖无符号值.

我尝试通过第一个回复中提到的方案来实现它: 使用逐位运算符实现除法 由于某种原因,这并没有让我走得太远.

然后我发现了这个:http: //www4.wittenberg.edu/academics/mathcomp/shelburne/comp255/notes/BinaryDivision.pdf 当我使用文档末尾的例子编写下面的代码时,我得到了它.

如果第一个值是正数而第二个值不是,那么这个就是正确的.

我现在至少工作了2天.也许有人可以说我哪里出错了.

---

这是我在@Dysaster的帮助下设法编写的代码.当两个值都是负数或正数时它不起作用但我在保护中设法从25中得到20分.

#include <stdio.h>
#include <stdlib.h>

char *bits(char Rg) {

    unsigned char bit = 0x80;
    int i;
    char *bits;
    bits = (char*) malloc(9);
    for (i=0; i < 8; i++) {
        *(bits+i) = Rg & bit ? '1' : '0';
        bit >>= 1;
    }
    *(bits+i) = '\0';
    return bits;
}

int divide(char Rg1, char Rg2) {

    char Rg3, r=0;
    int i;

    printf("Rg1 : %s (%2d)\n", bits(Rg1), Rg1);
    printf("Rg2 : %s (%2d)\n", bits(Rg2), Rg2);
    Rg3 = Rg1;
    printf("Rg3 : %s (%2d)  <- copy of Rg1\n", bits(Rg3), Rg3);
    if (Rg1 < 0) {
        r = 0xff;
    }
    printf("rem : %s (%2d)  <- remainder after sign check\n", bits(r), r);

    for (i = 0; i < 8; i++) {

        printf("\n ------------ %d. ITERATION ------------\n", i+1);


        if (Rg3 & 0x80) {
            printf(" - left shift r and Rg3, carry\n");
            Rg3 <<= 1;
            r <<= 1;
            r += 1;
            printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);
        } else {
            printf(" - left shift r and Rg3\n");
            Rg3 <<= 1;
            r <<= 1;
            printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);
        }

        printf(" - add in the divisor\n");
        r += Rg2;
        printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);

        if (Rg1 < 0 && Rg2 > 0 && r >= 0 || Rg1 > 0 && Rg2 < 0 && r < 0) { // real ugly, I know
            printf(" - subtract the divisor and set the lowest bit of Rg3 to 1\n");
            r -= Rg2;
            Rg3 |= 0x01;
            printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);
        } else {
            printf(" - lowest bit of Rg3 stays 0\n");
            printf(" > %s (%2d) | %s (%2d)\n", bits(r), r, bits(Rg3), Rg3);
        }

    }

    // post division sign check
    if ((Rg1 < 0 && Rg2 > 0) || (Rg1 > 0 && Rg2 < 0)) {
        Rg3++;
    }

    printf("\n%s (%d) / %s (%d) = %s (%d) r %s (%d)\n\n", bits(Rg1), Rg1, bits(Rg2), Rg2, bits(Rg3), Rg3, bits(r), r);
}


int main(int argc, char *argv[]) {

    divide(-13, -4); // buggy
    divide(-29, 4);  // OK
    divide(19, -8);  // OK
    divide(17, 5);   // buggy

    return 0;
}

Answer 1

看起来不允许你取绝对值的限制是一个很大的限制。可以稍微修改代码来处理 Rg1>0 和 Rg2<0 的情况。

您无需取负数的绝对值，只需更改使用 Rg2 的位置的符号 - 并更改输出上的符号。你似乎已经开始这样做了，但忘记了对你的除数取反的一点点（完成后 Rg3 中剩下的东西）。您可以通过两种方式做到这一点：保持算法不变，但Rg3=(Rg3^0xff + 1)在八次迭代后进行设置。或者，您可以在主循环中通过在 r 为负时移入 1 来恢复它，否则移入 0（这相当于隐式计算），并在Rg3 ^ 0xff8 个后面添加 1，而不是移入 0（表示负数）和 1（表示正数）迭代。要了解为什么需要加 1，请将 1 除以 -2，并看到 r 始终保持负数 - 导致所有1s 都移入Rg3。八次迭代后，您将得到 0xff（或 -1），但它应该是 0。因此您添加 1。

顺便说一句，功能上有一个错误bits。该行char bit = 0x80应为unsigned char bit = 0x80，因为值 0x80 的有符号字符在右移时会变为 0xC0 - 这会弄乱您的位值。

任何状况之下。Rg1<0我不知道如何处理无论 的符号如何的情况Rg2。如果我能想到什么，我会更新答案。最后，您的部门将必须根据每个输入参数的符号选择四种算法之一来完成这项工作。

编辑：

我不确定如何准确解释它，但对于Rg1<0,的情况Rg2>0，解决方案是简单地将 的初始值更改为r，并将下面的0xff符号检查更改为。的结果是，并且 的结果是。如果希望余数始终为正，则需要将 Rg3 减 1，并将 Rg2 添加到 r。rr >= 0-19/8-2*8-3-29/4-7*4-1

我选择0xFF初始值，因为它只是16 位r的符号扩展。Rg1由于r现在总是负数，因此在添加后检查它是否变为零或正数Rg2是很自然的。

您应该能够非常轻松地处理 的情况Rg1<0：Rg2<0只需再次恢复操作的符号即可Rg2。也可以将四种不同的例程组合成一个处理所有四种情况的例程，但我也将其留给您。:)