Geek asks and answers

Bitwise shift operation on a 128-bit number

Suppose I have an array of 4 32-bit integers that I use to store a 128-bit number

How can I shift left and right on this 128-bit number?

Thank!

+3
source share
5 answers
void shiftl128 (
    unsigned int& a,
    unsigned int& b,
    unsigned int& c,
    unsigned int& d,
    size_t k)
{
    assert (k <= 128);
    if (k >= 32) // shifting a 32-bit integer by more than 31 bits is "undefined"
    {
        a=b;
        b=c;
        c=d;
        d=0;
        shiftl128(a,b,c,d,k-32);
    }
    else
    {
        a = (a << k) | (b >> (32-k));
        b = (b << k) | (c >> (32-k));
        c = (c << k) | (d >> (32-k));
        d = (d << k);
    }
}

void shiftr128 (
    unsigned int& a,
    unsigned int& b,
    unsigned int& c,
    unsigned int& d,
    size_t k)
{
    assert (k <= 128);
    if (k >= 32) // shifting a 32-bit integer by more than 31 bits is "undefined"
    {
        d=c;
        c=b;
        b=a;
        a=0;
        shiftr128(a,b,c,d,k-32);
    }
    else
    {
        d = (c << (32-k)) | (d >> k); \
        c = (b << (32-k)) | (c >> k); \
        b = (a << (32-k)) | (b >> k); \
        a = (a >> k);
    }
}
+3
source

Work with uint128? If you can, use the x86 SSE instructions that were designed specifically for this. (Then, when you have lost your value, you are ready to perform other 128-bit operations ...)

SSE2 4 , (case case). 32 . - gcc-intrinsics, raw-, sseutil.c(github: " SSE2" ) - , . SSE2 , shift () . C (wordpress: C). , :

LeftShift (uint128 x, int n) = _mm_slli_epi64 (_mm_slli_si128 (x, n/8), n% 8) n = 65..71, 73..79,... 121..127 ... .

+4

-, n bits n 32, 32 . . 0 31. , , .

For each integer, you need to shift the remaining one n, and then shift the adjacent integer by the same amount and combine the actual bits from each.

+1
source

Since you mentioned that you are storing a 128-bit value in an array of 4 integers, you can do the following:

void left_shift(unsigned int* array)
{   
    for (int i=3; i >= 0; i--)
    {
        array[i] = array[i] << 1;

        if (i > 0)
        {
            unsigned int top_bit = (array[i-1] >> 31) & 0x1;
            array[i] = array[i] | top_bit;
        }
    }
}

void right_shift(unsigned int* array)
{   
    for (int i=0; i < 4; i++)
    {
        array[i] = array[i] >> 1;

        if (i < 3)
        {
            unsigned int bottom_bit = (array[i+1] & 0x1) << 31;
            array[i] = array[i] | bottom_bit;
        }
    }
}
0
source

More articles:


All Articles