Posted at

うるう年判定をビット演算で行う

More than 3 years have passed since last update.

うるう年判定は、4の倍数を判定するのでビット演算が使えますね。

(year & 3) == 0 && year % 100 != 0 || year % 400 == 0

(year & 3) == 0の部分がビット演算での4の倍数判定です。

javaのGregorianCalendarの中の人も使ってます。

で、なんとなく調べてみたら

(year & 3) == 0 && ((year % 25) != 0 || (year & 15) == 0)

ってのが出てきて、意味わからんΣ(゚д゚;)ってなったので調べてみようと思いました。

(タグはjavaにしてますけどC系でも一緒だと思います)

参考:

http://stackoverflow.com/questions/1021324/java-code-for-calculating-leap-year

http://stackoverflow.com/questions/3220163/how-to-find-leap-year-programatically-in-c/11595914#11595914

(2個目の参考ページにも説明がある雰囲気ですが、英語なのも相まって僕には理解不能でした。)


各判定要素の意味

それぞれ判定要素の意味は下記です。

判定要素
意味
補足

(year & 3) == 0
4の倍数
ビットで下2桁が0の場合は4の倍数

(year % 25) != 0
25の倍数以外
*

(year & 15) == 0
16の倍数
ビットで下4桁が0の場合は16の倍数


4と25の最小公倍数が100

次に始めの判定式のorがわかりづらいので分配法則で書き換えます。

((year & 3) == 0 && (year % 25) != 0) || ((year & 3) == 0 && (year & 15) == 0)

つまり

((year & 3) == 0 && (year % 25) != 0) || (year & 15) == 0

になるので、まとめると下記のようになります。

判定
意味
言い換え
補足

(year & 3) == 0 && (year % 25) != 0
4の倍数で25の倍数でない
4の倍数で100の倍数でない
4と25の最小公倍数が100みたいです

(year & 15) == 0
16の倍数
*
*


25と16の最小公倍数が400

あとは16の倍数がわかりづらいですが、これは書き換え前の元の状態で考えた方がわかりやすかったです。

((year % 25) != 0 || (year & 15) == 0)

の部分です。

これは、

1つ目の条件でほとんどの25の倍数がfalseになります。

2つ目の条件は16の倍数でtrueなるので、

合わせると25と16の最小公倍数が400のため

25の倍数の中でtrueになるのは400の倍数の時だけになります。


まとめ

簡単にまとめると

4と25の最小公倍数が100で

25と16の最小公倍数が400なので

うまくいくということでしょうか(?)

最小公倍数は下記で調べました。

http://www.calc-site.com/divisors/lcm_two


結果わかったような余計わからなくなったような。

世の中には効率的な演算をこだわって考える人がいるんだなって思いました。