c - C中的按位符号除法算法

Question

嗯，老实说，这实际上是我的作业，我必须在其中实现一个算法，该算法必须能够除以两个值而不用取它们的绝对值来进行除法。它还必须找出余数。

分红是绝对值大的，除数是绝对值小的。

我已经进行了大量的谷歌搜索，但大多数示例仅涵盖无符号值。

我尝试按照第一个回复提到的方案来实现: Implement division with bit-wise operator出于某种原因，这并没有让我走得太远。

然后我发现了这个: http://www4.wittenberg.edu/academics/mathcomp/shelburne/comp255/notes/BinaryDivision.pdf当我使用文档末尾的示例编写下面的代码时，它就可以正常工作了。

如果第一个值为正而第二个不是，则此方法正确。

我已经为此工作了至少 2 天。也许有人可以说我哪里错了。

---

这是我在@Dysaster 的帮助下拼凑起来的代码。当两个值都为负或正时它不起作用，但我在保护时设法得到 20 分(满分 25 分)。

#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)八次迭代后。或者，不是将负值移入 0，将正值移入 1，而是在主循环中通过在 r 为负时移入 1 来还原它，否则移入 0(这相当于隐式计算 Rg3 ^ 0xff)并加 1八次迭代后。要了解为什么需要加 1，请将 1 除以 -2，然后查看 r 始终保持负数 - 导致所有 1 s 将转移到 Rg3 .八次迭代后，您将得到 0xff(或 -1)，但它应该是 0。所以您加 1。

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

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

---

编辑:

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

我选择了0xFF初始值，因为 r只是 Rg1 的符号扩展到 16 位。自 r现在始终为负，在添加 Rg2 后检查它是变为零还是正很自然。

您应该能够处理 Rg1<0 的情况, Rg2<0很容易:简单地恢复 Rg2 的标志再次操作。也可以将四种不同的例程组合成一个处理所有四种情况的例程，但我也会将其留给您。 :)