Циклический сдвиг для 2^p разрядного числа на основе битовых операций
Ожидает приглашения
Постановка задачи
Возникла в ходе работы необходимость произвести циклический сдвиг 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]).