12,401,608 members (29,376 online)
Tip/Trick
Add your own
alternative version

17K views
165 downloads
11 bookmarked
Posted

# UInt128: Addition/Subtraction

, 12 Jun 2014 BSD
 Rate this:
Please Sign up or sign in to vote.
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.

### Addition

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

## License

This article, along with any associated source code and files, is licensed under The BSD License

## About the Author

 United States
No Biography provided

## Comments and Discussions

 First Prev Next
 Why did you not make your datatype a class and overload its operator? Wong Shao Voon12-Jun-14 21:37 Wong Shao Voon 12-Jun-14 21:37
 Re: Why did you not make your datatype a class and overload its operator? Jacob F. W.12-Jun-14 23:05 Jacob F. W. 12-Jun-14 23:05
 what is the best way to implement bitwise shift operations? carga16-Dec-13 3:45 carga 16-Dec-13 3:45
 Re: what is the best way to implement bitwise shift operations? Jacob F. W.22-Dec-13 11:11 Jacob F. W. 22-Dec-13 11:11
 My vote of 5 nv38-Jul-13 21:15 nv3 8-Jul-13 21:15
 Good code, small bug in Subtraction Hans8-Jul-13 20:38 Hans 8-Jul-13 20:38
 Re: Good code, small bug in Subtraction Jacob F. W.9-Jul-13 9:33 Jacob F. W. 9-Jul-13 9:33
 Thank you for sharing this ! Flaviu27-Jul-13 21:17 Flaviu2 7-Jul-13 21:17
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Jul-16 3:02 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160721.1 | Last Updated 12 Jun 2014
Article Copyright 2013 by Jacob F. W.
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid