ある連続した整数群の XOR
の結果を取得したい。
- 引数は、MとN の2つの整数
- M > 0
- N > M
- M から N までの連続した整数の
XOR
を結果として返す- 例えば X = 5, N = 8 の場合以下の通り(括弧で括った部分は2進数表現)
- answer = 5 ^ 6 ^ 7 ^ 8 = (101 ^ 110 ^ 111 ^ 1000) = (011 ^ 1111) = (1100) = 12
- 例えば X = 5, N = 8 の場合以下の通り(括弧で括った部分は2進数表現)
愚直にやるなら以下の通りです。
public class Solution1 { public static int solution(int M, int N) { return xors(M, N); } public static int xors(int M, int N) { int value = M; for (int i = M; i < N; i++) { value = value ^ (i + 1); } return value; } }
ただし、以下のコードでもいけるっぽい。
public class Solution2 { public static int solution(int M, int N) { return xORTrick(N) ^ xORTrick(M - 1); } private static int xORTrick(int n) { if (n % 4 == 0) { return n; } if (n % 4 == 1) { return 1; } if (n % 4 == 2) { return n + 1; } return 0; } }
いけるっぽいと書いてるのは、私がコードの内容を理解してないからです・・・。
理解してないもの載せるのもどうかとは思いつつも、載せちゃいました(汗)。
(後者の方が圧倒的に高速に動作します)