끔찍한 숫자

이진 확장에 홀수가 포함된 숫자는 홀수로 간주됩니다. 처음 10개의 홀수는 1,2,4,7,10,11,13,14,16,19,21입니다. 흥미롭게도 2의 거듭제곱은 모두 1비트만 설정되어 있기 때문에 홀수입니다.

다음 글에서는 숫자가 혐오 숫자인지 판단하는 두 가지 방법을 자세히 설명합니다.

문제 설명

이 질문의 목적은 주어진 숫자가 흉악한 숫자인지 확인하는 것입니다. 즉, 이진 확장에서 홀수로 설정된 비트가 있는 양수인지 확인하는 것입니다.

역겨운 숫자 예

지침

34의 이진 표현은 10010입니다.

자릿수 = 2로 설정합니다.

1의 숫자는 짝수이므로 34는 끔찍한 숫자는 아닙니다.

지침

1024의 이진 표현은 10000000000입니다.

자릿수 = 1로 설정합니다.

1024는 2의 거듭제곱이므로 설정 비트는 1개뿐입니다. 그래서 무서운 숫자다.

지침

(53)₁₀ = (110101)₂

자릿수 = 4로 설정합니다.

그래서, 가증스러운 숫자는 아닙니다.

솔루션

혐오숫자인지 판단하기 위해서는 설정된 자릿수가 홀수인지 짝수인지를 알아야 합니다. 여기서 주요 작업은 숫자의 이진 확장에 설정된 자릿수를 계산하는 것입니다. 다음 기술을 사용하여 자릿수를 세고 결과가 홀수인지 짝수인지 확인할 수 있습니다.

Naive Approach

Naive Approach

• 루프 및 오른쪽 시프트 연산자를 사용하여 숫자의 모든 자릿수를 하나씩 살펴보세요.

• 비트 값이 1이면 개수를 1씩 늘립니다.

• count의 최종 값이 홀수인지 짝수인지 확인하세요.

• 답변을 보여주세요.

의사코드

함수 no_of_set_bits()

• 초기화 횟수 = 0

• (n > 0)일 때

• 반품 횟수

함수 is_odious()

• (개수가 홀수인 경우)

참을 반환

• 기타

반품 오류

함수 main()

• n 초기화

• 함수 호출 no_of_set_bits()

• 호출 함수 is_odious()

• 인쇄물

예: C++ 프로그램

이 프로그램은 숫자가 공격적인지 여부를 확인합니다. no_of_set_bits() 함수에서 각 반복이 끝날 때마다 값을 n만큼 오른쪽으로 이동하여 루프의 각 반복에서 가장 오른쪽 비트를 확인합니다.

출력

시간과 공간 분석

시간 복잡도: O(log(n)), n의 이진 확장에는 log2n 비트가 필요하므로 모든 비트를 확인하여 어떤 비트가 설정되어 있는지 확인합니다.

공간 복잡도: O(1), 추가 공간이 사용되지 않기 때문입니다.

Brian Kernighan의 알고리즘 방법

이 알고리즘을 사용하면 숫자의 설정된 자릿수를 보다 효율적인 방법으로 계산할 수 있습니다. 그런 다음 is_odious() 함수를 사용하여 숫자가 공격적인지 여부를 확인할 수 있습니다.

이 방법의 기본 원리는 0에 도달하는 데 필요한 반복 횟수를 추적하면서 숫자의 가장 오른쪽에 설정된 비트를 반복적으로 지우는 것입니다. 관련된 단계는 다음과 같습니다 -

• 카운트를 0

으로 초기화합니다.

• 숫자가 0보다 큰 경우 숫자와 2의 보수 사이에 비트 단위 &를 수행하여 가장 오른쪽에 설정된 비트를 설정 해제합니다.

• 루프가 반복될 때마다 개수가 증가합니다.

• 최종 개수가 홀수인지 확인하세요.

• 결과 표시.

예

숫자를 10이라고 합시다. 10의 이진 전개는 1010입니다. 2개의 설정 비트가 있는 것을 볼 수 있습니다.

루프 반복 1 -

루프 반복 2 -

반복 횟수 = 설정 횟수 = 2.

의사코드

함수 no_of_set_bits()

• 초기화 횟수 = 0

• (n > 0)일 때

n = n & (n-1)

카운트 늘리기

• 반품 횟수

함수 is_odious()

이전 방법과 동일

함수 main()

이전 방법과 동일

예: C++ 프로그램

이 프로그램은 모든 설정된 비트를 설정 해제하는 데 필요한 반복 횟수를 계산하여 설정된 비트 수를 계산합니다. 비트를 취소하려면 n과 n-1에 대해 비트별 AND 연산을 수행합니다. 이는 n-1의 이진 표현이 n의 가장 오른쪽 세트 비트와 그에 따르는 모든 비트를 뒤집기 때문입니다.

출력

시공간 분석

Time Complexity - O(log(x)), 여기서 x는 숫자에 설정된 자릿수입니다. 설정된 비트가 1개뿐인 경우 루프는 한 번 실행됩니다.

공간 복잡성 - 추가 공간이 사용되지 않으므로 O(1)입니다.

위 방법을 비교해 보세요

첫 번째 방법은 이해하기 매우 쉽지만 최종 결과를 생성하려면 log(n) 반복이 필요합니다. 반면에 두 번째 방법은 log(x) 반복을 사용합니다. 여기서 x는 숫자의 이진 확장에 설정된 자릿수입니다. 따라서 성능이 향상됩니다.

결론

이 글에서는 숫자가 역겨운지 확인하는 두 가지 방법을 설명합니다. 또한 방법의 개념, 예제, 사용된 알고리즘, C++ 프로그램 솔루션 및 각 방법의 복잡성 분석을 제공합니다. 또한 두 가지 방법을 비교하여 어느 방법이 더 효과적인지 결정했습니다.

위 내용은 끔찍한 숫자의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!