Циклический битовый сдвиг влево и вправо

Этот рецепт будет посвящен двум часто применяемым в криптографических и похожих алгоритмах, где требуется манипулировать переменными как потоками битов — циклическому сдвигу влево и вправо.

Данные операции встречаются довольно часто, а вот их реализации найти достаточно сложно и некоторые из существующих решений некорректны. Именно поэтому мы решили здесь разместить обе функции, как обычный рецепт, который легко будет найти впоследствии.

Циклический сдвиг влево (для целочисленных значений и на целочисленный шаг) можно представить следующим образом:

static uint rotateLeft(uint value, int shift) 
{
	return (value << shift) | (value >> (32 - shift));
}

static T rotateLeft(T)(T value, T shift) 
{
	return (value << shift) | (value >> (T.sizeof * 8 - shift));
}

Циклический сдвиг битов вправо выглядит несколько иначе:

static uint rotateRight(uint value, int shift) 
{
	return (value >> shift) | (value << (32 - shift));
}

static T rotateRight(T)(T value, T shift) 
{
	return (value >> shift) | (value << (T.sizeof * 8 - shift));
}

Эти операции, как ни странно, встречаются очень часто и не только в криптографии, автору этого блога однажды удалось найти подобные операции в скоростном алгоритме сортировки, а также в одном из алгоритмов обработки изображений! И, поскольку циклические сдвиги упоминаются во многих алгоритмах, а реализации обычно предлагаются для сдвигов только на 1 бит, настоятельно рекомендуем взять рецепт на вооружение.

И напоследок определения из C, переведенные для D (циклические сдвиги для 32-битных беззнаковых целочисленных значений):

uint rotl32(uint value, uint count) 
{
    uint mask = 8 * sizeof(value) - 1;
    count &= mask;
    return (value << count) | (value >> (-count & mask));
}

uint rotr32(uint value, uint count) 
{
    uint mask = 8 * sizeof(value) - 1;
    count &= mask;
    return (value >> count) | (value << (-count & mask));
}