연산의 기술, 비트 매직

profile
FE Developer - 죠지
August 11, 2023
GPT 요약
Thumbnail

Descartes reinterpreted by MidJourney

안녕하세요. IT팀의 FE Developer 죠지입니다.

이번 글에서는 비트를 주제로 다양한 시도를 해보고 이를 활용해서 문제를 해결한 경험과 추가로 준비한 외전을 소개합니다.

비트의 세계

1과 0이 끝없이 반복해서 비처럼 내리는 세계. 흔히들 이 곳을 비트의 세계라고 말합니다.

Thumbnail

비트의 세계에서 무질서는 없습니다. 모든 것은 규칙에 따라 움직이고 있습니다. 그리고 이 규칙을 이해하고 활용하는 것이 비트 매직의 시작입니다.

Remind the bit

비트를 활용해서 해결한 문제에 대해 소개하기 전에 간단하게 기본 개념을 환기해보겠습니다.

비트 연산

비트 연산은 비트의 세계에서 규칙을 만드는 것입니다. 그리고 우리는 이러한 비트 연산을 & (AND), | (OR), ^ (XOR), ~ (NOT) 등의 기호로 표현합니다.

Tip
비트 연산의 우선순위는 산술 연산자보다 낮습니다.
Tip
비트 연산의 결합 방향은 왼쪽에서 오른쪽입니다.

비트 테이블

비트 연산을 이해하기 위해서는 비트 테이블을 알아야 합니다.

ABA & BA | BA ^ B~A
000001
010111
100110
111100

보수

보수는 비트 연산에서 가장 중요한 개념입니다. 보수는 비트 연산에서 0과 1을 바꾸는 것을 의미합니다.

A~A
01
10

1의 보수

1의 보수는 비트 연산에서 1을 0으로, 0을 1로 바꾸는 것을 의미합니다.

2의 보수

2의 보수는 비트 연산에서 1의 보수에 1을 더한 것을 의미합니다.

본격적인 비트 매직

      ___               ___          ___          ___          ___                   ___
     /\  \        ___  /\  \        /\__\        /\  \        /\  \        ___      /\  \
    /::\  \      /\  \ \:\  \      /::|  |      /::\  \      /::\  \      /\  \    /::\  \
   /:/\:\  \     \:\  \ \:\  \    /:|:|  |     /:/\:\  \    /:/\:\  \     \:\  \  /:/\:\  \
  /::\~\:\__\    /::\__\/::\  \  /:/|:|__|__  /::\~\:\  \  /:/  \:\  \    /::\__\/:/  \:\  \
 /:/\:\ \:|__|__/:/\/__/:/\:\__\/:/ |::::\__\/:/\:\ \:\__\/:/__/_\:\__\__/:/\/__/:/__/ \:\__\
 \:\~\:\/:/  /\/:/  / /:/  \/__/\/__/~~/:/  /\/__\:\/:/  /\:\  /\ \/__/\/:/  /  \:\  \  \/__/
  \:\ \::/  /\::/__/ /:/  /           /:/  /      \::/  /  \:\ \:\__\ \::/__/    \:\  \
   \:\/:/  /  \:\__\ \/__/           /:/  /       /:/  /    \:\/:/  /  \:\__\     \:\  \
    \::/__/    \/__/                /:/  /       /:/  /      \::/  /    \/__/      \:\__\
     ~~                             \/__/        \/__/        \/__/                 \/__/

본격적인 비트 매직을 시작해봅시다.

저희 프로젝트에서는 비트를 활용해서 해결해야 하는 문제가 다소 존재했습니다. 그리고 그 역할을 맡은 사람이 저였고, 이러한 계기로 비트에 대한 공부가 필요했습니다.

첫 번째 문제

비트를 활용해서 해결한 첫번째 문제입니다.

4가지 카테고리를 각각 32비트로 구성하고, 입력마다 검증한 후, 출력해야 했습니다.

Security
보안을 위해 특정 단어를 사용하지 않습니다.

구조 분석

제공된 변수의 차원은 2차원입니다. 그리고 하나의 차원은 64비트, Big Integer로 제공되었습니다. 4가지 카테고리가 있다고 했으니, 변수당 32비트로 쪼개어 사용한 것을 알 수 있습니다.

먼저 64비트라는 큰 수를 나타낼 수 있으려면 typescript에서는 BigInt를 사용해야 했습니다. 그리고 toString(2)을 활용해서 2진수로 변환해야 했습니다.

// es2020 이상
// 36028797018963968 = 2^55
const unknowBigInt1 = 36028797018963968n;

const unknowBigInt2 = BigInt(36028797018963968);
// ↪ 36028797018963968n

const unknowBigIntString = BigInt('36028797018963968');
// ↪ 36028797018963968n

const hexadecimal = BigInt('0x80000000000000');
// ↪ 36028797018963968n

const binary = BigInt(
  '0b10000000000000000000000000000000000000000000000000000000'
);
// ↪ 36028797018963968n

출력

이제 구조가 어떻게 되었는지를 알았으니, 출력을 해봅시다.

그리고 앞서 말씀드린 카테고리는 각각 카테고리_1, 카테고리_2, 카테고리_3, 카테고리_4로 구분하도록 하겠습니다.

hello

그림을 먼저 보시면 넘버링이 되어 있는 테이블로 보입니다. 각 cell은 하나의 비트로 이해할 수 있고, 각 비트가 8개씩 끊겨서 마치 저희가 입문에서 배우는 달팽이 그리기와 같은 시계 방향 회전을 하고 있습니다.

물론 이터레이션으로 구현해야 할 것 같습니다. 이제 넘겨 받은 수(최대 2^64)에 toString(2)를 취하고 padStart(64,'0')로 길이 64의 문자열로 변환합니다.

Security
출력의 알고리즘만 설명할 뿐 용도는 설명하지 않습니다.

hello2

다시 테이블을 살펴보도록 하겠습니다. 테이블에는 arrow로 direction이 표시되어 있습니다. 방향이 이터레이션의 주기마다 바뀌는 것을 확인 할 수 있습니다. 물론 허수를 사용한다면 4방위를 모두 나타낼 수 있지만, 허수는 파이썬에서나 가능하기 때문에 조금 더 간단하게 생각할 필요가 있습니다.

단순화 해봅시다. 방향은 순전히 왼쪽과 오른쪽뿐입니다. 그렇기 때문에 direction이라는 배열을 하나 생성합니다.

const direction = [-1, 1, 1, -1, -1, 1, 1, -1];

각 방향마다 8개의 처리를 해줘야하기 때문에 이중 for문의 형태가 적합 할 것 같습니다!

{
  // 방향
  direction.map((direction, idx_1) => {
    let acc = 380;
    // 8번의 이터레이션
    return new Array(8).fill(0).map((_, idx_2) => {
      const element = data[idx_1 * 8 + idx_2];
      if (validation.includes(element.value)) {
        return null;
      }
      const yPosition = getYPosition(element.value);
      const width = getWidthByValue(element.value);
      if (direction === -1) {
        acc += direction * (width + 5);
      } else {
        if (idx_1 === 1 || idx_1 === 2) {
          acc += bigGapResolver[idx_2] + 5;
        } else {
          acc += smallGapResolver[idx_2] + 5;
        }
      }
      return (
        <Element
          x={acc}
          y={yPosition}
          key={idx_2}
          data={element}
          onSelect={onSelect}
          isSelected={selectedElementIds.indexOf(element.value) >= 0}
          width={width}
          selectedStatus={selectedElementStatus[element.value]}
        />
      );
    });
  });
}

물론 최종적인 출력에는 비트를 자리 수마다 한 번 더 가공해서 props로 넘겨야합니다. 그래도 전체적인 구현의 프로세스만 설명하기 위한 목적으로 더 깊은 내용은 다루지 않겠습니다.

두 번째 문제

카테고리_2~4의 정보는 같은 테이블 cell에 다른 정보를 나타내기 위한 정보로 중복 체크를 해야합니다.

3 가지 변수를 선언해보겠습니다.

const category_1 = '0b10001001000000100001001000001001';
const category_2 = '0b01010000100001000100000010100100';
const category_3 = '0b00000100000010001000010000000000';

이제 본격적으로 연산이 필요합니다. 앞서 언급했던 '^', '/', '|'를 활용해봅시다.

먼저 셀을 선택하고 카테고리를 추가로 선택합니다.

hello3

Alert
실제로는 선택한 셀만의 인덱스 정보만 기억하는 방법을 활용합니다.

중복 체크

중복을 허용하지 않는다는 것은 어떤 의미일까요? 각각의 연산마다 생각이 필요합니다.

  • AND: 연산 후 값이 0보다 크다면 중복입니다. 활용 가능합니다.
  • OR: 연산 후 중복 정보를 잃어버리게 됩니다. 활용 불가능합니다.
  • XOR: XOR은 0의 정보도 중복으로 취급하기 때문에 활용하기에 어려움이 있습니다.

중복의 여부는 완전한 비트를 취했을 때, AND가 적합해 보입니다. 그런데 한 가지 의문입니다. 굳이 완전한 비트를 구성해서 연산해야 하는가입니다.

선택 셀의 인덱스는 지수와 같습니다. 그렇기 때문에 각 카테고리의 비트값과 단독으로 연산을 진행하고 다시 값을 할당하면 될 것 같습니다. 다시 각 연산을 생각해봅니다.

  • AND: 연산 후 0보다 크다면 중복입니다.
  • OR: 활용할 수 없습니다.
  • XOR: 연산 후 값이 일치하면 중복입니다.

중복 외전

남은 카테고리 2개에 각각 AND를 해도 되지만, OR로 중복 정보를 종합하고, 최종적으로 AND를 한다면 간단하게 중복처리가 가능합니다.

비트 외전

<<, >>, ~

시프트 연산자의 경우는 잘 사용하면 원하는 결과를 빠르게 얻을 수 있습니다. 그 예시가 바로 완전히 채워진 비트를 얻는 것입니다. 모든 자리수가 완전히 채워진 비트를 얻을 때 어떤 방법을 사용하고 계신가요? 아마도 루프를 돌면서 문자열을 만들고 계실지도 모릅니다.

하지만 아래와 같이 하면 좀 더 간단하게 구할 수 있습니다.

function returnFullBinary(n: number): string {
  return ((1 << n) - 1).toString(2);
}

위의 식을 활용하면 특정 i 이하나 이상의 비트를 0으로 마스킹 할 수도 있습니다.

function returnMasking1(target: number, i: number): string {
  return target & ~((1 << i) - 1);
}

function returnMasking2(target: number, i: number): string {
  return target & ((1 << i) - 1);
}

좀 더 나아가 보겠습니다. 해당 정수가 2의 거듭제곱인 것을 어떻게 알 수 있을까요?

감이 오셨나요?

function isPowerOf2(n: number): boolean {
  return n & (n - 1 === 0);
}

집합론과 비트

집합론에서 비트는 어떻게 활용되고 있을까요?

하나의 정수를 집합으로 나타내어 봅시다. 모든 정수는 이진수로 나타낼 수 있고, LSB의 인덱스를 0, MSB의 인덱스를 n이라고 가정했을 때, 아래와 같이 나타낼 수 있습니다.

// 301 == 0b100101101
// 301 = {8,5,3,2,0}

결국 정수의 연산은 이진법의 영역에서 특정 자리수의 스위칭입니다. 그렇기 때문에 각 자리수로 이루어진 집합으로 확장하면 비트 연산의 &, | 등을 교집합, 합집합에 매핑하여 이해할 수 있습니다.

예시를 들어 보겠습니다.

8과 7의 & 연산은 집합 { 3 }, { 2,1,0 }의 교집합과 같습니다. 그렇기 때문에 공집합 즉 0이 됩니다.

8과 11의 차집합은 { 3 }, { 3,1,0 }의 교집합과 집합 { 3 }의 뺄셈과 같습니다.
그렇기 때문에 8 & ~(8 & 11)로 나타낼 수 있습니다.

큐비트

hello4

1977년 새로운 암호화 알고리즘을 제시한 세 명의 과학자가 있습니다. 이들의 이름은 각각 Ron Rivest, Adi Shamir, Leonard Adlemon입니다. 그리고 새로운 암호화 알고리즘의 이름은 이들의 이름을 앞글자를 딴 RSA입니다.

RSA는 두 개의 큰 소수를 가지고 곱한 다음 이를 공개키로 배포합니다. 공개키는 모든 사람이 볼 수 있습니다. 이제 내가 공개키를 배포한 상대에게 메세지를 전달하고 싶다면 상대가 배포한 공개키를 활용해 나의 메세지를 암호화한 후 전송하면 됩니다.

배포자 즉, 두 개의 소수가 이미 무엇인지 알고 있는 쪽은 소수의 인수 분해 없이 곧바로 해독할 수 있습니다. 하지만 이것을 모른다면 무조건 공개키의 소수를 소인수 분해해서 두 개의 소수를 알아내야 합니다.

겉으로 보기에는 단순히 공개키를 소인수 분해만 하면 쉽게 풀릴 문제라고 오인합니다. 물론 일반 수체 알고리즘(GNFS) 등의 소인수 분해 알고리즘과 슈퍼 컴퓨터를 조합해서 소인수 분해할 수도 있습니다.

그렇지만 일반적으로 현대 암호학에서는 313자리의 소수를 활용합니다. 이렇게 매우 큰 두 소수의 곱을 소인수 분해하는 것은 현존 최강의 슈퍼 컴퓨터로도 1600만년이 걸립니다.

중첩

hello5

양자역학에서 중첩(Quantum Superposition)은 양자 메카니즘의 기본적인 특징 중 하나로, 양자 상태가 여러 가능한 값을 동시에 가질 수 있는 현상을 뜻합니다. 이는 전통적인 클래식 물리에서는 경험하지 못하는 현상으로, 양자역학의 핵심 개념 중 하나입니다.

큐비트와 같은 양자 시스템은 0과 1만을 나타내는 클래식 비트와 달리 양자 상태로서 0과 1을 동시에 나타낼 수 있습니다. 이렇게 동시에 여러 상태를 가지는 것을 중첩이라고 합니다. 중첩된 양자 상태는 수학적으로는 복소수를 이용한 벡터로 표현되며, 이 상태는 관측될 때 하나의 값을 가지게 됩니다.

예를 들어, 양자 컴퓨팅에서는 한 큐비트가 중첩된 상태인 (|0⟩ + |1⟩) / √2로 표현될 수 있습니다. 이는 0과 1을 동시에 가지고 있으며, 양자 연산이 이 중첩된 상태에 작용하면 복잡한 연산을 동시에 수행할 수 있게 됩니다.

가능성

hello6

모든 상태가 중첩이 되기 때문에 큐비트가 3개 모이면 즉 8가지 상태가 공존하게되고 한번에 8가지 계산을 할 수 있습니다. 그리고 이를 20개까지 늘린다면 2^20, 즉 백만가지가 넘는 계산을 한 번에 할 수 있습니다.

만약 큐비트가 300개가 넘게 모인다면, 관찰 가능한 우주에 있는 입자보다 더 많은 상태를 나타낼 수 있습니다. 정말 놀라운 일이 아닐 수 없습니다.

문제

실로 놀라운 능력을 보여주는 양자 컴퓨터도 분명히 문제를 가지고 있습니다. 바로 중첩입니다. 중첩은 양자 컴퓨팅의 근본이자 한계가 될 수 있습니다. 왜냐하면 모든 상태가 중첩된 상태이기 때문에 관측자가 이를 읽기가 쉽지 않다는 점 때문입니다.

관측을 하는 순간 중첩된 값들 중 랜덤한 하나의 값만 얻게 되고 나머지 정보는 곧바로 손실됩니다. 그렇기 때문에 양자 컴퓨팅의 결과로 얻어지는 중첩된 상태에서 우리가 원하는 정보를 정확하게 가진 상대로 변화하는 방법을 만들어야합니다.

아마 모래사장에서 바늘 찾기라는 말이 가장 어울리는 상황이 아닐까 싶습니다.

감사합니다!

profile
안녕하세요 👏
FE Developer 죠지입니다.
githubgithubgithub