틈틈이 C를 배우려고 노력해 왔는데, 다른 언어(C#, Java 등)도 같은 개념(그리고 종종 같은 연산자)을 가지고 있습니다 ...
제가 궁금한 것은 핵심 수준에서 비트 시프트(비트 시프트
, 비트 시프트
, 비트 시프트
)가 무엇을 하고, 어떤 문제를 해결하는 데 도움이 될 수 있으며, 어떤 문제가 숨어 있습니까? 다시 말해, 비트 시프트의 모든 장점을 담은 완전 초보자 가이드입니다.
비트 이동 연산자는 이름에서 알 수 있듯이 비트 이동을 수행합니다. 비트를 이동합니다. 다음은 다양한 시프트 오퍼레이터에 대한 간략한(또는 그다지 간략하지 않은) 소개입니다.
<<
는 왼쪽 시프트 연산자이며, 논리 및 산술 시프트의 요구를 모두 충족합니다.이러한 모든 연산자는 정수 값(int
, long
, short
및 byte
또는 char
)에 적용할 수 있습니다. 일부 언어에서는 int
보다 작은 데이터 유형에 시프트 연산자를 적용하면 피연산자의 크기가 자동으로 int
가 되도록 조정됩니다.
'<<<`는 중복되므로 연산자가 아니라는 점에 유의하십시오.
또한 C와 C++는 오른쪽 시프트 연산자를 구분하지 않습니다. 이들은 >>
연산자만 제공하며, 오른쪽 이동 동작은 부호화된 유형에 대해 정의된 구현입니다. 나머지 답변은 C# / Java 연산자를 사용합니다.
(gcc 및 clang/LLVM을 포함한 모든 주류 C 및 C++ 구현에서 부호화된 유형에 대한 >>
는 산술 연산입니다. 일부 코드는 이를 가정하지만 표준이 보장하는 것은 아닙니다. 하지만 '정의되지 않은' 것은 아니며, 표준에서는 구현이 어떤 식으로든 이를 정의하도록 요구합니다. 그러나 음의 부호가 있는 숫자의 왼쪽 이동은 정의되지 않은 동작(부호 있는 정수 오버플로)입니다. 따라서 산술적 오른쪽 이동이 필요한 경우가 아니라면 일반적으로 부호 없는 유형으로 비트 이동을 수행하는 것이 좋습니다.)
정수는 메모리에 일련의 비트로 저장됩니다. 예를 들어 숫자 6은 32비트 int
로 저장됩니다:
00000000 00000000 00000000 00000110
이 비트 패턴을 왼쪽으로 한 위치 이동(6 << 1
)하면 숫자 12가 됩니다:
00000000 00000000 00000000 00001100
보시다시피 숫자가 한 자리씩 왼쪽으로 이동했고 오른쪽의 마지막 자리는 0으로 채워져 있습니다. 왼쪽으로 이동하는 것은 2의 거듭제곱과 같다는 것을 알 수 있습니다. 따라서 6 < 1
은 6 * 2
에 해당하고 6 < 3
은 6 * 8
에 해당합니다. 좋은 최적화 컴파일러는 가능하면 곱셈을 시프트로 대체합니다.
이것은 순환 시프트가 아니니라는 점에 유의하세요. 이 값을 한 위치 왼쪽으로 이동합니다(3,758,096,384 << 1
):
11100000 00000000 00000000 00000000
는 3,221,225,472가 됩니다:
11000000 00000000 00000000 00000000
끝에서 '이동'된 숫자가 손실됩니다. 감싸지 않습니다.
논리적 오른쪽 시프트는 왼쪽 시프트와 반대입니다. 비트를 왼쪽으로 이동하는 대신 단순히 오른쪽으로 이동합니다. 예를 들어 숫자 12를 이동합니다:
00000000 00000000 00000000 00001100
를 한 위치 오른쪽으로 이동하면(12 &t; 1
) 원래 6을 되찾을 수 있습니다:
00000000 00000000 00000000 00000110
따라서 오른쪽으로 이동하는 것은 2의 거듭제곱으로 나누는 것과 같다는 것을 알 수 있습니다.
그러나 시프트는 손실된 비트를 되찾을 수 없습니다. 예를 들어 이 패턴을 이동한다고 가정해봅시다:
00111000 00000000 00000000 00000110
를 왼쪽 4위치(939,524,102 < 4
)로 이동하면 2,147,483,744가 됩니다:
10000000 00000000 00000000 01100000
그리고 다시 이동((939,524,102 << 4) >> 4
)하면 134,217,734가 됩니다:
00001000 00000000 00000000 00000110
비트가 손실되면 원래 값을 되돌릴 수 없습니다.
산술적 오른쪽 시프트는 논리적 오른쪽 시프트와 똑같지만 0으로 패딩하는 대신 가장 중요한 비트로 패딩한다는 점이 다릅니다. 이는 가장 중요한 비트가 부호 비트, 즉 양수와 음수를 구분하는 비트이기 때문입니다. 가장 중요한 비트로 패딩함으로써 산술적 오른쪽 시프트는 부호를 보존합니다.
예를 들어 이 비트 패턴을 음수로 해석하면 다음과 같습니다:
10000000 00000000 00000000 01100000
는 -2,147,483,552라는 숫자가 됩니다. 이를 산술 시프트를 사용하여 오른쪽 4자리로 이동하면(-2,147,483,552 > 4) 다음과 같은 결과가 나옵니다:
11111000 00000000 00000000 00000110
또는 -134,217,722라는 숫자가 됩니다.
따라서 논리적 우변환이 아닌 산술적 우변환을 사용하여 음수의 부호를 보존했음을 알 수 있습니다. 그리고 다시 한 번, 2의 거듭제곱으로 나눗셈을 수행하고 있음을 알 수 있습니다.
1바이트가 있다고 가정해 봅시다:
0110110
왼쪽 비트 시프트 하나만 적용하면 됩니다:
1101100
가장 왼쪽의 0이 바이트 밖으로 이동하고 바이트의 오른쪽 끝에 새로운 0이 추가되었습니다.
비트는 롤오버되지 않고 버려집니다. 즉, 1101100을 왼쪽으로 시프트했다가 오른쪽으로 시프트해도 동일한 결과를 다시 얻지 못합니다.
왼쪽으로 N을 이동하는 것은 2를 곱하는 것과 같습니다.
오른쪽으로 N만큼 이동하는 것은 (ones; complement를 사용하는 경우) 2N로 나눈 후 0으로 반올림하는 것과 같습니다.
비트 시프팅은 2의 거듭제곱으로 작업하는 경우 엄청나게 빠른 곱셈과 나눗셈에 사용할 수 있습니다. 거의 모든 저수준 그래픽 루틴은 비트 시프팅을 사용합니다.
예를 들어, 예전에는 게임에 모드 13h(320x200 256색)를 사용했습니다. 모드 13h에서는 비디오 메모리가 픽셀당 순차적으로 배치되었습니다. 즉, 픽셀의 위치를 계산하려면 다음과 같은 수식을 사용해야 했습니다:
memoryOffset = (row * 320) + column
당시에는 속도가 중요했기 때문에 비트 시프트를 사용하여 이 작업을 수행했습니다.
하지만 320은 2의 거듭제곱이 아니므로 이 문제를 해결하려면 더하면 320이 되는 2의 거듭제곱이 무엇인지 알아내야 합니다:
(row * 320) = (row * 256) + (row * 64)
이제 이를 좌변환으로 변환할 수 있습니다:
(row * 320) = (row << 8) + (row << 6)
최종 결과는 다음과 같습니다:
memoryOffset = ((row << 8) + (row << 6)) + column
이제 이전과 동일한 오프셋을 얻지만 값비싼 곱셈 연산 대신 두 비트 시프트를 사용합니다... x86에서는 다음과 같습니다(참고, 어셈블리를 해본 지 오래되었습니다(편집자 주: 몇 가지 실수를 수정하고 32비트 예제를 추가했습니다)):
mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]
; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov
합계: 이 타이밍을 가진 고대 CPU에서 28 사이클.
Vrs
mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6; 2
shl di, 8; 2
add di, ax; 2 (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]
동일한 고대 CPU에서 12주기.
예, CPU 사이클을 16회 줄이려면 이렇게 열심히 노력해야 합니다.
32비트 또는 64비트 모드에서는 두 버전 모두 훨씬 더 짧고 빨라집니다. 인텔 스카이레이크(http://agner.org/optimize/ 참조)와 같은 최신 아웃오더 실행 CPU는 하드웨어 배율이 매우 빠르기 때문에(낮은 지연 시간과 높은 처리량) 이득이 훨씬 작습니다. AMD 불도저 제품군은 특히 64비트 멀티플라이의 경우 약간 느립니다. 인텔 CPU와 AMD Ryzen의 경우, 2교대는 지연 시간은 약간 낮지만 멀티플라이보다 더 많은 명령어를 처리하므로 처리량이 낮아질 수 있습니다:
imul edi, [row], 320 ; 3 cycle latency from [row] being ready
add edi, [column] ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready.
vs.
mov edi, [row]
shl edi, 6 ; row*64. 1 cycle latency
lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency
add edi, [column] ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready.
컴파일러가 이 작업을 대신 수행합니다: gcc, clang 및 MSVC가 모두 return 320*row + col;
]2를 최적화할 때 shift+lea를 사용하는 방법을 확인하세요.
여기서 주목해야 할 가장 흥미로운 점은 x86에는 작은 왼쪽 이동과 추가를 동시에 수행할 수 있는 시프트 앤 애드 명령어(LEA
)가 있으며, 성능은 add
명령어와 같다는 점입니다. ARM은 훨씬 더 강력합니다. 모든 명령어의 피연산자 하나를 무료로 왼쪽 또는 오른쪽으로 이동할 수 있습니다. 따라서 2의 거듭제곱으로 알려진 컴파일 시간 상수로 스케일링하는 것이 곱하기보다 훨씬 더 효율적일 수 있습니다.
현대에는 비트 시프트를 사용하여 두 개의 8비트 값을 16비트 정수로 저장하는 것이 더 유용할 수 있습니다. 예를 들어, C#에서:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
C++에서는 두 개의 8비트 멤버가 있는 구조체
를 사용하는 경우 컴파일러가 이 작업을 수행해야 하지만, 실제로는 항상 그렇지는 않습니다.
저급 프로그래밍 등 기본적인 하드웨어 또는 임베디드 운영, 비트 시프트 (shift), 비트 있다. 심지어 일부 이진 파일 포맷의 경우 읽기 위해 사양명세를 디바이스입니다 볼 수 있습니다, 단어 및 dword 바이트입니다 비사양 바이트입니다 비트필드스 정렬되고 줄바꿈할 분할하고 있는 다양한 값을 포함하고 있다. 이러한 비트 필드를 액세스하면 읽기 / 쓰기를 위한) 가 가장 일반적인 사용.
16 비트 그래픽 프로그래밍 픽셀입니다 표현되는 것은 단순한 실수 예는 다음과 같다.
bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Blue | Green | Red |
이 값을 얻을 수 있는 녹색 emc. 할 것입니다.
#define GREEN_MASK 0x7E0
#define GREEN_OFFSET 5
// Read green
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
녹색 값을 얻기 위해 만 5, 10 시에 끝나며 오프셋할 시작하는 사용해야 합니다. (즉 6 비트 긴), 전체 16 비트 (bit) 가 있는 것은 오직 픽셀입니다 대해 적용했을 때 마스크 비트를 저희에게는힘과 관심이 모아지고 있다.
#define GREEN_MASK 0x7E0
0 000 011 111 100 000, 즉 적절한 마스크는 0x7e0 있는 binary) 은 2016년 자릿수를).
uint16_t green = (pixel & GREEN_MASK) ...;
마스크할 적용하십시오 및 연산자 (&), 사용할 수 있습니다.
uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;
빠르게 변하는 일반적인 곱셈, 디비전 2 의 힘을 통해 약어입니다 사용하고 있다.
i <<= x; // i *= 2^x;
i >>= y; // i /= 2^y;
흔히 사용되는 비트 등이 낮은 수준의 그래픽 프로그래밍. 예를 들어 특정 색상 값 인코딩되지 픽셀입니다 있는 32 비트 말을해야합니다.
Pixel-Color Value in Hex: B9B9B900
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000
같은 것을 통해, 이진 값 레이블된 seabreeze 단면에는 대한 전반적인 이해가 어떤 색상 부품.
Red Green Blue Alpha
Pixel-Color Value in Binary: 10111001 10111001 10111001 00000000
예를 들어 우리가 원하는 값을 # 39 의 말하도다 let& afaq 그린 이 픽셀입니다 색상. 로 간편하게 얻을 수 있는 가치 있는 우리는 마스킹과 및 이동.
우리의 마스크:
Red Green Blue Alpha
color : 10111001 10111001 10111001 00000000
green_mask : 00000000 11111111 00000000 00000000
masked_color = color & green_mask
masked_color: 00000000 10111001 00000000 00000000
&Amp 사용할 수 있는 논리 ',' 연산자입니다 값만 마스크는 1 유지됩니다. 마지막 한가지 이제 해야 하는 것이 올바른 의해 모든 x 16 비트 정수 값이 그 곳에서 오른쪽으로 옮기는 내려받습니다 (논리 오른쪽 shift) .
green_value = masked_color >>> 16
Pixels-Green Value in Hex: 000000B9
Pixels-Green Value in Binary: 00000000 00000000 00000000 10111001
Pixels-Green Value in Decimal: 185
이것은 종종 사용되는 이미지 포맷은 jpg, png 'like' 인코딩 또는 디코딩 ',' '.'.
나는 데 쓰는 요령을 전용, 시험 / 시험을 볼 수도 있다.
n ':' n = 1. n = 1 ',' n< <. n/2 ':' n = 2. n = 1 ',' n> >. 3. 있는지 확인하는 n 은 2 의 거듭제곱 (1.2,4.8.): (n &, 체크 '! (n-1)) ' 4. , X&l 가져오는 sup> th< /sup>;; 다소 'n': 'n = (1 < <; x) ' 5. X 는 또는 홀수입니다 있는지 확인하는 것이다. 1 = 0 ',' x& (짝수) 6. 이 , , sup> th< n&l 전환하십시오 /sup>; 비트 x: 'x ^ (1<, <, n)'
참고로, 비트 수를 shift+ctrl mod& # 39 는 Java 구현, 크기는 세로 x 소스.
예를 들면 다음과 같습니다.
(long) 4 >> 65
는 2. 모든 것을 기대할 수 있는 비트 오른쪽에 두는 쪽으로 65 배 아웃하지만 it& # 39 의 사실상 제로 아니하였으매 avamer 다음과 같다.
(long) 4 >> (65 % 64)
,,, 그리고 > > < 마찬가지입니다 < > > >;;). 다른 언어로 아웃해야 시도한 적이 없습니다.
Python 에서 몇 가지 유용한 비트 운영 / 조작. Python 에서 @Ravi 구현됩니까 프라카시 대답.
# basic bit operations
# int to bin
print(bin(10))
# bin to int
print(int('1010',2))
# multiplying x with 2 .... x**2== x << 1
print(200<<1)
# dividing x with 2 .... x /2 == x >> 1
print(200>>1)
# modulo x with 2 .... x%2 == x&1
if 20&1==0:
print("20 is a even number")
# check if n is power of 2 : check !(n & (n-1))
print(not(33 &(33-1)))
# getting xth bit of n : (n>>x)&1
print((10>>2)&1) # bin of 10==1010 and 2nd bit is 0
# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2))
Php 는 겨우 32 비트 버전의 Windows 플랫폼에서 사용할 수 있는 것을 염두에 두어야 합니다.
예를 들어, < < shift+ctrl 신앙이니라 있습니다. 또는 > >; 의해, 결과는 31 비트 이상의 오네스펙터블. 일반적으로 원래의 수가 될 수 있어 정말 까다로운 반환되었습니다, 대신 제로 버그.
물론 사용할 경우 64 비트 버전은 PHP (unix), 변화하는 이상 늘어난 63 비트임을 피해야 합니다 하지만, 예를 들어, MySQL 은 호환성 문제 때문에 64-비트 BIGINT 없어야 합니다.
업데이트: Php 7 에서 Windows, php 는 정수 전체 64bit 마침내 사용할 수 있다.