Операция побитового сдвига на 128-битном числе

Question

Допустим, у меня есть массив из 4 32-разрядных целых чисел, которые я использую для хранения 128-разрядного числа

Как я могу выполнить сдвиг влево и вправо для этого 128-битного числа?

Спасибо!

Answer 1

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);
    }
}

Answer 2

Работать с uint128? Если вы можете, используйте инструкции x86 SSE, которые были разработаны именно для этого. (Затем, когда вы изменили битовое значение, вы готовы выполнять другие 128-битные операции...)

Сдвиги битов SSE2 занимают в среднем ~4 инструкции с одной ветвью (оператор case). Никаких проблем со смещением более 32 бит тоже. Полный код для этого, использующий встроенные функции gcc вместо необработанного ассемблера, находится в sseutil.c ( github: "Необычное использование SSE2") - и это немного больше, чем имеет смысл вставлять сюда.

Препятствием для многих людей при использовании SSE2 является то, что сменные операции требуют немедленного (постоянного) количества смен. Вы можете решить это с небольшим изменением препроцессора 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 ... выполнение всей смены в двух инструкциях.

Answer 3

Вместо использования 128-битного числа, почему бы не использовать битовый набор? Используя битсет, вы можете настроить, насколько большим он будет. Плюс вы можете выполнить немало операций над ним.

Вы можете найти больше информации об этом здесь:

http://www.cppreference.com/wiki/utility/bitset/start?do=backlink

Answer 4

Во-первых, если вы переходите на n биты и n больше или равно 32, делим на 32 и сдвигаем целые числа. Это должно быть тривиально. Теперь у вас осталось количество сдвигов от 0 до 31. Если оно равно нулю, вернитесь рано, все готово.

Для каждого целого числа вам нужно сдвинуться на оставшиеся n, затем сдвиньте смежное целое число на ту же величину и объедините действительные биты от каждого.

Answer 5

Поскольку вы упоминали, что храните свое 128-битное значение в массиве из 4 целых чисел, вы можете сделать следующее:

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;
        }
    }
}