平方数を4で割った余り

平方数判定をする際にいくらか高速化できるテクニックを知ったのでメモしておく。

nが偶数の平方の場合は、
n = 2k * 2k = 4k^2
と表すことが出来る。よって4で割った余りは0。

nが奇数の平方の場合は、
n = (2k + 1) * (2k + 1) = 4k^2 + 4k + 1
と表すことが出来る。よって4で割った余りは1。

ということで、3とビットのandを取って1より大きくなった場合、その 数は平方数ではないことが分かる。