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

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

16 голосов
/ 24 марта 2012

Кто-то в 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) довольно сложно понять.Может кто-нибудь объяснить мне, как это работает?Любая ссылка об этой реализации?

Ответы [ 2 ]

14 голосов
/ 24 марта 2012

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 не будет високосным.

5 голосов
/ 24 марта 2012

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

...