power-of-two size 찾기

Memory allcation에 대해서 공부하다가 요청하는 숫자에 적합한 2의배수 값을 찾아주는게 필요해서 한번 간단히 짜봤다.

// 처음 1이 나오는 MSB 위치를 리턴 : 0-31
unsigned int SearchMSB(unsigned int n)
{
    unsigned int i;
    for (i=0; i<32; i++) {
        if (0x80000000 == (n & 0x80000000))
            break;
        n <<= 1;       
    }
    return i;
}

unsigned int FindFitSize(unsigned int n)
{
    unsigned int msb = SearchMSB(n);
    unsigned int tmp = SearchMSB((1 << (31-msb)) - 1 + n);
    return 1 << (31-tmp);
}

int _tmain(int argc, _TCHAR* argv[])
{
    while(1)
    {
        int n;
        printf("input number : ");
        scanf("%d",&n);
        printf("fit size : %u\n\n", FindFitSize(n));
    }
    return 0;
}

여기서 SearchMSB의 경우는 거의 모든 CPU에서 한사이클짜리 단일 asm으로 제공되어진다. (linux의 O(1) 스케쥴링 알고리즘이 그걸 이용함. - 물론 코드 분석한건 아니고 주워들은 얘기 ㅎㅎㅎ - TI DSP에도 _lmbd 라는 명령어로 존재한다.)

FindFitSize의 결과는 64를 넣으면 딱 맞으니까 64를 리턴하고,  65를 넣으면 128을 리턴하는 것. 또 나중에 생각하기 귀찮아서 생각난김에 플밍하고 기록해둠~ ^^;;