Geometry & Recognition

n이 양수일 때 n 과 n-1은 짝홀/홀짝의 짝이므로 2의 파워가 아니면 이진수로 표현할 때 한 곳에서 비트 차이가 난다. 따라서 AND연산을 하면 0이 아니다.  그런데 n이 2의 파워이면 최상위 비트만 1이고, n-1은 n의 최상위 비트를 제외한 하위비트 모두가 1로 구성되므로 AND 연산을 하면 0이다.

예:   n=6 = 110,  6-1=101 -->  6 & 5 = 100;

       n=8 = 1000, 8-1=0111 --> 8 & 7=0000

// n이 양수이고, n-1과 겹치는 비트가 없으면 된다;
bool IsPowerOf2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

n>1 일 떄 2로 나누기를 계속할 때 1을 제외한 홀수가 나오면 안됨; 

bool IsPowerOf2(int n) {
    if (n == 1) return true;
    if (n == 0 || n & 1) return false;
    return IsPowerOf2(n >> 1);
} // n == 0;

x보다 크기 않은 2^i을 구한 후 x와 같은가 체크;

bool IsPowerof2(int x){
    int i = 0;
    while ((1 << i) < x) i++;
    if (x == (1 << i)) return true;
    return false;
}

2의 파워이면 log_2(n) = 자연수 이므로 ceil과 floor가 같다.

bool IsPowerOf2(int n) {
   if (n == 0) return false;
   return (ceil(log2(n)) == floor(log2(n)));
}

주어진 자연수보다 작지 않은 최소의 2^n;

int NextPowerOf2(int n) { //32-bit;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    return n;    
} // NextPowerOf2(5) -> 8; NextPowerOf2(8) -> 8;