Click here to Skip to main content
15,867,568 members
Articles / Programming Languages / C++
Tip/Trick

UInt128: Bit Operations

Rate me:
Please Sign up or sign in to vote.
4.96/5 (7 votes)
12 Jun 2014BSD5 min read 21.2K   225   10   1
Bit Operations on a 128 Bit Unsigned Integer
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

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

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

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

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

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

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

C++
// Normalizing a 64 bit integer
uint64 N = 67;
unsigned Ct = nlz64(N);
N <<= Ct;
// nlz64(N) now equals 0

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.

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

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

 
SuggestionMore bit twiddling hacks Pin
Member 1113877911-Dec-14 8:37
Member 1113877911-Dec-14 8:37 

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.