##### UInt128 Series

## 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:

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.

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