순환 이동

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : "Circular shift"– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2009년 12월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

왼쪽과 오른쪽으로의 8원소 원형 이동 행렬

조합 수학에서, 순환 이동은 마지막 엔트리를 첫 번째 위치로 이동시키고, 다른 엔트리를 다음 위치로 이동시키거나, 또는 역연산을 수행함으로써 태플의 엔트리를 재배치하는 연산이다.순환 이동은 순환 순열의 특별한 종류이며, 순환 순열은 다시 특별한 종류의 순열이다.형식적으로 원형 이동은 다음과 같이 태플의 n개 엔트리의 치환 θ이다.

${\displaystyle }$모든 엔트리에 대해 i = 1, ..., n ulul (${\displaystyle （}$ ${\displaystyle \mathrm{i}}$+ 1$$ {$displaystyle$\ $equiv$ ( i ) \ equiv ( $i$+ 1) ${\displaystyle \}}$ modulo n

또는

${\displaystyle }$i${\displaystyle }$= 1, ${\displaystyle ...,}$ n의 $모든$ 엔트리에 대해${\displaystyle i}$ -$$ )${\displaystyle }$\$displaystyle$\ $equiv$ ( i ) \ equiv ( $i$- 1 ) modulo n 。

주어진 태플에 반복적으로 원형 시프트를 적용한 결과를 태플의 원형 시프트라고도 합니다.

예를 들어, 연속적으로 4 태플(a, b, c, d)에 원형 시프트를 적용하면,

• (d, a, b, c),
• (c, d, a, b),
• (b, c, d, a),
• (a, b, c, d)(원래 4 태플),

그리고 그 순서는 반복됩니다.따라서 이 4개의 태플은 4개의 뚜렷한 원형 시프트를 가지고 있습니다.그러나 모든 n개의 튜플이 n개의 뚜렷한 원형 시프트를 갖는 것은 아닙니다.예를 들어 4-튜플(a, b, a, b)은 2개의 뚜렷한 원형 이동만을 가집니다.일반적으로 n-튜플의 원형의 이동 수는 튜플의 엔트리에 따라 n의 임의의 제수가 될 수 있다.

컴퓨터 프로그래밍에서, 원형 이동이라고도 하는 비트 회전은 피연산자의 모든 비트를 이동하는 비트 연산입니다.산술적 이동과 달리 순환 이동은 숫자의 부호 비트를 유지하거나 부동 소수점 숫자의 지수와 유의점을 구분하지 않습니다.논리 시프트와 달리 빈 비트 위치는 0으로 채워지지 않고 시퀀스에서 벗어난 비트로 채워집니다.

순환 교대제 실시

순환 시프트는 비트시퀀스를 가능하게 하기 위해 암호학에서 자주 사용됩니다.유감스럽게도 C를 포함한 많은 프로그래밍 언어에는 거의 모든 프로세서가 ROL 및 ROR를 사용하고 있지만 순환 시프트를 위한 연산자 또는 표준 함수가 없습니다.다만, 일부의 컴파일러는, 고유의 기능을 사용해 프로세서의 명령에 액세스 할 수 있습니다.또한 표준 ANSI C 코드의 일부 구조는 컴파일러에 의해 그러한 명령을 가진 CPU 상의 "회전" 어셈블리 언어 명령에 최적화될 수 있다.대부분의 C 컴파일러는 다음과 같은 이디옴을 인식하여 단일 32비트 회전 ^[1][2]명령으로 컴파일합니다.

/* * C의 시프트 연산은 다음과 같은 시프트 값에 대해서만 정의됩니다. * 음수가 아니고 크기(값)보다 작음* CHAR_BIT. * 비트와 (&)와 함께 사용되는 마스크는 정의되지 않은 동작을 방지합니다. * 시프트 카운트가 0 또는 >=인 경우 부호 없는 int의 폭. */  #실패하다 < stdint >h>// uint32_t의 경우 int 크기에 관계없이 32비트 폭의 로테이션을 가져옵니다. #실패하다 <고객명>님.h>// CHAR_B의 경우IT부문  uint32_t 로틀32 (uint32_t 가치, 서명되어 있지 않다 인트 세어보세요) {     컨스턴트 서명되어 있지 않다 인트 마스크 = CHAR_BIT * 크기(가치) - 1;     세어보세요 &= 마스크;     돌아가다 (가치 << > 세어보세요)   (가치 >> (-세어보세요 & 마스크)); }  uint32_t 로트32 (uint32_t 가치, 서명되어 있지 않다 인트 세어보세요) {     컨스턴트 서명되어 있지 않다 인트 마스크 = CHAR_BIT * 크기(가치) - 1;     세어보세요 &= 마스크;     돌아가다 (가치 >> 세어보세요)   (가치 << > (-세어보세요 & 마스크)); } 

이 안전하고 컴파일러 친화적인 구현은 John Reger에 ^[3]의해 개발되었으며 Peter Codes에 ^[4][5]의해 더욱 다듬어졌다.

보다 단순한 버전은 종종 볼 수 있습니다.count는 1 ~ 31비트 범위로 제한됩니다.

uint32_t 로틀32 (uint32_t 가치, 서명되어 있지 않다 인트 세어보세요) {     돌아가다 가치 << > 세어보세요   가치 >> (32 - 세어보세요); } 

이 버전은 위험합니다.count는 0 또는 32 입니다.C 언어 표준에서는 정의되지 않은 동작인 32비트 시프트를 요구합니다.단, 대부분의 마이크로프로세서가 구현되어 있기 때문에 동작하는 경향이 있습니다.value >> 3232비트 시프트(0을 생성) 또는 0비트 시프트(원본을 생성) 중 하나로서value어느 쪽이든 이 어플리케이션에서 올바른 결과를 얻을 수 있습니다.

예

비트 시퀀스 0001 0111이 1비트 위치의 순환 시프트를 받는 경우...(아래 이미지 참조)

왼쪽의 출력: 0010 1110 좌측 원형 시프트.

오른쪽은 1000 1011입니다. 우측 순환 시프트.

비트 시퀀스 1001 0110이 다음 조작을 받는 경우:

적용들

순환 코드는 코드 워드의 순환 이동이 항상 다른 코드 워드를 생성하는 속성을 가진 블록 코드의 일종입니다.이것에 의해, 다음의 일반적인 정의가 가능하게 됩니다.알파벳 δ 위의 문자열 s는 s의 원형 이동 집합을 나타내고, 문자열 집합 L은 L의 모든 원형 이동 집합을 나타냅니다. 만약 L이 순환 코드라면, 이것은 L이 순환 언어일 때 필요한 조건입니다.운영 교대(L)는 형식 언어 이론에서 연구되었습니다.예를 들어 L이 문맥이 없는 언어인 경우 shift(L)는 다시 ^[6][7]문맥이 없는 언어입니다.또, 길이 n의 정규식으로 L을 기술하면,^[8] 시프트(L)를 기술하는 길이 O(n³)의 정규식이 있다.

「 」를 참조해 주세요.

• 배럴 시프터
• 순환제
• 린든어
• 목걸이 - 태플과 같은 물체이지만 원형 이동이 동등한 것으로 간주됩니다.

레퍼런스