Проверка високосного года с использованием побитовых операторов (удивительная скорость)

Кто-то из JSPerf потерял удивительно быструю реализацию для проверки високосных лет календаря ISO (ссылка: Нечетные манипуляции с битами):

function isLeapYear(year) {
  return !(year & 3 || year & 15 && !(year % 25));
}

Используя Node.js, я быстро проверил его против двух других реализаций одной строки, которые я знаю.

function isLeapClassic(y) { return (y % 4 == 0) && !(y % 100 == 0) || (y % 400 == 0); }
function isLeapXOR(y) { return (y % 4 == 0) ^ (y % 100 == 0) ^ (y % 400 == 0); }
function isLeapBitwise(y) { return !(y & 3 || y & 15 && !(y % 25)); }

//quick'n'dirty test on a small range!
//works with negative integers too
for (var i = 1900; i <= 2100; i++) {
    console.log(
        "year = %d,\t%d%d%d",
        i,
        isLeapClassic(i),
        isLeapXOR(i),
        isLeapBitwise(i)
    );
}

Он работает так, как ожидалось, но моя проблема в том, что я не могу понять, как это сделать. Я знаю ((a % b) == (a & (b-1)), когда значение b равно двум, поэтому (year % 4) == (year & 3), но year & 15 && !(year % 25) довольно сложно понять. Может кто-нибудь объяснить мне, как это работает? Любая ссылка об этой реализации?

Ответы

Ответ 1

year & 3 совпадает с year % 4. Не так сложно, он просто представляет собой обычный 4-летний цикл.

year & 15 совпадает с year % 16.

Итак, это не високосный год, если год не разделяет равномерно на 4, или если он не разделяет равномерно на 16, а равно равномерно на 25. Это означает, что каждый кратный 25 не является високосным годом если он также не кратен 16. Поскольку 16 и 25 не имеют каких-либо общих факторов, единственное время, в течение которого выполняются оба условия, - это год, когда год кратен 16 * 25 или 400 лет. Количества 4 * 25 будут считаться не високосные годы, составляющие 100-летний цикл.

1900 не был високосным годом, потому что он был делимым на 100, 2000 год был високосным годом, потому что он был делимым на 400, а 2100 не был високосным годом.

Ответ 2

Если число делится на 16 и делится на 25, оно делится на четыре раза 25 (100), а также 16 раз 25 (400).