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
