Циклический сдвиг в двоичном представлении целого числа на `k` позиций
Даны два положительных целых числа n а также k , выполнить циклический сдвиг двоичного представления n по k позиции.
Круговой сдвиг может быть двух видов:
- Циклический сдвиг влево (перемещение последнего бита в первую позицию при сдвиге всех остальных битов в следующую позицию).
- Круговой сдвиг вправо (перемещение первого бита в последнюю позицию при сдвиге всех остальных битов в предыдущую позицию).
N = 127 (00000000000000000000000001111111)
shift = 3
Left Shift 00000000000000000000001111111000
Right Shift 11100000000000000000000000001111
Идея состоит в том, чтобы выполнить обычный побитовый сдвиг влево или вправо, сначала изолировав последовательность k битов с правой или левой стороны соответственно. Наконец, верните побитовое OR сдвинутого числа с изолированными битами в правильном положении.
Например, рассмотрим n = 127 который 00000000000000000000000001111111 .
Круговой сдвиг вправо на 3:
1. Isolate the 3–bits from the right:
00000000000000000000000001111 111
00000000000000000000000001111 111
000 00000000000000000000000001111
00000000000000000000000000001111
111 00000000000000000000000000000
————————————————————————————————
11100000000000000000000000001111
Круговой сдвиг влево на 3:
1. Isolate the 3–bits from the left:
000 00000000000000000000001111111
000 00000000000000000000001111111
00000000000000000000001111111 000
00000000000000000000001111111000
00000000000000000000000000000 000
————————————————————————————————
00000000000000000000001111111000
Ниже приведена программа на C++ и Java, которая демонстрирует это:
/dev/energy
Сайт о том, как стать программистом и как с этим жить потом
Циклический сдвиг в массиве
Не так давно стартовал очередной курс Java на одном небезызвестном образовательном портале. И вот, моим студентам досталась задача по работе с массивами. Статья в первую очередь для них, но и для интересующихся, конечно же 🙂 Отдельное спасибо alexandr.baykov@gmail.com за комментарий по поводу массива с чётным количеством элементов и чётным размером сдвига. Я переписал алгоритм и обновил статью.
Итак, задача сформулирована следующим образом
Написать метод, которому на вход подается одномерный массив и число n (может быть положительным, или отрицательным), при этом метод должен сместить все элементы массива на n позиций. Для усложнения задачи нельзя пользоваться вспомогательными массивами.
Усложняющее условие было введено потому, что можно решить задачу при помощи разделения массивов. В таком случае решение состоит в том, чтобы «отрезать» от массива кусок длиной n справа или слева (в зависимости от того, как n сравнивается с 0) и «прикрепить» отрезанную часть обратно с другой стороны. Это довольно дешёвый алгоритм, который имеет сложность O(n), но он будет требовать дополнительной памяти для хранения временного массива размера n. Поскольку такое решение самое простое, да и не особенно подходит под условие задачи, то мы перейдём сразу к более сложной алгоритмизации.
Разумеется, после первых подходов многие студенты находят следующее довольно логичное и вполне корректное решение. Оно весьма популярно на различных сайтах, описывающих циклический сдвиг. Суть его в том, что любой сдвиг можно представить в качестве n сдвигов на 1 ячейку. Сдвиг на 1 ячейку довольно просто реализуется циклом. В итоге, если изобразить это Java-методом, получается примерно такой метод:
public static int[] shiftArray(int[] incomingArray, int shift) if(shift != 0) // Любой сдвиг больше длины массива можно оптимизировать до меньшего сдвига
// через деление по модулю
int finalShift;
if (shift > incomingArray.length) shift = Math.abs(shift % incomingArray.length);
>
else finalShift = shift;
>
// в зависимости от знака сдвига движение будет происходить
// слева направо при положительном сдвиге
// справа налево при отрицательном
if (shift > 0) for (int n = 0; n < shift; n++) <
// убираем первый элемент в буфер, а на его место ставим хвостовой элемент
int buffer = incomingArray[0];
incomingArray[0] = incomingArray[incomingArray.length - 1];
// циклично сдвигаем весь массив
for (int j = 1; j < incomingArray.length - 1; j++) incomingArray[incomingArray.length - j] = incomingArray[incomingArray.length - j - 1]; >
// ставим буферный элемент в 1 ячейку
incomingArray[1] = buffer;
>
>
else if (shift < 0) <
for (int i = 0; i > shift; i--) int buffer = incomingArray[incomingArray.length - 1];
incomingArray[incomingArray.length - 1] = incomingArray[0];
for (int j = 1; j < incomingArray.length - 1; j++) incomingArray[j - 1] = incomingArray[j];
>
incomingArray[incomingArray.length - 2] = buffer;
>
>
>
return incomingArray;
>
Хочу отметить, что такое решение имеет место, и оно применимо. Но мы же решаем алгоритмическую задачу, поэтому неплохо бы поговорить о том, какую сложность будет иметь приведенный алгоритм. Если опустить процесс вычислений буферных элементов и обмена ими между ячейками, то сложность алгоритма сводится к O(N * M), где N — размер входного массива, а M — величина сдвига. Очевидно, что для |M| = 1 (т.е. M = -1 или M = 1) сложность снизится до O(N). Это частный случай.
Теперь давайте подумаем, что же тут не так. На самом деле, если мы знаем величину сдвига (а мы её знаем), то вполне можно вычислить, какой элемент будет следующим. Это говорит о том, что можно создать жонглирующий алгоритм следующего вида:
- Получаем нулевой элемент и кладем его в буфер
- Начинаем цикл от 0 до длины массива включительно (это обусловлено тем, что в момент, когда мы дойдём до последнего элемента, он будет помещен в буфер, из которого его надо восстановить на месте нулевого элемента, чем полностью закольцевать сдвиг)
- Дальше мы меняем местами элементы, исходя из размера шага. Например, для шага 3 и массива длиной 7 мы сначала поменяем элементы 0, 3, 6. Затем — 1, 4, 2. И так далее.
Если рассмотреть наборы изменяемых элементов, то мы увидим, что количество таких наборов, внутри которых мы будем итеративно менять местами элементы, будет равно наименьшему общему делителю для размера массива и размера сдвига. К примеру, для массива из 12 элементов при сдвиге 3 мы будем иметь три набора смещаемых элементов
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
- 1, 4, 7, 10
- 2, 5, 8, 11
- 3, 6, 9, 12
4 5 6 7 8 9 10 11 12 1 2 3
Поскольку эти наборы независимы, то при перестановке в них элементов местами мы не нарушим общий порядок следования элементов.
В реализации нужно учитывать и то, что сдвиг может идти как влево, так и вправо.
Теперь мы можем написать реализацию нашего алгоритма
public class moves
public static void main(String[] args) int[] in1 = ;
int[] out1 = moves(in1, -2);
printOut(out1);
int[] in2 = ;
int[] out2 = moves(in2, 2);
printOut(out2);
int[] in3 = ;
int[] out3 = moves(in3, 5);
printOut(out3);
int[] in4 = ;
int[] out4 = moves(in4, 0);
printOut(out4);
>
/**
* Main method, shifts array
* @param incoming - user array
* @param delta - shift value
* @return int[] result array
*/
static int[] moves(int[] incoming, int delta) int currentIndex, movedIndex, buffer;
for (int i = 0; i < greatestCommonDivisor(delta, incoming.length); i++) buffer = incoming[i];
currentIndex = i;
if(delta > 0) while (true) movedIndex = currentIndex + delta;
if (movedIndex >= incoming.length)
movedIndex = movedIndex - incoming.length;
if (movedIndex == i)
break;
incoming[currentIndex] = incoming[movedIndex];
currentIndex = movedIndex;
>
>
else if(delta < 0) while (true) movedIndex = currentIndex + delta;
if (movedIndex < 0)
movedIndex = incoming.length + movedIndex;
if (movedIndex == i)
break;
incoming[currentIndex] = incoming[movedIndex];
currentIndex = movedIndex;
>
>
incoming[currentIndex] = buffer;
>
return incoming;
>
/**
* Simple printout
* @param incoming Array user array
*/
public static void printOut(int[] incomingArray) for(int item: incomingArray) System.out.print(item + " ");
>
System.out.println();
>
/**
* Finding the GCD in recoursive function
* @param a - first element
* @param b - second element
* @return int GCD
*/
static int greatestCommonDivisor(int a, int b)
if (b == 0)
return a;
else
return greatestCommonDivisor(b, a % b);
>
>
Как и в прошлый раз, мы можем пренебречь расчетами индексов. И в конечном итоге мы получаем сложность алгоритма, которая зависит исключительно от длины массива, т.е. O(N). И эта сложность не будет меняться в зависимости от исключительных ситуаций, что как минимум не хуже предыдущего алгоритма, а для сдвигов, больших, чем единица, лучше.
Надеюсь, приведенные измышления будут для Вас полезны. Буду рад критике и комментариям!
Дочитавшим до конца, картинка де мотиватор 🙂
Циклический «сдвиг» массива
Здравствуйте. Может кто-то помочь написать метод, который бы брал массив, допустим, (1,2,3,4,5), и делал из него (5,1,2,3,4)?
Циклический сдвиг елементов массива
Как циклически сдвинуть на заданое значение елементы массива? И еще: как найти индекс последнего.
Не получается сделать циклический сдвиг массива
Осуществите циклический сдвиг массива на к (к вводится с клавиатуры)единиц вправо, если минимальный.
Циклический сдвиг двумерного массива на N элементов влево
Добрый день! Подскажите как модифицировать метод shifting, чтобы он делал циклический сдвиг.
Циклический сдвиг значений компонентов массива влево на k
Помогите,буду очень благодарна! Дан массив целых чисел (i=1, 2, …,n), целое число k (k >.
взять один массив, получить длину, объявить новый массив того же типа и длины, в цикле размерностью длины массива начать перекладывать со сдвигом (сдвиг+i), при достижении конца массива из нового индекса вычитать длину (сдвиг + i — длина массива).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
package javaapplication1; public class JavaApplication1 while(shift>0) { int lastVar = inArr[inArr.length-1]; for(int counter = 0;counterinArr.length;counter++) { int curVal = inArr[counter]; inArr[counter] = lastVar; lastVar = curVal; } shift--; } return inArr; } public static void main(String[] args) { int[] testArr = {1,2,3,4,5}; testArr = shiftArr(testArr,2); for(int i=0; i testArr.length; i++ ) { System.out.print(testArr[i]+" "); } } }
edwin3d, спасибо большое. И есть один вопрос — как это поменять, чтоб оно делало сдвиг не на 1 позицию, а на n позиций?
2TehEagle:
Потрудитесь 5 минут, загрузите отладчик, прочитайте код.
Данный код УЖЕ делает сдвиг на Н позиций.
Вызов
Сдвигает массив на 2 позиции.
Помотрите — метод shiftArr принимает 2 аргумента.
1-й — массив из чисел
2-й — не сколько позиций его надо сдвигать
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
public static int[] shiftArr(int[] inArr,int shift) while(shift>0) { int lastVar = inArr[inArr.length-1]; for(int counter = 0;counterinArr.length;counter++) { int curVal = inArr[counter]; inArr[counter] = lastVar; lastVar = curVal; } shift--; } return inArr; } public static void main(String[] args) { for(int j=1;j10;j++){ int[] testArr = {1,2,3,4,5}; testArr = shiftArr(testArr,j); for(int i=0; i testArr.length; i++ ) { System.out.print(testArr[i]+" "); } System.out.println(); } }
5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1 1 2 3 4 5 5 1 2 3 4 4 5 1 2 3 3 4 5 1 2 2 3 4 5 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
public class Sdvig { public static void main(String. args) { int[] mass = new int[] { 1, 2, 3, 4, 5 }; for (int i : mass) { System.out.print(i + " "); } System.out.println(); new Sdvig().reverse(mass, 2); // кидаем массив и число на которое нужно // сдвинуть for (int i : mass) { System.out.print(i + " "); } } public int[] reverse(int[] input, int sdvig) if (sdvig > input.length int[] output = new int[input.length]; int j = 0; for (int i : input) { output[j++] = i; } int tmp = sdvig; for (int i = 0; i output.length; i++) { if (sdvig > 0) { input[i] = output[output.length - sdvig]; sdvig--; } else { input[i] = output[i - tmp]; } } return input; } }
Сообщение от IVIakCollideR 
IVIakCollideR, вариант со смещением влево не рассмотрен так-же как и в предыдущей реализации. При передаче в метод 0-го сдвига нужно вернуть исходный массив без изменений. А если больше или равен длине массива, то использовать остаток от деления.
Сообщение от Ev_Hyper
При передаче в метод 0-го сдвига нужно вернуть исходный массив без изменений. А если больше или равен длине массива, то использовать остаток от деления.
Сообщение от Ev_Hyper