14,388,187 members

Rate this:
12 Jun 2014BSD
Adding and subtracting a 128 Bit Unsigned Integer

## Introduction

One of my pet projects I've been working on is a 128 bit Unsigned Integer Datatype. Not really anything new or innovative: it's primarily been just a fun learning experience: something I would work on during the weekends or in class when my teacher started teaching the same thing about functions that he had covered for the third time that past week.

Currently, I'm working on cleaning up the code to make it a little more presentable before I upload it. In the meantime, I'd like to go over some of the tricks I used to get it up and running. In this tip, I'll go over the `Addition`/`Subtraction `& `Increment`/`Decrement `Functions. I have two more tips planned, one to cover Multiplication, and the second to cover the biggest beasts of all, Division and Modulus.

## Datatype

To keep things as simple as possible, I'll be using a very simple `struct `to represent the datatype, and will only be using functions, no operators.

```struct uint128
{
uint64 Hi;
uint64 Lo;
}; ```

Two 64 bit unsigned integers, `Hi` and `Lo`, are used to hold the upper and lower bits respectively.

## Functions

### Increment

So the first function to cover is the `Increment `Function. Simple enough, right. A basic implementation would look like this:

```// Basic Version
void Increment(uint128& N)
{
N.Lo++;
if(N.Lo == 0)
{
N.Hi++;
}
} ```

It increments the lower bits, then if they overflow, it increments the upper bits. Easy enough, right?

Yes, if you want the simplest version, that would be it. But one of my goals has been to make this as fast and efficient as possible. In this case, we use an `if `statement, which could lead to a branch delay, which makes it a bit of a nuisance when it comes to performance.

```// Optimized Version
void Increment(uint128& N)
{
uint64 T = (N.Lo + 1);
N.Hi += ((N.Lo ^ T) & N.Lo) >> 63;
N.Lo = T;
}```

This version increments `Lo`, calculates the Carry bit (either 1 or 0) and adds it to `Hi`. Imagine if `Lo` and `Hi` were only 4 bits:

```Hi: 1010
Lo: 1111```

`Lo` will only overflow if it is at its maximum value, i.e., all its bits are 1. What we do is compare the highest bit in` Lo` before and after we increment it. If the highest bit is `1 `before we increment, and `0 `after that means it overflowed. The neat thing is that instead of using the comparison operators and `if `statements, we can just use bitwise operators and shifts.

### Decrement

The `Decrement `function is, of course, the `Increment `function in reverse.

```void Decrement(uint128& N)
{
uint64 T = (N.Lo - 1);
N.Hi -= ((T ^ N.Lo) & T) >> 63;
N.Lo = T;
}```

Apart from using subtraction instead of addition, the only difference is that we reverse where `T` and `Lo` are when we calculate the carry bit.

Now things start to get interesting. While the addition itself is not that complicated, calculating the carry bit is. The only way I could figure it out was to, sadly, cheat.

```void Add(uint128& Ans, uint128 N, uint128 M)
{
uint64 C = (((N.Lo & M.Lo) & 1) + (N.Lo >> 1) + (M.Lo >> 1)) >> 63;
Ans.Hi = N.Hi + M.Hi + C;
Ans.Lo = N.Lo + M.Lo;
}  ```

The cheat here is that while `Hi` and `Lo` are only 64 bit integers, we treat them as if they were 65 bit. We add the two lowest bits together, and get their carry bit, then we shift `N.Lo` and `M.Lo` down one bit, and add them and the carry bit together. The highest bit of the Sum will indicate whether or not they overflowed, so we shift all the way back down, and add it to `Ans.Hi`.

### Subtraction

Subtraction uses the same trick as addition, only the Lower bits first, then calculate the carry bit to determine if it underflowed.

```void Subtract(uint128& Ans, uint128 N, uint128 M)
{
Ans.Lo = N.Lo - M.Lo;
uint64 C = (((Ans.Lo & M.Lo) & 1) + (M.Lo >> 1) + (Ans.Lo >> 1)) >> 63;
Ans.Hi = N.Hi - (M.Hi + C);
}```

## Conclusion

So that's it for now. Next up is Multiplication, then Division after that. If you find any bugs or have any questions, I'll see you in the comments.

Jacob

## Share

 United States
No Biography provided

 First Prev Next
 Why did you not make your datatype a class and overload its operator? Shao Voon Wong12-Jun-14 22:37 Shao Voon Wong 12-Jun-14 22:37
 Re: Why did you not make your datatype a class and overload its operator? Jacob F. W.13-Jun-14 0:05 Jacob F. W. 13-Jun-14 0:05
 Because the point of these articles is not to show the full, working product. I wanted to go over the individual functions and focus only on them. Having additional operators would clutter the code. Don't worry though; after I finish the articles, I plan on releasing the full class (with operators and everything). That will probably happen in a week or so.
 what is the best way to implement bitwise shift operations? carga16-Dec-13 4:45 carga 16-Dec-13 4:45
 Re: what is the best way to implement bitwise shift operations? Jacob F. W.22-Dec-13 12:11 Jacob F. W. 22-Dec-13 12:11
 My vote of 5 nv38-Jul-13 22:15 nv3 8-Jul-13 22:15
 Good code, small bug in Subtraction Hans8-Jul-13 21:38 Hans 8-Jul-13 21:38
 Re: Good code, small bug in Subtraction Jacob F. W.9-Jul-13 10:33 Jacob F. W. 9-Jul-13 10:33
 Thank you for sharing this ! _Flaviu7-Jul-13 22:17 _Flaviu 7-Jul-13 22:17
 Last Visit: 11-Dec-19 0:50     Last Update: 11-Dec-19 0:50 Refresh 1