How to recover the Carry Bit

As frequent readers might have observed, I like the concept of the Carry Bit as it allows for efficient implementations of long integer arithmetic, which I would like to use as default integer type for most application development. And unfortunately such facilities are not available in high level languages like C and Java. But it is possible to recover the carry bit from what is available in C or Java, with some extra cost of performance, but maybe neglectable, if the compiler does a good optimization on this. We might assume gcc on a 64-Bit-Linux. It should be possible to do similar things on other platforms.

So we add two unsigned 64-bit integers $x$ and $y$ and an incoming carry 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

$0 \le x_l+y_l + i \le 2^{64}-1$

and we can see that

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

for some

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

.
And we have

$x+y+i = 2^{64}c+z$

where

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

is the carry bit.
When looking just at the highest visible bit and the carry bit, this boils down to

$2c+z_h = 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	c
0	0	0	0	0
1	0	0	1	0
0	1	0	1	0
1	1	0	0	1
0	0	1	1	0
1	0	1	0	1
0	1	1	0	1
1	1	1	1	1

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

$c = x_h \wedge\neg z_h \vee y_h \wedge\neg z_h \vee x_h \wedge y_h \wedge z_h$

$c = (x_h \vee y_h) \wedge\neg z_h \vee x_h \wedge y_h \wedge z_h.$

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

An incoming carry bit $d$ does not change this, it just allows for $x_l + y_l + d < 2^{64}$ , which is sufficient for making the previous calculations work.

In a similar way subtraction can be dealt with.

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

Beteilige dich an der Unterhaltung

Schreibe einen Kommentar

Antworten abbrechen