Бит круговой сдвиг - PullRequest
Новая
       12

Бит круговой сдвиг

0 голосов
/ 28 апреля 2019

В настоящее время я учусь побитовым операциям, и мне поручено сделать 4-битное целое число с левым поворотом.

Мой код для 4-битного поворота влево равен 

private static int BITS_IN_INTEGER = 4;

private static int leftRotate(int x, int n) {
  return (x << n) | (x >> (BITS_IN_INTEGER - n));
}

Я хочу сделать 4-битный круговой сдвиг, чтобы сохранить его как 4-битный после поворота, но не могу понять, как он работает.

Пример: 10 (1010) после поворота влево на 1 битдайте мне 5 (0101), но это даст мне значение 21, которое больше, чем мой 4-разрядный.

Любая помощь, которая поможет мне понять эту проблему, будет высоко оценена!

1 Ответ

3 голосов
/ 28 апреля 2019

Если я вас правильно понял, вы хотите

  • эмулирует целые числа с BITS_IN_INTEGER многими битами вместо 32 бит.
  • сделать поворот на такое эмулируемое целое число

В настоящее время вы можете делать ротацию, но верхние биты фактического int, которые не являются частью эмулируемого int, могут заканчиваться чем-то отличным от 0. Пример: 

intput x
0000 0000  0000 0000  0000 0000  0000 1100
                                     |____|___, emulated int
result of rotating left by n=2       |    |
0000 0000  0000 0000  0000 0000  0011 0011

Как мы видим, все, что нам нужно сделать, это установить биты выше эмулируемого int (то есть 32 - BITS_IN_INTEGER старших битов) в ноль. Для этого мы используем логические "и" (&). Нам нужна маска с 0 в битах, которые мы хотим установить в ноль (все, что & 0 всегда равно 0) и 1 в битах, которые мы хотим сохранить (все, что & 1 всегда в любом месте). 

  0...0  0011 0011  ←  the result from before
& 0...0  0000 1111  ←  a mask
——————————————————
  0...0  0000 0011  ←  the masked result where unused bits are 0

Для генерации маски вида 0...01...1 с BITS_IN_INTEGER много 1 с мы можем использовать (1 << BITS_IN_INTEGER) - 1. - 1 преобразует 10000 в 01111. 

static int BITS_IN_INTEGER = 4;
static int INTEGER_MASK = (1 << BITS_IN_INTEGER) - 1;

static int leftRotate(int x, int n) {
  return INTEGER_MASK & ((x << n) | (x >>> (BITS_IN_INTEGER - n)));
}
...