UInt128 Series
Background
My first and second articles in the UInt128 Series were, respectively, Addition/Subtract and Multiplication/Squaring. So the next logical step is.... Bit Operations.
So yeah, this article is kind of a step backwards. The reason is that, while I was working on the Division/Modulo Article, I realized it used several bit operations that I hadn't introduced. My first thought was to combine the Bit Operations with the Division article, but I realized that if I did that, there was enough of them that they might overshadow the Division functions, therefore negating the entire purpose of having a separate article just for Division. Alternatively, I could cover only the bit operations that the Division code needed and ignore the rest, but that would seem a bit half-a$$ed.
Finally, I decided that I had given each class of operation its own separate article, so I might as well keep the tradition going.
Functions
I will be covering three types of operations in this article:
- Logic Gates
- Bit Shifts
- Bit Counters
Now the first two types I won't be covering in much detail, because if you don't know what they are, you really shouldn't be reading this. The last one I will be covering and give examples of, as they aren't encountered that much in classes or books unless they are absolutely needed.
Comparison
Before we look at the main operations, there is one function I want to go over; the Comparison Function. It takes two UInt128's, N1 and N2, and returns:
1 if N1 is greater than N2
-1 if N1 is less than N2
0 if N1 is equal to N2
int compare128(uint128 N1, uint128 N2)
{
return (((N1.Hi > N2.Hi) || ((N1.Hi == N2.Hi) && (N1.Lo > N2.Lo))) ? 1 : 0)
- (((N1.Hi < N2.Hi) || ((N1.Hi == N2.Hi) && (N1.Lo < N2.Lo))) ? 1 : 0);
}
Logic Gates
So first up, we will be looking at the four basic logic operations, Not, Or, And, Xor. These are the simplest operations, as we can just use the machine operations on each 64 bit part of the Integer.
void not128(uint128 N, uint128& A)
{
A.Hi = ~N.Hi;
A.Lo = ~N.Lo;
}
void or128(uint128 N1, uint128 N2, uint128& A)
{
A.Hi = N1.Hi | N2.Hi;
A.Lo = N1.Lo | N2.Lo;
}
void and128(uint128 N1, uint128 N2, uint128& A)
{
A.Hi = N1.Hi & N2.Hi;
A.Lo = N1.Lo & N2.Lo;
}
void xor128(uint128 N1, uint128 N2, uint128& A)
{
A.Hi = N1.Hi ^ N2.Hi;
A.Lo = N1.Lo ^ N2.Lo;
}
Bit Shifts
Next up are the Left and Right Shifts. These ones are a little more complicated since we have to deal with separate where they overlap. I'll be showing you two versions of these functions. The first is a simple implementation that shows off the different cases.
void shiftleft128(uint128 N, unsigned S, uint128& A)
{
S &= 127;
if(S != 0)
{
if(S > 64)
{
A.Hi = N.Lo << (S - 64);
A.Lo = 0;
}
else if(S < 64)
{
A.Hi = (N.Hi << S) | (N.Lo >> (64 - S));
A.Lo = N.Lo << S;
}
else
{
A.Hi = N.Lo;
A.Lo = 0;
}
}
else
{
A.Hi = N.Hi;
A.Lo = N.Lo;
}
}
void shiftright128(uint128 N, unsigned S, uint128& A)
{
S &= 127;
if(S != 0)
{
if(S > 64)
{
A.Hi = N.Hi >> (S - 64);
A.Lo = 0;
}
else if(S < 64)
{
A.Lo = (N.Lo >> S) | (N.Hi << (64 - S));
A.Hi = N.Hi >> S;
}
else
{
A.Lo = N.Hi;
A.Hi = 0;
}
}
else
{
A.Hi = N.Hi;
A.Lo = N.Lo;
}
}
The second version is an optimized implementation I developed, which doesn't use if-else statements, eliminating branching in the code.
void shiftleft128(uint128 N, unsigned S, uint128& A)
{
uint64 M1, M2;
S &= 127;
M1 = ((((S + 127) | S) & 64) >> 6) - 1llu;
M2 = (S >> 6) - 1llu;
S &= 63;
A.Hi = (N.Lo << S) & (~M2);
A.Lo = (N.Lo << S) & M2;
A.Hi |= ((N.Hi << S) | ((N.Lo >> (64 - S)) & M1)) & M2;
}
void shiftright128(uint128 N, unsigned S, uint128& A)
{
uint64 M1, M2;
S &= 127;
M1 = ((((S + 127) | S) & 64) >> 6) - 1llu;
M2 = (S >> 6) - 1llu;
S &= 63;
A.Lo = (N.Hi >> S) & (~M2);
A.Hi = (N.Hi >> S) & M2;
A.Lo |= ((N.Lo >> S) | ((N.Hi << (64 - S)) & M1)) & M2;
}
Note: Both versions will be included in the downloadable code, with the unoptimized version commented out.
Bit Counters
The basic idea behind bit counters is that we are looking for count various patterns of bits that appear in an integer. There are many, many types of patterns you could look for, but the three types I will go over are Population Count, Leading Zeroes, and Trailing Zeroes.
Population Count
Basically, population count means to count all the 1 bits in an integer for instance.
6 in binary is 110, so the population count would be 2.
0 in binary is 0, so the population count would be 0.
21 in binary is 10101, so the population count would be 3.
255 in binary is 11111111, so the population count would be 8.
So we just have to count the number of 1s in the Hi and Lo Bits of the UInt128, and add them together.
size_t popcnt128(uint128 N)
{
return popcnt64(N.Hi) + popcnt64(N.Lo);
}
size_t popcnt64(uint64 V)
{
V -= ((V >> 1) & 0x5555555555555555);
V = (V & 0x3333333333333333) + ((V >> 2) & 0x3333333333333333);
return ((V + (V >> 4) & 0xF0F0F0F0F0F0F0F) * 0x101010101010101) >> 56;
}
The code for the Population Count in a 64 bit Unsigned Integer comes from Bit Twiddling Hacks, a great site I highly recommend to anyone interested in these types of functions.
Trailing Zeroes
Counting trailing zeroes means that we start at the least significant bit, and count how many zeroes there are before you hit the first 1s bit.
For example:
148 in binary is 10010100 so there are 2 trailing zeroes
1952 in binary is 11110100000 so there are 5 trailing zeroes.
595 in binary is 101010011 so there are 0 trailing zeroes.
In case it isn't obvious from 595, any odd number will have 0 trailing zeroes.
There's one special situation, and that is 0. How many trailing zeroes does 0 have? Well, ultimately this depends on how big the integer you're storing it in is.
unsigned char - 8 trailing zeroes
unsigned short - 16 trailing zeroes
unsigned long - 32 trailing zeroes
unsigned long long - 64 trailing zeroes
And in our case:
uint128 - 128 trailing zeroes.
So to count the Trailing Zeroes in a UInt128, we first need to check and see if the Low 64 Bits are all 0s. If they are, then we count the trailing zeroes in the High 64 Bits, and add 64 to that count. If the Low 64 Bits aren't all 0s, then we have to count the trailing zeroes in it.
size_t ntz128(uint128 N)
{
return (N.Lo == 0) ? ntz64(N.Hi) + 64 : ntz64(N.Lo);
}
size_t ntz64(uint64 N)
{
uint64 I = ~N;
size_t C = ((I ^ (I + 1)) & I) >> 63;
I = (N & 0xffffffff) + 0xffffffff;
I = ((I & 0x100000000) ^ 0x100000000) >> 27;
C += I; N >>= I;
I = (N & 0xffff) + 0xffff;
I = ((I & 0x10000) ^ 0x10000) >> 12;
C += I; N >>= I;
I = (N & 0xff) + 0xff;
I = ((I & 0x100) ^ 0x100) >> 5;
C += I; N >>= I;
I = (N & 0xf) + 0xf;
I = ((I & 0x10) ^ 0x10) >> 2;
C += I; N >>= I;
I = (N & 3) + 3;
I = ((I & 4) ^ 4) >> 1;
C += I; N >>= I;
C += ((N & 1) ^ 1);
return C;
}
Leading Zeroes
As you may have guessed, leading zeroes is the opposite of trailing zeroes: you start at the most significant bit of the integer type, and count how many zeroes until you reach the most significant bit of the number itself. This mean that the size of the datatype always determines the number of leading zeroes.
So if you have the number 1 stored in an 8 bit integer, the binary form would be
00000001 so there are 7 leading zeroes.
But if you stored it in a 16 bit integer:
0000000000000001 so there would be 15 leading zeroes
In binary, 67 in an 8 bit integer would be
01000011 so there is 1 leading zero.
But again, if it was a 16 bit integer:
0000000001000011 so there are 9 leading zeroes.
And just like trailing zeroes, in the case of 0, it would be the bitsize of the word.
Leading zeroes is commonly used to normalize an integer, which means you shift the integer all the way up so that it's leading bit is in the highest place.
uint64 N = 67;
unsigned Ct = nlz64(N);
N <<= Ct;
So, just like with trailing zeroes, we can count the leading zeroes of a UInt128 by counting the leading zeroes in each 64 bit half. First we have to check to see if the High 64 bits are all 0s; if they are we can count the leading zeroes in the Low 64 bits, and add 64 to them. If the High 64 bits aren't all 0s, then we just count the leading zeroes in them.
size_t nlz128(uint128 N)
{
return (N.Hi == 0) ? nlz64(N.Lo) + 64 : nlz64(N.Hi);
}
size_t nlz64(uint64 N)
{
uint64 I;
size_t C;
I = ~N;
C = ((I ^ (I + 1)) & I) >> 63;
I = (N >> 32) + 0xffffffff;
I = ((I & 0x100000000) ^ 0x100000000) >> 27;
C += I; N <<= I;
I = (N >> 48) + 0xffff;
I = ((I & 0x10000) ^ 0x10000) >> 12;
C += I; N <<= I;
I = (N >> 56) + 0xff;
I = ((I & 0x100) ^ 0x100) >> 5;
C += I; N <<= I;
I = (N >> 60) + 0xf;
I = ((I & 0x10) ^ 0x10) >> 2;
C += I; N <<= I;
I = (N >> 62) + 3;
I = ((I & 4) ^ 4) >> 1;
C += I; N <<= I;
C += (N >> 63) ^ 1;
return C;
}
Conclusion
So, with the functions out of the way, we can proceed to the juicy stuff. I should have the Division/Modulus article out soon, so keep an eye out for it.
As always, if you find any bugs in my code, please let me know, and I'll try to fix them a.s.a.p.
