Есть ли способ выполнить циклический сдвиг бит в C#?
Я знаю, что верно следующее
int i = 17; //binary 10001
int j = i << 1; //decimal 34, binary 100010
Но если вы сдвинетесь слишком далеко, биты отвалятся. Где это происходит, зависит от размера целого числа, с которым вы работаете.
Есть ли способ выполнить сдвиг, чтобы биты вращались на другую сторону? Я ищу одну операцию, а не цикл for.
очень хороший вопрос. Я только что проверил сгенерированный код, и компилятор C# не генерирует код, который использует инструкции поворота ЦП (не то, чтобы архитектура x86 имела их со времен 8086 ...). Какая жалость. C выполняет эту оптимизацию. Также ротации очень важны для задач криптографии и dsp.
Ответы 6
Если вы знаете размер шрифта, вы можете сделать что-то вроде:
uint i = 17;
uint j = i << 1 | i >> 31;
... который будет выполнять циклический сдвиг 32-битного значения.
В качестве обобщения циклического сдвига влево на n бит для переменной b бит:
/*some unsigned numeric type*/ input = 17;
var result = input << n | input >> (b - n);
@The comment, it appears that C# does treat the high bit of signed values differently. I found some info on this здесь. I also changed the example to use a uint.
Поскольку я не знаю C#, выполняют ли операторы сдвига арифметические или логические сдвиги? Если это арифметика, то этот алгоритм нельзя использовать для 64-битных целых чисел со знаком.
Так что, возможно, оба типа int и var должны иметь префикс беззнакового модификатора, если, конечно, C# это позволяет.
В любом случае, вращение битов имеет смысл только с целыми числами без знака.
@ LasseV.Karlsen: Я бы не согласился с этим. GetHashCode возвращает (подписанный) int, и если вы хотите равномерно распределять хэш-коды, используя полные 32 бита этого (что может включает ротацию битов), знак на самом деле не имеет значения - и, очевидно, мешает ротации бит .
Если вы используете i << n | i >> -n (или, альтернативно, i << n | i >> ~n >> 1), вам не нужно изменять значение b для разных размеров. Теоретически это могло быть и немного быстрее, но не настолько, чтобы вы когда-либо заметили.
@ O.R.Mapper верно, но на самом деле GetHashCode следует рассматривать как uint, но он должен быть int, чтобы соответствовать требованиям CLS. Если вы собираетесь немного повозиться с ним, действительно имеет смысл либо привести к uint, либо замаскировать знаковый бит. В большинстве случаев использования результата вам все равно потребуется замаскировать знаковый бит (например, индексация по модулю).
Также следует отметить, что второй пример никогда не будет работать сам по себе - вы используете необъявленную переменную «i» вместо предполагаемого «input». (И если вы переключите его на ввод, компилятор все равно превратит его в обычный int, а не в uint).
Странно, что для этого потребовалось бы даже такое количество кода, учитывая тот факт, что и ror, и rol являются частью голого набора инструкций процессора x86. Разве они не могли просто сделать инструкцию <<> или что-то для этого на C#?
Год назад я внедрил MD4 для своей дипломной работы. Вот моя реализация кругового битового сдвига с использованием UInt32.
private UInt32 RotateLeft(UInt32 x, Byte n)
{
return UInt32((x << n) | (x >> (32 - n)));
}
Эти две функции идеально подходят для вращения битов 1/2 слова, как и справка о том, как это сделать:
static public uint ShiftRight(uint z_value, int z_shift)
{
return ((z_value >> z_shift) | (z_value << (16 - z_shift))) & 0x0000FFFF;
}
static public uint ShiftLeft(uint z_value, int z_shift)
{
return ((z_value << z_shift) | (z_value >> (16 - z_shift))) & 0x0000FFFF;
}
Было бы легко расширить его до любого заданного размера.
Самым известным приложением является решение проблемы Иосифа Флавия (как описано в Конкретной математике, см. http://oeis.org/A006257). По сути, это головоломка без очевидных приложений. В это видео я продемонстрировал связь между проблемой Иосифа Флавия второго порядка и полными сбалансированными деревьями. Это все еще не приложение, но оно немного движется в правильном направлении.
Начиная с .NET Core 3.0 и выше есть BitOperations.RotateLeft() и BitOperations.RotateRight(), так что вы можете просто использовать что-то вроде
BitOperations.RotateRight(12, 3);
BitOperations.RotateLeft(34L, 5);
В предыдущих версиях вы можете использовать BitRotator.RotateLeft() и BitRotator.RotateRight() в Microsoft.VisualStudio.Utilities.
Методы расширения для вращения битов uint (32 бита):
public static uint ROR(this uint x, int nbitsShift)
=> (x >> nbitsShift) | (x << (32 - nbitsShift));
public static uint ROL(this uint x, int nbitsShift)
=> (x << nbitsShift) | (x >> (32 - nbitsShift));
Где можно было бы использовать операцию этого типа? Какова цель выполнения Bit Rotate? Мне не нужно знать, но я просто заинтересован в расширении знаний. Кит