C++20에서 양의 정수가 2의 제곱인지 효율적으로 테스트하는 방법

2024-07-27

C++20에서 양의 정수가 2의 제곱인지 효율적으로 테스트하는 방법

비트 연산 사용:

가장 간단하고 빠른 방법은 비트 연산을 사용하는 것입니다. 다음 코드는 n이 2의 제곱인지 확인하는 비트 연산 기반 함수입니다.

bool isPowerOfTwo(unsigned int n) {
  return (n && (n & (n - 1)) == 0);
}

이 함수는 다음과 같은 방식으로 작동합니다.

n과 n - 1의 비트와 논리곱을 수행합니다. 2의 제곱인 경우 결과는 항상 0이 됩니다. 왜냐하면 2의 제곱에서 1 비트를 빼면 모든 비트가 0이 되기 때문입니다.
n과 결과를 비트와 논리합을 수행합니다. 결과가 0이 아니면 n은 2의 제곱이 아닙니다.

루프 사용:

다음 코드는 루프를 사용하여 n이 2의 제곱인지 확인하는 함수입니다.

bool isPowerOfTwo(unsigned int n) {
  if (n == 0) return false;
  while (n % 2 == 0) {
    n /= 2;
  }
  return (n == 1);
}

n이 0인 경우 2의 제곱이 아니므로 false를 반환합니다.
n이 2로 나누어 떨어지는 동안 반복합니다. 2의 제곱은 2로 반복해서 나눌 수 있습니다.
루프가 종료되면 n은 1이어야 합니다. 1은 유일한 홀수 2의 제곱이기 때문입니다.

표준 라이브러리 함수 사용:

C++20에는 std::bit_mask 함수와 같은 유용한 표준 라이브러리 함수가 도입되었습니다. 다음 코드는 std::bit_mask 함수를 사용하여 n이 2의 제곱인지 확인하는 함수입니다.

#include <bitset>

bool isPowerOfTwo(unsigned int n) {
  return std::bitset<sizeof(unsigned int)>(n).count() == 1;
}

n을 std::bitset 객체로 변환합니다.
count() 함수를 사용하여 비트셋에서 설정된 비트 수를 계산합니다. 2의 제곱은 1개의 설정된 비트만 가질 수 있습니다.
설정된 비트 수가 1인 경우 n은 2의 제곱입니다.

성능 비교:

세 가지 방법 모두 빠르고 효율적이지만, 일반적으로 비트 연산을 사용하는 방법이 가장 빠릅니다. 루프 기반 방법은 n이 큰 값일 때 약간 느려질 수 있습니다. 표준 라이브러리 함수는 코드 간결성을 제공하지만 다른 두 방법보다 약간 느릴 수 있습니다.

예제 코드

#include <iostream>
#include <bitset>

using namespace std;

bool isPowerOfTwo_Bitwise(unsigned int n) {
  return (n && (n & (n - 1)) == 0);
}

bool isPowerOfTwo_Loop(unsigned int n) {
  if (n == 0) return false;
  while (n % 2 == 0) {
    n /= 2;
  }
  return (n == 1);
}

bool isPowerOfTwo_Bitset(unsigned int n) {
  return std::bitset<sizeof(unsigned int)>(n).count() == 1;
}

int main() {
  unsigned int n;

  cout << "양의 정수를 입력하세요: ";
  cin >> n;

  if (isPowerOfTwo_Bitwise(n)) {
    cout << n << "은 2의 제곱입니다." << endl;
  } else {
    cout << n << "은 2의 제곱이 아닙니다." << endl;
  }

  if (isPowerOfTwo_Loop(n)) {
    cout << n << "은 2의 제곱입니다." << endl;
  } else {
    cout << n << "은 2의 제곱이 아닙니다." << endl;
  }

  if (isPowerOfTwo_Bitset(n)) {
    cout << n << "은 2의 제곱입니다." << endl;
  } else {
    cout << n << "은 2의 제곱이 아닙니다." << endl;
  }

  return 0;
}

이 코드를 실행하면 다음과 같은 출력이 나타납니다.

양의 정수를 입력하세요: 8
8은 2의 제곱입니다.
8은 2의 제곱입니다.
8은 2의 제곱입니다.

양의 정수를 입력하세요: 15
15은 2의 제곱이 아닙니다.
15은 2의 제곱이 아닙니다.
15은 2의 제곱이 아닙니다.

이 예제는 세 가지 방법 모두가 올바르게 작동하는 것을 보여줍니다.

참고:

이 코드는 C++20을 사용합니다. 이전 버전의 C++를 사용하는 경우 std::bit_mask 함수를 사용할 수 없습니다.
코드는 unsigned int 형을 사용합니다. 다른 정수 형식을 사용하려면 코드를 조정해야 할 수 있습니다.

C++20에서 양의 정수가 2의 제곱인지 확인하는 대체 방법

전제 조건 사용:

다음 코드는 std::is_power_of_2 함수를 사용하여 n이 2의 제곱인지 확인하는 함수입니다. 이 함수는 C++20의 <type_traits> 헤더에서 제공됩니다.

#include <type_traits>

bool isPowerOfTwo(unsigned int n) {
  return std::is_power_of_2(n);
}

std::is_power_of_2 템플릿 특성을 사용하여 n이 2의 제곱인지 확인합니다.
특성이 true를 반환하면 n은 2의 제곱입니다.

lambda 표현식 사용:

bool isPowerOfTwo(unsigned int n) {
  return [](unsigned int x) { return (x && (x & (x - 1)) == 0); }(n);
}

이 함수는 앞서 설명한 비트 연산 기반 함수와 동일한 기능을 수행하는 lambda 표현식을 사용합니다.

bool isPowerOfTwo(unsigned int n) {
  return n > 0 && ((n & (n - 1)) == 0);
}

이 함수는 다음과 같은 조건을 사용하여 n이 2의 제곱인지 확인합니다.

n은 0보다 커야 합니다.
n과 n - 1의 비트와 논리곱을 수행하면 0이어야 합니다.

std::is_power_of_2 함수를 사용하는 방법은 일반적으로 가장 빠르고 효율적입니다. 하지만 이 함수는 C++20만 지원됩니다. 비트 연산을 사용하는 방법과 lambda 표현식을 사용하는 방법은 성능 면에서 비슷하지만, 코드 간결성 측면에서 lambda 표현식이 더 유리할 수 있습니다. 제한 조건을 사용하는 방법은 다른 방법들보다 느릴 수 있지만, 코드가 가장 간결합니다.

c++ performance bit-manipulation