1. 개요
이 기사에서는 주어진 수보다 작은 2의 가장 큰 거듭제곱을 찾는 방법을 살펴보겠습니다.
우리의 예에서는 샘플 입력 9를 사용할 것입니다. 2 0 은 1이며, 주어진 입력보다 작은 2의 거듭제곱을 찾을 수 있는 최소 유효 입력은 2입니다. 따라서 1보다 큰 입력만 다음과 같이 간주합니다. 유효한.
2. 순진한 접근
1인 2 0 부터 시작 하고 입력보다 작은 숫자를 찾을 때까지 계속해서 2를 곱합니다 .
public long findLargestPowerOf2LessThanTheGivenNumber(long input) {
Assert.isTrue(input > 1, "Invalid input");
long firstPowerOf2 = 1;
long nextPowerOf2 = 2;
while (nextPowerOf2 < input) {
firstPowerOf2 = nextPowerOf2;
nextPowerOf2 = nextPowerOf2 * 2;
}
return firstPowerOf2;
}샘플 입력 = 9에 대한 코드를 이해합시다 .
firstPowerOf2 의 초기 값 은 1이고 nextPowerOf2 는 2입니다. 보시다시피 2 < 9는 true이고 while 루프 내부로 들어갑니다.
첫 번째 반복의 경우 firstPowerOf2 는 2이고 nextPowerOf2 는 2 * 2 = 4입니다. 다시 4 < 9이므로 while 루프를 계속할 수 있습니다.
두 번째 반복의 경우 firstPowerOf2 는 4이고 nextPowerOf2 는 4 * 2 = 8입니다. 이제 8 < 9이므로 계속 진행하겠습니다.
세 번째 반복의 경우 firstPowerOf2 는 8이고 nextPowerOf2 는 8 * 2 = 16입니다. while 조건 16 < 9는 거짓이므로 while 루프에서 빠져 나옵니다. 8은 9보다 작은 2의 가장 큰 거듭제곱입니다.
코드의 유효성을 검사하기 위해 몇 가지 테스트를 실행해 보겠습니다.
assertEquals(8, findPowerOf2LessThanTheGivenNumber(9));
assertEquals(16, findPowerOf2LessThanTheGivenNumber(32));
우리 솔루션의 시간 복잡도는 O(log 2 (N)) 입니다. 우리의 경우 log 2 (9) = 3번 반복했습니다.
3. Math.log 사용하기
로그 밑수 2는 숫자를 재귀적으로 2로 나눌 수 있는 횟수를 제공합니다 . 즉, 숫자의 로그 2 는 2 의 거듭제곱을 제공합니다 . 이를 이해하기 위해 몇 가지 예를 살펴보겠습니다.
log 2 (8) = 3 및 log 2 (16) = 4. 일반적으로 y = log 2 x 여기서 x = 2 y 임을 알 수 있습니다 .
따라서 2로 나누어 떨어지는 숫자를 찾으면 숫자가 2의 완전 거듭제곱인 시나리오를 피하기 위해 1을 뺍니다.
Math.log 는 로그 10 입니다. log 2 (x)를 계산하려면log 2 (x)=log 10 (x)/log 10 (2)공식을 사용할 수 있습니다.
코드에 넣어 보겠습니다.
public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) {
Assert.isTrue(input > 1, "Invalid input");
long temp = input;
if (input % 2 == 0) {
temp = input - 1;
}
long power = (long) (Math.log(temp) / Math.log(2));
long result = (long) Math.pow(2, power);
return result;
}샘플 입력을 9로 가정하면 temp 의 초기 값 은 9입니다.
9 % 2는 1이므로 임시 변수는 9입니다. 여기서는 나머지 9/2를 제공하는 모듈로 나누기를 사용합니다.
log 2 (9) 를 찾기 위해 log 10 (9) / log 10 (2) = 0.95424 / 0.30103 ~= 3을 수행합니다.
이제 결과 는 2 3 즉 8입니다.
코드를 확인해 보겠습니다.
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32));실제로 Math.pow 는 접근 1에서 했던 것과 동일한 반복을 수행할 것입니다. 따라서 이 솔루션에서도 시간 복잡도는 O(Log 2 (N)) 이라고 말할 수 있습니다 .
4. 비트와이즈 기법
이 접근 방식에서는 비트 시프트 기술을 사용합니다. 먼저 숫자를 나타내는 4비트가 있다는 점을 고려하여 2의 거듭제곱에 대한 이진 표현을 살펴보겠습니다.
| 2 0 | 1 | 0001 |
| 2 1 | 2 | 0010 |
| 2 2 | 4 | 0100 |
| 2 3 | 8 | 1000 |
자세히 살펴보면 1의 바이트를 왼쪽으로 이동하여 2의 거듭제곱을 계산할 수 있음을 관찰할 수 있습니다 . 즉. 2 2 는 1 x 2 자리에 대한 왼쪽 시프트 바이트입니다.
비트 시프트 기술을 사용하여 코딩해 보겠습니다.
public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) {
Assert.isTrue(input > 1, "Invalid input");
long result = 1;
long powerOf2;
for (long i = 0; i < Long.BYTES * 8; i++) {
powerOf2 = 1 << i;
if (powerOf2 >= input) {
break;
}
result = powerOf2;
}
return result;
}위의 코드 에서는 8바이트 또는 64비트를 사용하는 데이터 유형으로 long 을 사용하고 있습니다. 그래서 우리는 2의 거듭제곱을 2 64 까지 계산할 것 입니다. 비트 시프트 연산자 << 를 사용하여 2의 거듭제곱을 찾습니다. 샘플 입력 9의 경우 4 번째 반복 후 powerOf2 = 16 및 result = 8 의 값은 루프에서 16 > 9로 나뉩니다 . 입력 .
코드가 예상대로 작동하는지 확인해 보겠습니다.
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));이 접근 방식 의 최악의 시간 복잡도 는 첫 번째 접근 방식에서 본 것과 유사하게 다시 O(log 2 (N)) 입니다. 그러나 이 접근 방식은 곱셈에 비해 비트 시프트 연산이 더 효율적 이기 때문에 더 좋습니다 .
5. 비트 AND
다음 접근 방식에서는 이 공식 2 n AND 2 n -1 = 0 을 사용할 것 입니다.
작동 방식을 이해하기 위해 몇 가지 예를 살펴보겠습니다.
4의 이진 표현은 0100 이고 3은 0011 입니다.
이 두 숫자에 대해 비트 AND 연산 을 수행해 보겠습니다 . 0100 과 0011 은 0000 입니다. 2의 거듭제곱과 그보다 작은 수에 대해서도 동일하게 말할 수 있습니다. 각각 1000 , 0111 로 표현되는 16(2 4 )과 15를 취합시다 . 다시 말하지만, 이 두 가지에 대한 비트별 AND 결과는 0입니다. 또한 이 2를 제외한 다른 숫자에 대한 AND 연산은 0이 되지 않을 것이라고 말할 수 있습니다.
비트 AND를 사용하여 이 문제를 해결하는 코드를 살펴보겠습니다.
public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) {
Assert.isTrue(input > 1, "Invalid input");
long result = 1;
for (long i = input - 1; i > 1; i--) {
if ((i & (i - 1)) == 0) {
result = i;
break;
}
}
return result;
}위의 코드에서 우리는 입력보다 작은 숫자를 반복합니다. 숫자와 숫자-1의 비트 AND를 찾을 때마다 숫자가 2의 거듭제곱이라는 것을 알기 때문에 루프에서 빠져 나옵니다. 이 경우 샘플 입력 9의 경우 루프에서 빠져 나옵니다. 시 저는 8 = I = 1 (7) -.
이제 몇 가지 시나리오를 확인하겠습니다.
assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9));
assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));이 접근 방식 의 최악의 시간 복잡도 는 입력이 정확한 거듭제곱 2일 때 O(N/2)입니다 . 우리가 볼 수 있듯이 이것은 가장 효율적인 솔루션은 아니지만 올 수 있으므로 이 기술을 아는 것이 좋습니다. 유사한 문제를 해결할 때 편리합니다.
6. 결론
우리는 주어진 숫자보다 작은 2의 가장 큰 거듭제곱을 찾는 다양한 접근 방식을 보았습니다. 또한 비트 연산이 경우에 따라 계산을 단순화할 수 있는 방법도 확인했습니다.
이 기사에 대한 단위 테스트가 포함된 전체 소스 코드는 GitHub 에서 찾을 수 있습니다 .
