[Algorithm]가장 가까운 2의 멱수

BMP 이미지같은 파일 포맷은 가로(width)가 반드시 4bytes 의 배수가 되어야 한다.

이때 발생하는 padding을 계산하기위해, Width 보다 크고 가장 가까운 4의 배수를 찾아야한다.

고등학생 프로그래머 같이 생각하면, 아래와 같다.(교수님 ㅠㅠ)

int padding=width%4;  
if(padding%4!=0){  
    padding=4-padding%4;
}

조금 더 심플하고, 2진수답게 생각하면,

int padding = ((width+3)&~3)-width;  

원리는 간단. 4의 배수는 최하위2비트가 무조건 0이다.

따라서, width 보다 바로큰 다음 합동수를 구하기 위해 3을 더하고 이 수에서 최하위 2비트를 0으로 만들면된다.

조금더 생각해보면 모든 2의멱수를 이런식으로 생각할 수 있다.

n이 입력되는 수이고, x가 해당 2의 멱수, a가 결과라고 하면 소스는 아래와 같다.

int foo(int n,int x){  
    int a=(n+x-1)&~(x-1);
    return a;
}