Click here to Skip to main content
15,867,453 members
Articles / General Programming / Algorithms
Tip/Trick

UInt128: Addition/Subtraction

Rate me:
Please Sign up or sign in to vote.
4.86/5 (11 votes)
12 Jun 2014BSD3 min read 41.4K   280   11   8
Adding and subtracting a 128 Bit Unsigned Integer
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.

C++
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:

C++
// 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.

C++
// 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:

C++
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.

C++
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.

C++
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.

C++
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


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionWhy did you not make your datatype a class and overload its operator? Pin
Shao Voon Wong12-Jun-14 21:37
mvaShao Voon Wong12-Jun-14 21:37 
AnswerRe: Why did you not make your datatype a class and overload its operator? Pin
Jacob F. W.12-Jun-14 23:05
Jacob F. W.12-Jun-14 23:05 
Questionwhat is the best way to implement bitwise shift operations? Pin
carga16-Dec-13 3:45
carga16-Dec-13 3:45 
AnswerRe: what is the best way to implement bitwise shift operations? Pin
Jacob F. W.22-Dec-13 11:11
Jacob F. W.22-Dec-13 11:11 
GeneralMy vote of 5 Pin
nv38-Jul-13 21:15
nv38-Jul-13 21:15 
QuestionGood code, small bug in Subtraction Pin
Hans8-Jul-13 20:38
Hans8-Jul-13 20:38 
AnswerRe: Good code, small bug in Subtraction Pin
Jacob F. W.9-Jul-13 9:33
Jacob F. W.9-Jul-13 9:33 
QuestionThank you for sharing this ! Pin
_Flaviu7-Jul-13 21:17
_Flaviu7-Jul-13 21:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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