신기한 윤년 판별 알고리즘

우연히 인터넷에서 신기한 윤년 판별 코드를 발견해서 정리해 본다.

윤년의 규칙은 다음과 같다.

1. 4로 나누어떨어지는 해는 윤년, 아니면 평년
2. 100으로 나누어떨어지되 400으로 나누어떨어지지 않는 해는 평년

정리하면 4의 배수에서 100의 배수가 아닌 수 또는 400의 배수인 해이다.

이걸 C++ 코드로 나타내면 다음과 같다.

bool is_leap_year(uint32_t y) {
    return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
}

6년 전, 내가 백준에 제출했던 코드이다. 저 때도 한 줄 코드 좋아했었구나…ㅎㅎ

 

여기서 y % 100은 이미 앞에서 4로 나누었으므로 y % 25로 대체할 수 있고, y % 400은 앞에서 25로 나누었으므로 y % 16 대체할 수 있다.

여기에 나는 이해할 수 없는 여러 트릭을 적용하면 이렇게 된다.

bool is_leap_year(uint32_t y) {
    return !(y & ((y % 25) ? 3 : 15));
}

뭔진 모르겠지만 잘 작동한다. 여기에 더더욱 신기한 비트 트위들링 접근법이란 걸 사용하면

bool is_leap_year_fast(uint32_t y) {
    return ((y * 1073750999) & 3221352463) <= 126976;
}

이 따위 코드로도 윤년을 판별할 수 있다.뭐지.. 고속 역 제곱근 알고리즘인가? 참고로 이 코드는 0~102499년 범위에서 정확하다고 한다.

나는 이 코드를 이해할 수 없으니 자세한 건 아래 출처에서 읽어보길 바란다.

출처: https://hueffner.de/falk/blog/a-leap-year-check-in-three-instructions.html