비트 조작

Bit manipulation
다른 용도는 조작을 참조하십시오.
비트뱅잉과 혼동하지 마세요.

비트 조작은 단어보다 짧은 비트 또는 기타 데이터를 알고리즘으로 조작하는 행위입니다.비트 조작이 필요한 컴퓨터 프로그래밍 태스크에는 저수준 디바이스 제어, 오류 검출 및 수정 알고리즘, 데이터 압축, 암호화 알고리즘 및 최적화가 포함됩니다.대부분의 다른 태스크에서 현대 프로그래밍 언어는 프로그래머가 추상화를 나타내는 비트 대신 추상화를 직접 작업할 수 있도록 합니다.비트 조작을 실행하는 소스 코드에서는 비트 조작이 사용됩니다.AND, OR, XOR, NOT 및 부울 연산자와 유사한 기타 조작도 있습니다.또, 1과 0의 카운트, 1과 0의 하이와 로우의 검색, 비트 설정, 리셋, 테스트, 필드 추출과 삽입, 필드 마스크와 제로, 수집과 스캐트도 가능합니다.err 비트가 지정된 비트 위치 또는 필드에서 송수신됩니다.정수 연산자는 다른 연산자와 함께 비트 연산에 영향을 줄 수도 있습니다.

경우에 따라 비트 조작은 데이터 구조를 루프할 필요성을 없애거나 줄일 수 있으며 비트 조작이 병렬로 처리되기 때문에 여러 배의 속도 향상을 제공할 수 있습니다.

용어.

비트 트위들링과 비트 배싱은 종종 비트 조작과 함께 사용되지만, 때로는 영리하거나 분명하지 않은 비트 조작 방법이나 사용, 또는 지루하거나 어려운 저수준 디바이스 제어 데이터 조작 태스크를 배타적으로 언급하기도 합니다.

비트 트위들링(bit twiddle)이라는 용어는 컴퓨터 오퍼레이터가 컴퓨터 컨트롤을 조정하거나 빙글빙글 돌리면서 조정을 하는 초기 컴퓨팅 하드웨어에서 유래했습니다.컴퓨터 프로그래밍 언어가 진화함에 따라 프로그래머들은 비트 수준 연산을 포함한 모든 데이터 처리를 의미하는 용어를 채택했습니다.

비트 연산

주요 기사: 비트 조작

비트 연산은 1개 이상의 비트 패턴 또는 바이너리 숫자에 대해 각각의 비트 수준에서 동작합니다.이는 중앙 처리 장치(CPU)에서 직접 지원되는 빠르고 원시적인 작업으로 비교 및 계산을 위한 값을 조작하는 데 사용됩니다.

대부분의 프로세서에서 대부분의 비트 연산은 단일 사이클로 분할 및 곱셈 및 분기보다 훨씬 빠릅니다.최신 프로세서는 명령 파이프라인 및 기타 아키텍처 설계 선택사항이 길기 때문에 일반적으로 비트 단위 연산과 동일한 속도로 일부 산술 및 논리 연산을 수행하지만, 비트 단위 연산에서는 리소스 사용이 감소하기 때문에 일반적으로 더 적은 전력을 사용합니다.

비트 조작의 예

어떤 숫자가 2의 거듭제곱인지 판별하려면 개념적으로 정수 나누기를 반복하여 2로 균등하게 나누지 않을 때까지 합니다.남은 계수가 1인 경우 원래 숫자는 2의 거듭제곱이었습니다.비트 연산자와 논리 연산자를 사용하면 true (1) 또는 false(0)를 반환하는 간단한 식이 있습니다.

 부울 isPowerOfTwo = (x != 0) & & ((x & (x - 1)) == 0);

두 번째 방법에서는 2의 거듭제곱이 1비트만 바이너리 표현으로 설정되어 있다는 사실을 사용합니다.

x == 0...010...0 x-1 == 0...001...1 x & (x-1) == 0...000...0

숫자가 0도 아니고 2의 거듭제곱도 아닌 경우 두 자리 이상에 '1'이 있습니다.

x == 0...1...010...0 x-1 == 0...1...001...1 x & (x-1) == 0...1...000...0

인라인 어셈블리 언어 코드가 사용되는 경우 피연산자 내의 1 또는 0의 수를 카운트하는 명령을 사용할 수 있습니다. 정확히 1비트를 가진 피연산자는 2의 거듭제곱입니다.단, 이러한 명령어는 위의 비트 방식보다 지연이 클 수 있습니다.

비트 조작

다음 항목도 참조하십시오.비트 조작 명령어세트

프로세서는 일반적으로 유용한 비트 연산자의 서브셋만 제공합니다.프로그래밍 언어는 대부분의 비트 연산을 직접 지원하지 않으므로 코드화에 관용구를 사용해야 합니다.예를 들어 'C' 프로그래밍 언어는 비트 단위 AND(&), OR(&), XOR(^) 및 NOT(~)만 제공합니다.Fortran은 AND(.and.), OR(.or.), XOR(.neqv.) 및 EQV(.eqv.)를 제공합니다.Algol은 구문 비트필드 추출 및 삽입을 제공합니다.언어가 하드웨어 명령에 직접 매핑되지 않는 비트 연산을 제공하는 경우 컴파일러는 사용 가능한 연산자에서 해당 연산을 통합해야 합니다.

특히 유용한 비트 연산은 머신 워드의 상위 세트비트를 찾기 위해 사용되는 카운트 선행 0입니다.다만,[1] 각종 아키텍처에서는 이름이 다를 수 있습니다.간단한 프로그래밍 언어 관용구는 없으므로 컴파일러 고유 또는 시스템 라이브러리 루틴에 의해 제공되어야 합니다.이 연산자가 없으면 산술 연산의 비대칭 반송 전파로 인해 단어의 높은 비트에 대한 연산을 수행하는 데 비용이 많이 듭니다(첫 번째 set#CLZ 검색 참조).다행히 대부분의 CPU 아키텍처는 1980년대 중반 이후 이를 제공하고 있습니다.수반되는 동작 카운트, POPCOUNT라고도 불리는 동작 카운트도 보통 하드웨어 오퍼레이터로서 제공됩니다.비트 설정, 리셋, 테스트 및 토글과 같은 단순한 비트 연산은 하드웨어 연산자로 제공되는 경우가 많지만 그렇지 않은 경우 쉽게 시뮬레이션됩니다. 예를 들어 (SET R0, 1, LSHFT R0, i; OR x, R0) 비트 i를 오퍼랜드 x로 설정합니다.

프로그래밍 언어에서 관용어로 코드화되고 컴파일러에 의해 합성되어야 하는 보다 유용하고 복잡한 비트 연산에는 다음과 같은 것들이 있습니다.

  • 지정된 비트 위치에서 위로 클리어(단어의 하위 부분을 남김)
  • 지정된 비트 위치에서 아래로 클리어(word의 윗부분을 남김)
  • 저비트 다운으로부터의 마스크(하위 클리어)
  • 하이비트 업으로부터의 마스크(하위 클리어)
  • 비트필드 추출
  • 비트필드 삽입
  • 비트필드의 인접 부분을 머신워드에 분산하거나 워드 내의 다른 비트필드를 비트필드의 인접 부분에 수집하는 비트필드 산란/수집 조작(최근 인텔 PEXT/PDEP 연산자 참조).암호화 및 비디오 인코딩에 사용됩니다.
  • 행렬 반전

일부 산술 연산은 보다 단순한 연산과 비트 연산으로 축소될 수 있습니다.

  • 시프트 덧셈의 순서로 상수를 곱하다

예를 들어 9를 곱하면 카피 오퍼랜드, 시프트 업 3(8 곱하기)이 되고 원래 오퍼랜드에 추가됩니다.

  • 일정하게 분할하여 시프트 타임의 시퀀스로 환원하다

마스킹

주요 기사: 마스크(컴퓨팅)

마스크는 특히 비트필드에서 비트 조작에 사용되는 데이터입니다.

마스크를 사용하여 바이트, 니블, 워드 등의 여러 비트를 단일 비트 단위로 켜거나 끄거나 반대로 설정할 수 있습니다.마스킹의 보다 포괄적인 적용은 운용에 조건부로 적용되었을 때 프레딕션이라고 불립니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 대부분의 인텔 칩에서는 BSR(비트캔 리버스)이지만 새로운 SoC에는 LZCNT(선행 제로 카운트)도 탑재되어 있습니다.

추가 정보

  • Warren, Henry S. (2013). Hacker's Delight (2nd ed.). Addison–Wesley Professional. p. 512. ISBN 978-0321842688.
  • Knuth, Donald E. (2009). The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams (1st ed.). Addison–Wesley Professional. p. 272. ISBN 978-0321580504. (파시클 1a 초안 다운로드 가능)

외부 링크