How to recover the Borrow Bit

In a similar way as the carry bit for addition it is possible to recover the borrow bit for substraction, just based on the highest bits of three numbers that we deal with during the operation.

With this program, a subtraction operation of an 8-bit CPU can be simulated exhaustively

#!/usr/bin/perl


my $x, $x, $bi;
my %tab = ();
for ($bi = 0; $bi <= 1; $bi++) {
    for ($x = 0; $x < 256; $x++) {
        for ($y = 0; $y < 256; $y++) {
            my $zz = $x - $y - $bi;
            my $b  = $zz < 0 ? 1 : 0;
            my $c  = 1 - $b;
            my $z = ($zz + 256) & 0xff;
            my $xs = $x >> 7;

            my $ys = $y >> 7;

            my $zs = $z >> 7;

            my $key = "$xs:$ys:$zs";

            $tab{$key} //= $b;

            my $bb = $tab{$key};

            if ($bb != $b) {

                print "b=$b bb=$bb c=$c xs=$xs ys=$ys zs=$zs x=$x y=$y z=$z zz=$zz bi=$bi\n";

            }

        }

    }

}

for my $key (sort keys %tab) { $key =~ m/(\d+):(\d+):(\d+)/; $xs=$1; $ys=$2; $zs=$3; $b =$tab{$key}; $c = 1 - $b; $bb = $xs & $ys & $zs | !$xs & ($ys | $zs); print "b=$b bb=$bb c=$c xs=$xs ys=$ys zs=$zs\n"; }

This gives an idea, what is happening. But in real life, probably a 64bit-CPU is used, but the concepts would work with longer or shorter CPU words the same way.

So we subtract two unsigned 64-bit integers $x$ and $y$ and an incoming borrow bit $i\in\{0, 1\}$ to a result

$z\equiv x-y-i \mod 2^{64}$

with

$0 \le z < 2^{64}$

using the typical „long long“ of C. We assume that

$x=2^{63}x_h+x_l$

where

$x_h \in \{0,1\}$

and

$0 \le x_l < 2^{63}.$

In the same way we assume $y=2^{63}y_h + y_l$ and $z=2^{63}z_h + z_l$ with the same kind of conditions for $x_h$ , $y_h$ , $z_h$ or $x_l$ , $y_l$ , $z_l$ , respectively.

Now we have

$-2^{63} \le x_l-y_l-i \le 2^{63}-1$

and we can see that

$x_l - y_l - i = z_l-2^{63}u$

for some

$u\in \{0,1\}$

.
And we have

$x-y-i = z-2^{64}b$

where

$b\in\{0,1\}$

is the borrow bit.
When combining we get

$2^{63}x_h - 2^{63}y_h + z_l - 2^{63}u = 2^{63}x_h + x_l -2^{63}y_h-x_l -i = x-y-i = z - 2^{64}b = 2^{63}z_h + z_l -2^{64}b$

When looking just at the highest visible bit and the borrow bit, this boils down to

$z_h-2b = x_h - y_h - u$

This leaves us with eight cases to observe for the combination of $x_h$ , $y_h$ and $u$ :

x_h	y_h	u	z_h	b
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	1
1	0	0	1	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

Or we can check all eight cases and find that we always have

$b = x_h \wedge y_h \wedge z_h \vee \neg x_h \wedge (y_h \vee z_h)$

So the result does not depend on $u$ anymore, allowing to calculate the borrow bit by temporarily casting $x$ , $y$ and $z$ to (signed long long) and using their sign.
We can express this as „use $y_h \wedge z_h$ if $x_h=1$ and use $y_h \vee z_h$ if $x_h = 0$ „.

The incoming borrow bit $i$ does not change this, it just allows for $x_l - y_l - d \ge -2^{64}$ , which is sufficient for making the previous calculations work.

The basic operations add, adc, sub, sbb, mul, xdiv (div is not available) have been implemented in this library for C. Feel free to use it according to the license (GPL). Addition and subtraction could be implemented in a similar way in Java, with the weirdness of declaring signed longs and using them as unsigned. For multiplication and division, native code would be needed, because Java lacks 128bit-integers. So the C-implementation is cleaner.

Schreibe einen Kommentar

Antwort abbrechen