JavaScript에서 이진계산과 비트 연산자에 대한 포괄적인 입문서
비트 연산자는 학습하는 데 몇 분이 걸리지 만 코드를 더 많은 공간과 시간 효율적으로 만들 수있는 재미있는 방법입니다.
또한 복잡한 문제에 대한 놀랄만큼 간단한 솔루션을 제공 할 수 있습니다.
MDN에 따르면 비트 연산자는 "피연산자를 10 진수, 16 진수 또는 8 진수가 아닌 32 비트 (0과 1) 시퀀스로 처리하는 연산자입니다.
예를 들어, 십진수 9는 1001의 이진 표현을가집니다. 비트 연산자는 이러한 이진 표현에 대한 연산을 수행하지만 표준 JavaScript 수치를 반환합니다."
이것이 의미하는 바는 이 연산자를 사용하여 같은 숫자의 이진 표현인 것처럼 정수를 조작 할 수 있다는 것입니다.
그리고 솔직히, 그들을 치료하지 않거나 이성적으로 생각할 이유가 없습니다.
결국, 2 진수의 '1100'과 10 진수의 '12'는 두 가지 다른 방식으로 같은 양을 나타낼뿐입니다.
따라서 우리의 수에 기존의 수학 연산자(+, -, *, /)를 적용하면 일반적으로 10 진수로 생각하면됩니다.
그러나 이 숫자에 비트 연산자를 적용하면 (>>, <<, &, |, ^, -, ~), 기본 2 (이진) 표현으로 우리의 삶을 훨씬 더 쉽게 상상할 수 있습니다.
제가 2를 언급 할 때 의미하는 것은 무엇입니까? 우리가 10진법에 대해서 이야기함으로써 시작한다면 이해하기가 더 쉬울 것입니다.
10진법이 있기 때문에 우리의 수학 시스템은 10진법을 기반으로 만들어졌습니다. 이것은 문자 그대로 유일한 이유입니다.
10이 본질적으로 특별하다는 수학적 이유는 없습니다. 테이블에있는 10 개의 물체를 보면,
"꽤 무작위적인 양이고, 나는이 양을 기준으로 숫자 체계를 구성해야한다고 생각하지 않는다"고 말할 것입니다.
저의 겸손한 의견으로는 2,3, 그리고 4로 나눌 수 있기 때문에 더 의미가있다.
10진법이 의미하는 바는 각 숫자 0-9에 대해 별도의 기호가 있음을 의미합니다. '0'은 원, '1'은 수직선, '2'는 백조처럼 보입니다.
하지만 9가 지나면 숫자가 9 + 1과 같아지면 심볼이 부족합니다. 우리는 그 모든 것을 하나의 그룹, 즉 '열 (ten)'로 그룹화하고,
우리는 '하나의 열 (ten)'이라고 말합니다. 이 양에 대한 기호가 없으므로 '1'을 사용하여 표현하지만 왼쪽으로 이동합니다.
우리는 '10'과 '0'이 있음을 보여주기 위해 '10'을 사용합니다. 10 개의 10을 갖게되면 '100'으로 그룹화하여 100으로 작성합니다.
그러나 9 + 1에 해당하는 숫자는 특별하지 않습니다. 대신에 5를 중심으로 시스템을 쉽게 만들 수 있습니다.
우리는 0,1,2,3,4를 계산 한 다음 10 점으로 이동합니다. 그러나 10은 '5의 한 그룹'과 같은 것을 의미합니다.
그리고 100은 "(한 그룹으로 된) 다섯 그룹으로 된 다섯 그룹"(일명 25 명)을 의미합니다.
따라서 바이너리는 'base 2'를 기반으로합니다. 이것은 우리가 0,1을, 그리고 나서 10을 의미합니다.
그러나 10은 '2의 한 그룹'을 의미하고 100은 '두 그룹의 두 그룹'(우리 시스템에서 일명 '네')을 의미합니다.
10,000 = (2 그룹 = 2 * 2 * 2 * 2 = 2 4 = '16') 두 그룹의 두 그룹의 두 그룹.
혼란스러워지기 시작했습니다. 단지 10 개가 아니라 2 개의 손가락이 있다고 상상해보십시오. 우리 시스템은 어떻게 다른가요?
우리는 '0, 1, 10'을 셉니다. 그러나 '10 '은 우리가'2 '라고 말할 때 일반적으로 의미하는 바를 의미합니다.
따라서 JavaScript에서 계산을 수행하는 경우 정수 9에 변수를 할당 할 수 있습니다.
정상적인 계산을 수행하는 경우 9를 기본 10에 속한 것으로 생각하는 것이 가장 쉽습니다.
그러나 그 수는 또한 base 2의 비트 1001의 시리즈로 생각할 수 있습니다.
(그리고 "비트"는 한자리 수 또는 위 값입니다 - 위의 숫자에서 개별 0 또는 1 중 하나임).
이것은 이진 연산자가 들어오는 곳입니다. 우리가 숫자 9에 NOT 연산자 (~)를 적용하면 1001에서 0110까지 각 비트를 뒤집습니다.
밑줄 10에서 말하면 ~ 9는 6과 같습니다.
우리가 비트 연산자를 사용한다면, 우리는 10을 기준으로하지 않고 2를 기준으로 숫자를 생각해야합니다.
이것은 ~ 1001이 ~ 1110 (기본 2)과 얼마나 관련되는지 ~ 9가 ~ 6과 관련되는 것보다 쉽게 인식 할 수 있기 때문입니다.
이 점에서 "폴, 브라우저에서 ~ 9을 실행하려했지만 6을 반환하지 않았습니다!"와 같은 말을하는 것일 수도 있습니다.
당신이 그렇게 말하면, 당신이 옳을 것이고, 나는 틀릴 것입니다. 나는 물건을 간단하게 유지하기를 원했습니다. 그러나 설명을 위해 계속 읽으십시오!
문제는 (처음에는 MDN의 정의에 포함 된 부분 중 하나입니다.) 이 숫자가 이진 표현으로 취급되는 한 32 비트로 처리됩니다.
따라서 비트 연산자를 사용하면 9는 000000000000000000000000000001001으로 처리됩니다.
따라서 ~ 9는 1111111111111111111111110110과 같습니다. (올바른 것은 6과 동일하지 않습니다.)
아직도 따라오나요? 우리는 JS에서 바이너리를 완전히 이해하고 있습니다.
그러나 내가 의도적으로 당신에게 은폐하고있는 바이너리 표현의 또 다른 측면이 있습니다.
이것은 현대 컴퓨팅에서 숫자의 음수는 그 숫자의 2의 보수로 표현된다는 것입니다.
이것이 의미하는 것의 복잡함을 놓치고 있을지 모르지만,
내가 이해할 수있는 것은 가장 왼쪽 (가장 큰) 비트 / 자리 값이 음수를 나타내는 데 사용된다는 것입니다. 설명해드릴게요.
일반적으로 숫자 합계를 더하여 합계 값을 찾습니다. 10 진수에서는 1973이 나타내는 값을 각 자리 값을 취하고 그 합계를 더하여 구할 수 있습니다.
그래서 base 10 :
base 10: 1973 = 1000 + 900 + 70 + 3
비슷하게베이스 2에서 1110은 8 + 4 + 2 + 0과 동일합니다. 이것은 base 10에서 14와 동일합니다.
base 2: 1110 = 1000 + 100 + 10 + 0
aka: 14 = 8 + 4 + 2 + 0
그러나 현대 컴퓨팅에서 일련의 가장 왼쪽 비트는 숫자의 음수 구성 요소를 나타내는 데 사용됩니다.
우리가 4 비트 만 작업한다면, 1110은 -8 + 4 + 2를 나타내며, 이는 -2와 같습니다.
예를 들어 -7을 표현하고 싶다면 1001 (-8 + 0 + 0 + 1)을 사용할 수 있습니다.
base 2: 10001 = 1000 + 000 + 00 + 1
aka: -7 = -8 + 0 + 0 + 1
유사하게, 32 비트에서, 가장 왼쪽의 비트가 하나 인 경우 -232를 나타내며, 이는 -4,294,967,296과 동일하다.
우리의 수의 양의 요소로 다른 비트를 사용하면 4,949,729,296보다 작은 절대 값을 갖는다면 원하는 모든 음수를 생성 할 수 있습니다.
조금 더 넓은 범위의 양수를 나타낼 수 있습니다.
32 번째 비트가 우리의 음수 요소로 예약되었으므로 우리가 사용할 수있는 가장 큰 자리 값은 2³¹을 나타냅니다.
31 개의 줄을 연속으로 나열하고 가장 왼쪽 비트를 0으로두면 최대 4,294,967,295 (최대 음수보다 작은 하나)까지 나타낼 수 있습니다.
이 시스템을 사용할 때 비트에 부정적인 변환을 적용하는 의미는 흥미롭다. 패턴을 찾으십시오.
5 비트에서 01001 (8 + 1 = 9)의 음수는 10111 (-16 + 4 + 2 + 1 = -9)입니다.
10011 (-16 + 2 + 1 = -13)의 음수는 01101 (8 + 4 + 1 = 13)입니다.
두 경우 모두 네거티브가 각 비트를 뒤집은 다음 하나를 더함으로써 얻어지는 것을 관찰 할 수 있습니다.
01001 (9)의 음수는 10110 + 1 = 10111이됩니다. 마찬가지로 -13 : -10011 => 01100 + 1 => 01101의 음수를 찾습니다.
아래를 참조하십시오.
Algorithm for finding the negative of a binary number using two's complement:
1) flip the bits
2) then add one
base 2 : neg (01001) = 10110 + 1 = 10111
/ | \
aka: neg (9) = -16 + 4 + 2 + 1 = -9
Javascript에서는 비트 연산자를 사용하여 흥미로운 방식으로 이진수를 빠르게 조작 할 수 있습니다.
이미 음수 연산자 (-)와 NOT 연산자 ()에 대해 논의했습니다. 즉, () 연산자는 각 비트를 반전하고
(-) 연산자는 각 비트를 반전시킨 다음 하나를 더합니다. 다른 것들에 대해 배워봅시다.
그러나 한 가지 중요한 점은 (위에서 언급 한 바와 같이) javascript는 10진수로 사용자와 의사 소통하는 경향이 있다는 것입니다.
따라서 시스템에 입력 한 모든 숫자가 기본 10에 있고 모든 결과가 반환 될 것으로 예상됩니다.
그래서 내가 JavaScript에서 '10010'을 입력하면, JS는 바이너리 / base 2로 해석하지 않을 것입니다.
대신, JS는 그것을 base 10 (1 만 및 10)의 10,010으로 해석합니다.
따라서 이진 연산자를 사용하려면 10진수로 숫자를 써야하고 2진수 연산자를 사용하여 2진수로 처리해야합니다.
1010을 사용하여 비트를 플립하고 0101을 생성하려면 "~ 1010"을 쓸 수 없습니다.
그 대신에 나는 10 번에 해당하는 번호 (이 경우 1010 = 12)를 찾아 그 번호 앞에 내 연산자를 입력해야합니다.
그래서 저는 "~ 12"라고 쓸 것입니다. 결과를 '0101'로 출력하는 대신 JS는 '10'으로 '5'로 인쇄합니다.
대신에 base 2로 코드를 입력하려면 parseInt 연산자를 사용하면됩니다.
ParseInt의 첫 번째 인수는 숫자로 해석 할 문자이고 두 번째 인수는 해석 할 기본 시스템입니다.
따라서 (1010, 2)를 쓰면 '1010'이 기본 2로 해석되고, 이 번호를 나타내는 데이터를 반환합니다.
따라서 ~ 1010을 시뮬레이트하고 싶다면 ~ 12를 쓰는 대신 ~ parseInt (1010, 2)를 쓸 수 있습니다.
ES6 업데이트 : 바이너리 리터럴을 사용하여 이진수를 입력 할 수도 있습니다!
'0b'라고 써서 사용하고자하는 이진수를 씁니다. '0b101'은 10 진수 '5'라는 이진수 '101'을 나타내는 데 사용할 수 있습니다.
아래의 모든 예는 명확성을 위해 base 2 표기법을 사용합니다.
그러나 위의 설명에 따르면, 자바 스크립트 환경에서 이러한 예제를 복제하려면 base 10 숫자를 입력으로 사용하거나 parseInt를 사용해야합니다.
AND, OR 및 XOR 연산자는 두 개의 이진수를 가져 와서 각 자리 비트 (각 자리 값)를 비교하고 각 자리 값에 표시되는 값에 따라 새 숫자를 생성합니다.
예를 들어, 1010 & 1000은 각 숫자의 각 자리 값을 서로 비교합니다. 두 개를 찾으면 출력 위치 값에 1을 생성합니다.
두 개의 0 또는 1과 0을 찾으면 출력의 해당 위치 값에 0을 출력합니다. 따라서 양쪽 입력 비트가 1 인 경우에만 1을 생성 할 수 있습니다.
둘 중 하나가 0이면 0을 생성합니다. 예를 보려면 아래를 스크롤하십시오.
이것은 정상적인 연설에 대한 우리의 직관과 일치해야합니다.
"엘리야가 샌드위치를 먹었고 마키가 샌드위치를 먹었다"고 말하면 두 문장 모두 참 (1)이라면 내 결과 문장은 참 (1)이라고 생각할 수 있습니다.
어느 쪽이든 샌드위치를 먹지 않았다면 우리의 진술은 거짓 (0)입니다. 따라서 1 AND 1 = 1이지만 1 AND 0 = 0입니다.
다음은 작동중인 AND 연산자의 예입니다.
& Operator (AND)
example: 1100 & 1001 = 1000
1100
1001 &
--------
1000
OR 연산자 (|)는 마찬가지로 두 개의 숫자를 비교하여 두 입력 숫자의 각 비트를 정렬하여 출력 숫자를 생성합니다.
두 개의 0이 있으면 해당 비트에 대해 0을 출력합니다. 그러나 1과 0 또는 2가 1이면 1을 출력합니다.
이것은 "너는 미쳐야한다. 그렇지 않으면 너는 바보가되어야한다."와 같은 문장과 비교된다.
하위 조건 중 하나 또는 모두가 참일 경우 스피커가 정확하다고 말합니다.
대담자가 대담하고 어리석지 않은 경우에만 진술이 거짓 (a 0)이라고 말할 것입니다.
| Operator (OR)
example: 1100 | 1001 = 1101
1100
1001 |
--------
1101
마지막으로 XOR 연산자 (^)는 "배타적 논리합"으로 사용됩니다.
이것은 입력 비트 중 하나가 1이고 다른 비트가 0 인 경우에만 주어진 비트에 대해 true를 생성합니다.
이것은 "당신은 아이스크림을 먹을 수 있습니다. 아니면 파이를 먹을 수 있습니다."와 같은 문장입니다.
우리는 이것들 중 단 하나만 사실 일 수 있다고 주장합니다.
둘 다 사실로 밝혀 지거나 둘 다 거짓으로 밝혀지면 발표자의 발언이 잘못되었다고 말할 수 있습니다.
^ Operator (XOR)
example: 1100 ^ 1001 = 0101
1100
1001 ^
--------
0101
이 유용한 연산자는 base 2의 자리 값을 특정 숫자 / 자릿수만큼 이동합니다.
이것이 작동하는 방식은 base 10에 대한 우리의 경험에서 상대적으로 친숙해야합니다. 10을 곱하거나 나누면 값을 바꿀 수 있습니다.
왼쪽 시프트 (<<)부터 시작합시다.
1011 (일명 11)의 이진수를 취하여 <<을 한 번 적용하면 10110 (22)을 생성하면서 한 자리 값만큼 각 숫자를 이동시킵니다.
이것은 base 10 시스템 (3130 * 10 = 31300)에서 10을 곱한 값과 비슷합니다. 두 경우 모두 맨 아래 자리 값에 0을 채 웁니다.
하나의 왼쪽 시프트를 적용하면 우리의 숫자에 2를 곱하는 것과 같습니다. 숫자를 한 번 왼쪽으로 이동하려면 [number] << 1을 씁니다.
추측 할 수 있듯이 기호 오른쪽의 숫자는 번호를 왼쪽으로 옮기고 싶은 횟수를 나타냅니다.
따라서 19 << 2는 19 (10011)의 이진 값을 두 번 왼쪽으로 시프트하려고 함을 의미합니다.
이것은 1001100, 일명 76을 산출 할 것입니다. 이것은 또한 우리의 수를 두 배로 곱하는 것과 같습니다 (일명 2², 일명 4).
<< Operator (Left shift)
example: 1101 << 2 = 110100
오른쪽 시프트 연산자 (>>)는 두 자리 값만큼 오른쪽으로 숫자를 이동합니다.
따라서 010100 >> 2 (일명 20 >> 2) 일 경우 000101 (일명 5)이됩니다. 이것은 우리의 수를 2로 나누는 것과 같습니다.
아래 예제에서, 균등하게 나눌 수없는 01101 (13)과 같은 숫자를 처리하면 나머지는 버려집니다.
우리가 음수를 오른쪽으로 시프팅하는 것이 이상하게 생기는 곳입니다.
2의 보수를 사용하고 1010 (-8 + 0 + 2 + 0 = -6)과 같은 숫자가 있다고 가정합니다.
오른쪽으로 한 번 이동하면 컴퓨터가 가장 왼쪽 비트에 1 또는 0을 채우게할까요?
0을 채우면 왼쪽으로 이동하는 1010은 0101이됩니다. 따라서 -6에서 5로 이동합니다.
이전 작업에서 예상했던 결과와 완전히 다른 점은이 작업이 2로 나누는 것과 비슷하다는 것입니다.
이러한 종류의 작업을 "0 채우기 오른쪽 시프트"라고하며 기호 ">>>"로 나타냅니다.
반면에 가장 왼쪽 비트에 1을 채우면 1010 >> 1이 1101이되어 -8 + 4 + 1 = -3과 같습니다.
이것은 우리가 옳은 시프트를 가질 것으로 예상했던 결과와 더 유사합니다.
이것은 "부호 전파 오른쪽 시프트"로 알려져 있으며 기호 ">>"로 표시됩니다.
그러나 아래에서 관찰 할 수 있듯이 양수 (최하위 비트에 0을 가짐)로 작업 할 경우 두 부호가 모두 0으로 채워지고 동일한 결과가 나타납니다.
>> (Sign-Propagating Right shift)
example1: 110100 >> 2 = 111101
example2: 0101 >> 2 = 0001
배교 대상 :
>>> (Zero-Fill Right shift)
example1: 110100 >>> 2 = 001101
example2: 0101 >> 2 = 0001
이것들은 더 위에 논의되었지만, 참조용으로 포함되어있다.
~ (NOT)
example: ~1001 = 0110
음수의 경우, 2의 보수를 사용하면 비트를 뒤집어서 음수를 더할 수 있습니다.
- (NEGATIVE)
example: -1001 = 0111
정통한 독자는 비트 연산자를 사용하거나, 바이너리로 생각하거나, 매우 긴 중간 기사를 읽지 않고도 이러한 작업 중 많은 작업을
쉽게 수행 할 수 있습니다. 왜, 예를 들어, 우리는 3 * 2 5 대신 3 >> 5를하고 싶습니까? 이것은 완전히 동등합니다.
당신이 이것을 생각하고 있다면, 당신은 분명히 요점을 가지고 있습니다!
그러나 이 연산자는 실제로 배열이나 객체를 사용할 정보를 저장하기 위해 바이너리를 사용할 수 있다는 것을 알게되면 실제로 빛을 발합니다.
예를 들어, 수학 숙제를 하기 위해 기다리고 있는 학생들의 목록이 있다고 상상해보십시오 (수학, 영국).
이 정보를 javascript로 추적하려면 처음에 배열의 각 요소가 학생인 배열을 만들기로 결정할 수 있다.
각각의 학생을 별도의 객체로 표현하는 대신에, 기억 공간을 많이 차지하는 프로그래머라면, 각 학생을 단순한 부울로 표현할 수 있습니다.
반올림 한 경우 true이고 그렇지 않은 경우 false입니다. 그래서 거짓 배열, [거짓, 거짓, 거짓, 거짓, 거짓]으로 시작합니다.
숙제가 끝나기 하루 전, 학생들 중 일부는 일찍 숙제를하므로 배열을 반복하고 일부 거짓말을 사실로 변경합니다 : [참, 거짓, 참, 거짓, 거짓, 거짓]. 어떻게하는지에 따라 배열을 적어도 한 번 반복해야합니다. 이 연산에 O (n)의 최악의 시간 복잡도를 부여해야합니다.
다음 날, 더 많은 학생들이 늦게 들어서서 다시 배열을 반복하고, 더 많은 거짓들을 사실로 뒤집습니다 : [진실, 진실, 진실, 거짓, 참, 참].
이것은 충분히 잘 작동합니다. 그러나 바이너리 및 비트 연산자를 사용하여 이 동일한 정보를 저장하고 조작 할 수있는 방법에 대해 생각해보십시오.
우선, 클래스를 나타 내기 위해 요소로 가득 찬 배열 전체가 필요하지 않습니다. falses로 가득 찬 배열 대신에 일련의 000000 비트로 시작하십시오.
이것은 크기 n의 배열을 단일 숫자로 대체 할 때 훨씬 적은 공간을 차지합니다! 첫날 이후에는 101000이 될 것입니다. 숫자 40과 같습니다.
단지 40이라는 숫자가 수업의 상태에 대해 필요한 모든 정보를 인코딩하는 데 충분하다는 것은 놀랍고 즐겁습니다.
그리고 다음날 111011, 일명 59가됩니다.
이것은 바이너리 연산자가 어떻게 공간을 최적화하는 데 도움이되는지를 보여줄 것입니다.
그러나 그것은 또한 우리가 수업의 디지털 표현을 훨씬 더 효율적으로 업데이트하는 데 도움이 될 것입니다.
첫 날이 끝나면 1과 3의 위치 (0 색인을 선호하는 경우 0과 2)에 저장된 학생들이 숙제를 제출했음을 알 수 있습니다.
우리는 OR 연산자 (|)를 사용하여 스토리지를 쉽게 업데이트 할 수 있습니다. 00000 | 101000 = 101000입니다.
다음날 우리는 결과를 얻고 3 명의 추가 학생을 추가하여 숙제를 제출합니다 : 101000 | 010011 = 111011입니다.
두 경우 모두 첫 번째 숫자는 클래스의 현재 상태를 나타내고 두 번째 숫자는 추가 제출을 나타내며
세 번째 숫자는 두 클래스를 결합하여 클래스의 새 상태를 찾습니다.
이것이 얼마나 시간 효율적인지를 주목하십시오. 각 OR 연산은 6 + 5와 같은 일반적인 수학 연산과 비슷한 두 개의 정수에 대한 상수 시간 연산입니다.
이전 방법은 배열의 각 요소를 거쳐 업데이트 할지 여부와 O (n ) 효율성 작업), 우리는 한 단계에서 동일한 작업을 수행 할 수 있습니다.
(특히 빠른 O (1) 작업). 우리는 루프를 사용하는 것보다이 연산자를 사용하는 코드가 훨씬 적어지게됩니다.
그러나 이것은 한 가지 예 일뿐입니다. 데이터를 조작하기 위해 연산자를 사용할 수있는 편리하고 신속하며 쉬운 방법이 많이 있습니다.
어떤 학생들이 숙제를 제출하지 않았음을 보여주는 목록을 원하면 ~ 111011을 사용하여 000100을 얻을 수 있습니다
(32 비트로 작업하면 왼쪽에있는 0에 어떤 영향을 미치는지 인식 할 수 있지만).
그러나 우리 학생을 우리 학급에 추가하기를 원한다면 (그리고 32 비트로 작업하고 여분의 비트가있을 경우)
111011 << 1을하고 1110110을 새로운 학생과 함께 끝내면됩니다.
바이너리 및 비트 연산자를 사용하여 호텔의 결원을 나타내는 방법을 상상해보십시오.
또는 두 개의 이진수를 사용하여 tic tac toe 보드의 상태를 나타낼 수 있습니다.
하나의 숫자는 x의 제곱을 나타낼 수 있고 다른 숫자는 o의 사각형을 나타낼 수 있습니다. 그렇다면 우주 X를 할 수 있습니다.
spacesO를 사용하여 칠판에 채워진 모든 사각형을 얻거나 ~ (spacesX | spacesO)를 사용하여 재생할 수있는 공백을 만듭니다.
이제 이진 계산과 비트 연산자에 대해 배웠으니 이를 사용할 수있는 기회에 주목하십시오.
뿐만 아니라 시간과 공간을 절약 할 수있을뿐만 아니라 재미 있고 놀라운 문제에 대한 해결책을 찾을 수 있습니다.
또한 귀하의 친구 및 가족은 시간 효율적 운영에 대한 귀하의 숙련도에 깊은 인상을받습니다. 해피 코딩!