Циклический сдвиг в целом числе на n бит влево и вправо

Старая тема, наткнулся на неё при поиске другой задачи и захотел подытожить её, так как других тем с такой задачей на форуме больше нет (да и в остальном рунет тоже не шибко таких).

1) В первую очередь, надо определиться с самим понятием что такое

функция циклического сдвига в 2p разрядном целом

.

В общем случае возможны варианты: отрицательное и неотрицательное число, разрядность стандартная (8, 16, 32, 64 бита) или произвольная.

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

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

С битностью всё несколько сложнее. Даже с самим представлением числа не всё ясно. Можно использовать массив байт или BigInteger, но в любом случае потребуется ещё передавать и количество бит числа, поскольку оно может быть не кратно 8.

2)

n

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

3) Циклически сдвиг вправо или влево - это взаимозаменяемы функции. Для 32 бит :

сдвиг_влево => сдвиг_вправо(32-сдвиг_влево);

4) Для сдвига более чем на

p

разрядов нужно получать сдвиг по модулю

p

(остаток деления).

5) В результате получаем примерно такой код на основе представленного

OwenGlendower

:

C#Выделить код

1
2
3
4
5
6
7
8
9
10
11
12

    public static class Helper
    {
        public static uint Shift(this uint value, int n)
        {
            n %= 32;
            if (n == 0 || value == 0) return value;
 
            if (n < 0)
                n += 32;
            return (value << (32 - n)) | (value >> n);
        }
    }

Для числа с произвольным количеством разрядов можно в этом методе заменить входной тип значения на BigInteger и из результата вырезать нужное количество разрядов:

C#Выделить код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

        public static BigInteger Shift(this BigInteger value, int p, int n)
        {
            if (value < 0) throw new ArgumentOutOfRangeException(nameof(value));
            if (p <= 0) throw new ArgumentOutOfRangeException(nameof(p));
 
            n %= p;
            if (n == 0 || value == 0) return value;
 
            if (n < 0)
                n += p;
            BigInteger mask = BigInteger.Zero;
            for (int i = 0; i < p; i++)
            {
                mask <<= 1;
                mask |= BigInteger.One;
            }
 
            return ((value << (p - n)) | (value >> n)) & mask;
        }