Feb 28 2019 at 16:27

Циклический сдвиг для 2^p разрядного числа на основе битовых операций

Invite pending

Постановка задачи

Возникла в ходе работы необходимость произвести циклический сдвиг 2^p разрядного числа на n байт. На просторах интернета была найдена формула (Уоррен Генри — Алгоритмические трюки для программистов — 2014):

Эта формула ориентированна исключительно на 32 битные переменные, следовательно int хорошо бы подошел под эту задачу, так как имеет в себе необходимые 32 бита, но динамичность параметра p накладывала ограничения на размер типа.

Решение

var num = ....;
var offcet = ....; //n
var nearestDegree = (int)Math.Log(num, 2);
                var bitCount = nearestDegree + 1; 

                var maxNum = (int)Math.Pow(2, bitCount) - 1;

                var realOffset = Offset - Offset / bitCount * bitCount;

                var resR = (num >> realOffset) | ((num << (bitCount - realOffset)) & (maxNum)); //Правый
                 var resL = ((num << realOffset) & (maxNum)) | (num >> (bitCount - realOffset));//Левый

Почему так?

Первым, что пришло в голову — это заменить 32 в формуле на количество P полученное из логарифма.

var num = ....;
var offcet = ....; //n
var nearestDegree = (int)Math.Log(num, 2); 
                var bitCount = nearestDegree + 1; //  в логарифме присутствует степень = 0
//которую необходимо учесть для получения кол-ва бит
                var res = (num >> offset) | (num << (bitCount - offset) );

Но сразу же возникла проблема: хоть мы и урезали P, но фактическую длину int урезать мы не можем… Или можем?

Вспоминая основы алгебры логики, на ум приходит операция: && (and). Если мы получим максимальное число, которое вмещает себя 2^p бит и умножим это на полученное число в ходе сдвига влево (Только там биты не занулятся из-за большей разрядности), то излишние биты просто занулятся… Profit.

                var maxNum = (int)Math.Pow(2, bitCount) - 1; // получаем число уже для большей
 //вместимости и просто отнимаем единичку для соответствия 2^p
                var resR = (num >> offset) | ((num << (bitCount - offset)) & (maxNum)); //

И у этого кода есть проблемы, из-за bitCount — offset, в один прекрасный момент, offset может превысить bitCount и тогда неточность обеспечена. Решается это за счет:

var realOffset = Offset - Offset / bitCount * bitCount;

Сдвиг — циклический, а следовательно можно отбросить целое число оборотов (Offset/bitCount должна вернуть int [div operation]).

Hubs: