주어진 입력에 가장 가까운 2^N 값을 찾는 방법은 무엇입니까?

Question

지수 함수의 출력이 입력 값을 초과 할 때까지 아무래도 내 프로그램을 계속 실행 한 다음이를 지수 함수의 이전 출력과 비교해야합니다. 의사 코드 (pseudocode) 일지라도 어떻게 그런 짓을 할 수 있을까요? 대상에 가까운 쪽 1.

동안 X < 타겟

Answer 1

1. 것은 주어진 번호 => X (2)로부터의 기준이 대수 찾기 = 원 (X)
2. + 1^Y, 2^Z2는 검색 입력이 둘을 비교하여 I 쉬운 입력으로 5를 사용 더

Answer 2

집합 X 설정 X = 2 * X

그런 다음 복귀 X 또는 X/2. = 로그 (2- 입력) 모두 상하 => Y 1 단계에서 취득 된 값 라운드

: = 라운드 (X) Z

Answer 3

public static int neareastPower2(int in) { 
    if (in <= 1) { 
     return 1; 
    } 
    int result = 2; 

    while (in > 3) { 
     in = in >> 1; 
     result = result << 1; 
    } 

    if (in == 3) { 
     return result << 1; 
    } else { 
     return result; 
    } 
} 

Answer 4

맞는 하나를 선택 예 대신 50.

• 입력을 비트/바이트로 변환하십시오.이 경우 101
• 2의 제곱을 찾고 있으므로 답은 모두 10000 ... 00 (일정량의 제로가있는 숫자)입니다. . 입력 값 (3 비트)을 가져 와서 100 (3 비트) 및 1000 (4 비트)의 정수 값을 계산합니다. 정수 100은 입력보다 작을 것이고, 정수 1000은 더 커질 것입니다.
• 입력 값과 가능한 두 값의 차이를 계산하고 가장 작은 값을 사용합니다. 검색된 응답이 1000 = 8 (차분 3)하지만,이 경우에서는 100 = 4 (1 차) 빠른에 따라 될 수있는 하나 용액도있어 반복 이격 4

Answer 5

public static int neareastPower2(int in) { 
    return (int) Math.pow(2, Math.round(Math.log(in)/Math.log(2))); 
} 

Answer 6

컴파일러는 nlz 명령을 매핑하는 방법 :

public int nextPowerOfTwo(int val) { 
    return 1 << (32 - Integer.numberOfLeadingZeros(val - 1)); 
} 

명시 적 루프와 Math.pow를 사용하여 솔루션에 비해 확실히 더 효율적입니다. numberOfLeadingZeros에 대해 컴파일러가 생성하는 코드를 보지 않고도 더 많이 말하기가 어렵습니다.

그러면 우리는 쉽게 2의 저력을 얻고 어느 쪽이 더 가까운 지 비교할 수 있습니다. 마지막 부분은 나에게 맞는 각 솔루션에 대해 수행되어야합니다.

Answer 7

사용중인 언어에 따라 비트 단위 연산을 사용하여 쉽게 수행 할 수 있습니다. 단일 1 비트 세트가 입력 값에 설정된 최상위 비트보다 큰 값 또는 입력 값에서 가장 높은 1 비트 세트가있는 값을 원합니다.

가장 높은 세트 비트보다 작은 비트를 모두 1로 설정하면, 다음으로 큰 2의 제곱으로 끝나는 비트를 추가하십시오. 당신은 2의 다음 낮은 힘을 얻고 2의 더 가까운 것을 선택하기 위해 이것을 오른쪽으로 바꿀 수 있습니다.

unsigned closest_power_of_two(unsigned value) 
{ 
    unsigned above = (value - 1); // handle case where input is a power of two 
    above |= above >> 1;   // set all of the bits below the highest bit 
    above |= above >> 2; 
    above |= above >> 4; 
    above |= above >> 8; 
    above |= above >> 16; 
    ++above;      // add one, carrying all the way through 
            // leaving only one bit set. 

    unsigned below = above >> 1; // find the next lower power of two. 

    return (above - value) < (value - below) ? above : below; 
} 

다른 유사한 트릭을 보려면 Bit Twiddling Hacks을 참조하십시오.

Answer 8

다음은 입력 번호를 받아 답을 반환하는 함수의 의사 코드입니다.

int findit(int x) { 
    int a = int(log(x)/log(2)); 
    if(x >= 2^a + 2^(a-1)) 
    return 2^(a+1) 
    else 
    return 2^a 
} 

Answer 9

다음은 비트 솔루션입니다. 넥타이의 경우 2^N 및 2^(N + 1)의 렌털을 반환합니다. 이것은 log() 함수를 호출하는 것과 비교할 때 매우 빠릅니다.

let mask = (~0 >> 1) + 1 

while (mask > value) 
    mask >> 1 

return (mask & value == 0) ? mask : mask << 1