산술 시프트

Arithmetic shift
2진수 숫자의 오른쪽 산술 시프트 1.최상위 비트의 빈 위치는 원래 MSB의 복사본으로 채워집니다.
2진수 숫자의 왼쪽 산술 시프트가 1입니다.최하위 비트의 빈 위치는 0으로 채워집니다.
다양한 프로그래밍 언어 및 프로세서의 산술 시프트 연산자
언어 또는 프로세서 왼쪽 맞다
ActionScript 3, Java, JavaScript, Python, PHP, Ruby;
C, C++,[1] D, C#, Go, Julia, Swift(서명 형식만)[note 1]		 << >>
아다 Shift_Left [2] Shift_Right_Arithmetic
코틀린 shl shr
표준 ML << ~>>
베릴로그 <<< >>> [주2]
OpenVMS 매크로 언어 @[note 3]
스킴 arithmetic-shift[주 4]
일반적인 리스프 ash
OCaml lsl asr
하스켈 Data.Bits.shift[주 5]
어셈블리, 68k ASL ASR
어셈블리, x86 SAL SAR
VHDL sla[주 6] sra
RISC-V sll,slli[4] sra,srai
Z80 SLA[5] SRA

컴퓨터 프로그래밍에서 산술적 시프트는 시프트 연산자로, 때때로 부호화된 시프트라고 불린다(단, 부호화된 피연산자로 제한되지는 않음).두 가지 기본 유형은 산술적 좌측 시프트와 산술적 우측 시프트입니다.바이너리 숫자의 경우 피연산자의 모든 비트를 이동하는 비트 연산입니다. 피연산자의 모든 비트는 지정된 수의 비트 위치만 이동하면 빈 비트 위치가 채워집니다.논리 시프트에서와 같이 모든 0으로 채워지는 대신 오른쪽으로 이동하면 맨 왼쪽 비트(보통 부호 있는 정수 표현에서의 부호 비트)가 복제되어 빈 위치를 모두 채웁니다(이것은 부호 확장의 일종).

일부 저자는 산술적 및 논리적 이동에 대해 각각 [6]스틱 오른쪽 이동과 제로 채우기 오른쪽 이동이라는 용어를 선호합니다.

산술적 이동은 부호 있는 정수를 2의 거듭제곱으로 곱하거나 나누는 효율적인 방법으로 유용할 수 있습니다.부호 있는 이진수 또는 부호 없는 이진수에서 n비트를 왼쪽으로 이동하면 2를n 곱하는 효과가 있습니다.2의 보완 부호 이진수에서 n비트로 이동하면 2로 나누는n 효과가 있지만, 항상 반올림(음수 무한대 방향)됩니다.이것은 보통 부호 있는 정수 나눗셈(0을 향해 반올림)에서 반올림하는 방식과는 다릅니다.이 불일치로 인해 다수의 [7]컴파일러에 오류가 발생하고 있습니다.

예를 들어 x86 명령 집합에서 SAR 명령(산술 오른쪽 시프트)은 부호화된 숫자를 2의 거듭제곱으로 나누어 음의 [8]무한대로 반올림합니다.그러나 IDIV 명령(부호 분할)은 부호 있는 숫자를 분할하여 0으로 반올림합니다.따라서 SAR 명령은 IDIV를 2개의 명령의 거듭제곱으로 대체할 수 없으며 그 반대도 마찬가지입니다.

형식적 정의

Federal Standard 1037C에서 산술적 이동의 공식 정의는 다음과 같다.

고정 기수 숫자 시스템 및 고정 소수점 표현 시스템에서의 숫자 표현에 적용되는 시프트로, 숫자의 고정 소수점 부분을 나타내는 문자만 이동한다.산술 시프트는 반올림 효과를 제외하고 일반적으로 기수의 양수 또는 음수의 적분승에 숫자를 곱하는 것과 같습니다. 논리 시프트와 산술 시프트를 비교합니다.특히 부동소수점 표현의 경우입니다.

FS 1073C 정의에서 중요한 단어는 "통상"입니다.

산술적, 논리적 좌회전 및 곱셈의 등가성

산술적 좌측 이동은 기수의 (양수, 적분) 거듭제곱(예: 이진수의 경우 2의 거듭제곱)과 같습니다.곱셈 및 산술적 이동은 산술적 오버플로를 트리거할 수 있지만 논리적 이동은 트리거하지 않는다는 점을 제외하면 논리적 좌측 이동도 동일합니다.

산술적 우측 이동과 나눗셈의 불일치

그러나 산술적 오른쪽 이동은 특히 음수 정수의 반올림을 처리하는 데 있어 무의식적인 사람들을 위한 주요 함정입니다.예를 들어, 음의 정수에 대한 일반적인 두 개의 보완 표현에서 -1은 모두 1로 표시됩니다.8비트 부호 있는 정수의 경우, 이것은 111111입니다.1(또는 2, 3, ..., 7)의 산술적 오른쪽 시프트는 다시 -1인 111111을 산출합니다.이는 반올림(음수 무한대 방향)에 해당하지만 일반적인 나눗셈 규칙은 아닙니다.

산술적 오른쪽 시프트는 기수의 (양수, 적분)승으로 나누는 것과 같기 때문에 기수의 거듭제곱으로 나누는 것을 산술적 오른쪽 시프트로 구현함으로써 최적화할 수 있다(시프트기는 나눗셈기보다 훨씬 간단하다).대부분의 프로세서에서 시프트 명령은 분할 명령보다 더 빨리 실행됩니다.)DEC, IBM, Data General, 그리고 ANSI와 같은 회사와 기관의 많은 1960년대와 1970년대 프로그래밍 핸드북, 매뉴얼, 그리고 다른 사양서들이 그러한 잘못된 진술을 합니다.

논리 우측 이동은 양수 또는 부호 없는 숫자에 대해서만 기수(일반적으로 2)의 거듭제곱으로 나눈 것과 같습니다.산술적 오른쪽 이동은 양의 서명된 숫자에 대한 논리적 오른쪽 이동과 동일합니다.N-1의 보완(보통 2의 보완)에서 음수에 대한 산술적 오른쪽 이동은 기수(보통 2)의 거듭제곱으로 나눗셈과 거의 동일하며, 여기서 홀수에 대해서는 아래쪽으로 반올림한다(보통 0이 아니다).

음수에 대한 산술적 오른쪽 이동은 일부 과거 컴퓨터에서 사용되었던 것처럼 부호 있는 숫자의 보완 표현에서 0을 향해 반올림하는 것과 동일하지만, 이것은 더 이상 일반적으로 사용되지 않습니다.

프로그래밍 언어로 문제 해결

프로그래밍 언어 C에 대한 (1999) ISO 표준은 [10]2의 거듭제곱에 의한 나눗셈의 관점에서 오른쪽 시프트 연산자를 정의합니다.위에서 기술한 비등가성으로 인해, 이 표준은 음의 값을 갖는 부호 숫자의 올바른 이동을 그 정의에서 명시적으로 제외한다.이러한 상황에서 오른쪽 시프트 연산자의 동작을 규정하지 않고, 대신 각 개별 C 컴파일러가 [note 7]음수 값의 올바른 시프트 동작을 정의해야 합니다.

적용들

일관된 반올림이 필요한 응용 프로그램에서는 서명된 값의 산술적 오른쪽 이동이 유용합니다.예를 들어 래스터 좌표를 2의 거듭제곱하여 균일한 간격을 유지하는 다운스케일링이 있습니다.예를 들어 오른쪽 시프트가 1이면 0, 1, 2, 3, 4, 5, ..., 0, 1, 1, 2, 2, ..., 그리고 -1, -2, -3, -4, ...이 -1, -1, -2, -2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -2, ...로 짝수 간격을 유지합니다.반대로 반올림을 0으로 하는 정수 나눗셈은 -1, 0 및 1을 모두 0으로 보내고 대신 -2, -1, -1, -1, 0, 0, 0, 1, 2, ...을 산출합니다. -2는 0에서 불규칙합니다.

메모들

  1. ^ 그 >> C와 C++의 연산자는 반드시 산술적 시프트는 아닙니다.일반적으로 왼쪽에 부호 있는 정수형을 사용하는 경우에는 산술적 시프트에 불과합니다.대신 부호 없는 정수 유형에 사용되는 경우 논리적 이동이 됩니다.
  2. ^ Verilog 산술 오른쪽 이동 연산자는 실제로 첫 번째 피연산자가 서명된 경우에만 산술 이동을 수행합니다.첫 번째 피연산자가 부호 없는 경우 연산자는 실제로 논리적 오른쪽 이동을 수행합니다.
  3. ^ OpenVMS 매크로 언어에서는 두 번째 피연산자가 양의 것인지 음의 것인지에 따라 산술 시프트가 왼쪽인지 오른쪽인지 여부가 결정됩니다.이건 보통 일이 아니다.대부분의 프로그래밍 언어에서 두 방향은 서로 다른 연산자를 가지고 있으며, 연산자가 방향을 지정하며 두 번째 연산자는 암묵적으로 양의 값입니다(Verilog와 같은 일부 언어에서는 음수 값을 부호 없는 양의 값으로 변환해야 합니다).C나 C++ 등 일부 언어에서는 음수 값이 사용되는 경우 동작이 정의되지 않습니다.)[3][page needed]
  4. ^ 스킴 내arithmetic-shift두 번째 피연산자에 따라 왼쪽 및 오른쪽 시프트가 모두 가능하며 OpenVMS 매크로 언어와 매우 유사하지만 R6RS Scheme에 의해 둘 다 추가됩니다.-right그리고.-left변종입니다.
  5. ^ 그Bits하스켈의 수업Data.Bitsmodule은 양쪽을 정의합니다.shift서명된 주장을 받아들여서shiftL/shiftR서명되지 않은 주장을 받아들입니다.이것들은 동형입니다.새로운 정의의 경우 프로그래머가 필요로 하는 것은 두 가지 형태 중 하나뿐이며, 다른 형태는 제공된 형태에 따라 자동으로 정의됩니다.
  6. ^ VHDL 산술 왼쪽 시프트 연산자가 특이합니다.결과의 LSB를 0으로 채우는 대신 원래 LSB를 새로운 LSB로 복사합니다.이것은 산술적 오른쪽 시프트의 정확한 미러 이미지이지만, 연산자의 일반적인 정의는 아니며 2의 거듭제곱과 동일하지 않습니다.VHDL 2008 표준에서는 숫자 해석을 강제하지 않는 인수 유형(BIT_Vector 등)에 대해서는 이 이상한 동작을 변경하지 않고 있습니다만, 서명되지 않은 인수 유형 및 서명되지 않은 인수 유형에 대해서는 'SLA'가 예상대로 동작합니다(즉, 대부분의 위치가 0으로 채워집니다).VHDL의 SLL(Shift Left Logical) 함수는 앞서 언급한 '표준' 산술 시프트를 구현합니다.
  7. ^ C 표준은 C 언어를 하나의 보완 아키텍처 또는 두 개의 보완 아키텍처로 제한하지 않기 위한 것이었다.이와 같이 한 사람의 보완표현과 두 사람의 보완표현의 행동이 다른 경우, 이 기준서는 개별 C 컴파일러가 대상 아키텍처의 행동을 문서화하도록 요구한다.예를 들어 GNU 컴파일러 컬렉션(GCC)의 문서에서는 부호 [11]확장을 사용하는 것으로 동작하고 있습니다.

레퍼런스

상호 참조

  1. ^ "Bit manipulation - Dlang Tour". tour.dlang.org. Retrieved 2019-06-23.
  2. ^ "Annotated Ada 2012 Reference Manual".
  3. ^ HP 2001.
  4. ^ "The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA" (PDF). GitHub. 2019-12-13. pp. 18–20. Retrieved 2021-08-07.
  5. ^ "Z80 Assembler Syntax".
  6. ^ 토마스 R.케인과 앨런 T.셔먼."기퍼드의 암호를 푸는 법"섹션 8.1: "스틱 비트 시프트와 비스틱 비트 시프트"크립톨로지아1997.
  7. ^ Steele Jr, Guy. "Arithmetic Shifting Considered Harmful" (PDF). MIT AI Lab. Retrieved 20 May 2013.
  8. ^ Hyde 1996, § 6.6.2.2 SAR.
  9. ^ 스틸 1977년
  10. ^ ISOIEC9899 1999, § 6.5.7 비트 단위 시프트 연산자.
  11. ^ FSF 2008, § 4.5 정수 구현.

사용된 소스

Public Domain이 문서에는 General Services Administration 문서의 퍼블릭도메인 자료가 포함되어 있습니다.