[C++] xor에 대해

ChangJin·2025년 1월 18일

목록 보기

3/3

글의 목적

C++의 XOR 연산은 어떻게 구현이 되어 있는지 알아보기 위해 작성

알게 된 점

C++에서 XOR 연산인 operator^는 컴파일러 수준에서 처리가 됩니다. 어셈블리 코드에서는 xorl로 XOR 연산을 수행합니다. 또한 스택 프레임의 오프셋에 있는 값을 XOR 하여 연산합니다. 또한 bitset 라이브러리는 큰 수에서 효율적입니다.

참고한 문서

내용

XOR : 흔히 생각할 수 있는 XOR 함수

딱 봐도 굉장히 비효율적인 XOR 함수입니다.


int XOR(const int& A, const int& B)
{
    int c = 0;
    int resultValue = 0;
    int a = A;
    int b = B;
    int k = 1;
    while (a != 0 || b != 0)
    {
        int ta = a % 2;
        int tb = b % 2;
        resultValue += ta == tb ? 0 : 1 * k;
        a /= 2; b /= 2;
        k *= 2;
    }
    return resultValue;
}

두 수를 mod 2 한 결과 값이 다르면 해당 비트의 값 만큼 더하여 최종 값을 더해나가는 코드입니다.

XOR2 : bitset 사용하기

C++ 표준 라이브러리 에서는 XOR 연산을 지원하는 bitset이 있습니다. 이를 사용하여 구현하면 다음처럼 만들 수 있습니다. 다음은 bitset 라이브러리를 사용하여 만든 함수 입니다.

std::bitset<8> XOR2(const std::bitset<8>& A, const std::bitset<8>& B)
{
    return A ^ B;
}

bitset의 내부 구현은 다음처럼 되어 있습니다. 배열에 접근하여 각 인덱스의 값을 xor하는 걸 알 수 있습니다.

_EXPORT_STD template <size_t _Bits>
_NODISCARD _CONSTEXPR23 bitset<_Bits> operator^(const bitset<_Bits>& _Left, const bitset<_Bits>& _Right) noexcept {
    bitset<_Bits> _Ans = _Left;
    _Ans ^= _Right;
    return _Ans;
}

_CONSTEXPR23 bitset& operator^=(const bitset& _Right) noexcept {
    for (size_t _Wpos = 0; _Wpos <= _Words; ++_Wpos) {
        _Array[_Wpos] ^= _Right._Array[_Wpos];
    }

    return *this;
}

XOR3 : ^ 연산으로 만들기

그리고 C++에서는 XOR을 더 쉽게 사용할 수 있는 ^ 연산이 있습니다.
다음은 ^ 연산을 사용하여 만든 XOR 함수입니다.

int XOR3(const int& A, const int& B)
{
    return A ^ B;
}

^ 연산은 다음의 함수를 어셈블리 코드로 변환하여 보면 이해할 수 있습니다. 다음의 코드를 실행해서 어셈블리 코드를 만들어 봅시다.

#include <iostream>
using namespace std;

int main() {
    int a = 5;
    int b = 3;
    int c = a ^ b;
    cout << c << endl;
    return 0;
}

g++ xor_example.cpp -S -o xor_example.s

그러면 다음처럼 a를 선언 및 정의하고 b를 선언 및 정의하고 c에 값을 대입하는 부분에 해당하는 어셈블리 코드를 확인할 수 있습니다.

	movl	$5, -4(%rbp)
	movl	$3, -8(%rbp)
	movl	-4(%rbp), %eax
	xorl	-8(%rbp), %eax
	movl	%eax, -12(%rbp)

movl : 32비트 데이터를 복사하는 명령

이 어셈블리 코드가 의미하는 건 다음과 같습니다.

movl $5, -4(%rbp)
정수 5를 스택 프레임의 오프셋 -4에 저장
movl $3, -8(%rbp)
정수 3을 스택 프레임의 오프셋 -8에 저장
movl -4(%rbp), %eax
스택 프레임의 오프셋 -4에서 값을 읽어와 레지스터 eax에 저장
xorl -8(%rbp), %eax
레지스터 eax와 스택 프레임의 오프셋 -8의 값을 XOR 연산
movl %eax, -12(%rbp)
레지스터 eax의 값을 스택 프레임의 오프셋 -12에 저장

세 함수의 연산 속도 차이

XOR, XOR2, XOR3
그렇다면 이 세 함수의 연산 속도 차이는 어떻게 될까요? 과연 어떤 함수가 실행 시간이 가장 짧을까요?

C++의 시간 측정 라이브러리인 chrono를 사용하여 실행 시간를 비교해보겠습니다.

#include <iostream>
#include <chrono>

int XOR(const int& A, const int& B)
{
    int c = 0;
    int resultValue = 0;
    int a = A;
    int b = B;
    int k = 1;
    while (a != 0 || b != 0)
    {
        int ta = a % 2;
        int tb = b % 2;
        resultValue += ta == tb ? 0 : 1 * k;
        a /= 2; b /= 2;
        k *= 2;
    }
    return resultValue;
}

std::bitset<8> XOR2(const std::bitset<8>& A, const std::bitset<8>& B)
{
    return A ^ B;
}

int XOR3(const int& A, const int& B)
{
    return A ^ B;
}

void XORCheck(const int& A, const int& B)
{
    int c = 0;
    for (int i = 0; i < 1000000; i++)
    {
        c = XOR(A, B);
    }
}

void XOR2Check(const std::bitset<8>& A, const std::bitset<8>& B)
{
    std::bitset<8> c = 0;
    for (int i = 0; i < 1000000; i++)
    {
        c = XOR2(A, B);
    }
}

void XOR3Check(const int& A, const int& B)
{
    int c = 0;
    for (int i = 0; i < 1000000; i++)
    {
        c = XOR3(A, B);
    }
}

int main(int argc, char* argv[])
{
    int a = 5;
    int b = 3;
    std::bitset<8> ab("00000101");
    std::bitset<8> bb("00000011");

    auto start1 = std::chrono::high_resolution_clock::now();
    XORCheck(a,b);
    auto end1 = std::chrono::high_resolution_clock::now();
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1).count();
    std::cout << "XOR Execution Time: " << duration1 << " microseconds\n";

    auto start2 = std::chrono::high_resolution_clock::now();
    XOR2Check(ab, bb);
    auto end2 = std::chrono::high_resolution_clock::now();
    auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2).count();
    std::cout << "XOR2 Execution Time: " << duration2 << " microseconds\n";

    auto start3 = std::chrono::high_resolution_clock::now();
    XOR3Check(a,b);
    auto end3 = std::chrono::high_resolution_clock::now();
    auto duration3 = std::chrono::duration_cast<std::chrono::microseconds>(end3 - start3).count();
    std::cout << "XOR3 Execution Time: " << duration3 << " microseconds\n";

    return 0;
}

결과는 다음과 같습니다.

while문을 사용하는 함수 : 6588 ms
biset을 사용하는 함수 : 12908 ms
^ 연산을 사용하는 함수 : 1454 ms

int와 같은 원시 타입의 XOR은 CPU에서 컴파일러 수준에서 명령어로 처리되기 때문에 그 속도가 굉장히 빠른 것을 알 수 있습니다.

신기한 것은 XOR 함수가 XOR2 함수보다 실행시간이 더 짧은 것인데요.
이는 bitset이 for문으로 8자리 인덱스를 계속해서 for문이 실행되는 것이라 while문을 사용하는 함수보다 느립니다.

따라서 굉장히 큰 수에서는 XOR2 함수가 XOR 함수보다 빠릅니다.

큰 수의 XOR

#include <iostream>
#include <chrono>

int XOR(const int& A, const int& B)
{
    int c = 0;
    int resultValue = 0;
    int a = A;
    int b = B;
    int k = 1;
    while (a != 0 || b != 0)
    {
        int ta = a % 2;
        int tb = b % 2;
        resultValue += ta == tb ? 0 : 1 * k;
        a /= 2; b /= 2;
        k *= 2;
    }
    return resultValue;
}

std::bitset<20> XOR2(const std::bitset<20>& A, const std::bitset<20>& B)
{
    return A ^ B;
}

int XOR3(const int& A, const int& B)
{
    return A ^ B;
}

void XORCheck(const int& A, const int& B)
{
    int c = 0;
    for (int i = 0; i < 1000000; i++)
    {
        c = XOR(A, B);
    }
}

void XOR2Check(const std::bitset<20>& A, const std::bitset<20>& B)
{
    std::bitset<20> c = 0;
    for (int i = 0; i < 1000000; i++)
    {
        c = XOR2(A, B);
    }
}

void XOR3Check(const int& A, const int& B)
{
    int c = 0;
    for (int i = 0; i < 1000000; i++)
    {
        c = XOR3(A, B);
    }
}

int main(int argc, char* argv[])
{
    int a = 500000;
    int b = 300000;
    std::bitset<20> ab("11110100001001000000");
    std::bitset<20> bb("100100011110000000");

    auto start1 = std::chrono::high_resolution_clock::now();
    XORCheck(a,b);
    auto end1 = std::chrono::high_resolution_clock::now();
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1).count();
    std::cout << "XOR Execution Time: " << duration1 << " microseconds\n";

    auto start2 = std::chrono::high_resolution_clock::now();
    XOR2Check(ab, bb);
    auto end2 = std::chrono::high_resolution_clock::now();
    auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2).count();
    std::cout << "XOR2 Execution Time: " << duration2 << " microseconds\n";

    auto start3 = std::chrono::high_resolution_clock::now();
    XOR3Check(a,b);
    auto end3 = std::chrono::high_resolution_clock::now();
    auto duration3 = std::chrono::duration_cast<std::chrono::microseconds>(end3 - start3).count();
    std::cout << "XOR3 Execution Time: " << duration3 << " microseconds\n";

    return 0;
}

XOR2 함수가 XOR 함수보다 실행 시간이 짧은 것을 확인 할 수 있습니다.
^ 연산은 큰 수, 작은 수일 때 실행 시간이 같은 것을 확인할 수 있습니다.

ChangJin

게임 프로그래머

이전 포스트

[C++] xor에 대해

C++

글의 목적

알게 된 점

참고한 문서

내용

[C++] Name Mangling

0개의 댓글