Exclusive or

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 327    Accepted Submission(s): 137

Given n, find the value of 






Note: ⊕ denotes bitwise exclusive-or.

3

4

6

4

题解：

以下是官方给的答案：

鉴于比較难以理解官方大神的解说，这里我研究了一下，以下给出求解化简过程：

图片有些不清晰，凑合看吧 T^T

代码：

import java.util.*;

import java.io.*;

import java.math.*;

public class Main {

	public static BigInteger zero=BigInteger.valueOf(0);

	public static BigInteger one=BigInteger.valueOf(1);

	public static BigInteger two=BigInteger.valueOf(2);

	public static BigInteger four=BigInteger.valueOf(4);

	public static BigInteger six=BigInteger.valueOf(6); 

	public static HashMap<BigInteger,BigInteger> map=new HashMap<BigInteger,BigInteger>();

	public static BigInteger solve(BigInteger n)

	{

		if(map.containsKey(n))

			return map.get(n);

		BigInteger t=BigInteger.valueOf(0);

		BigInteger k=n.divide(two);

		BigInteger r=n.mod(two);

		if(r.compareTo(one)==0)

			t=solve(k).multiply(four).add(k.multiply(six));

		else  {

			t=two.multiply(solve(k));

			t=t.add(two.multiply(solve(k.subtract(one))));

			t=t.add(four.multiply(k));

			t=t.subtract(four);

		}

		map.put(n, t);

		return t;

	}

	public static void main(String []args)

	{

        BigInteger n;

        map.put(zero, zero);

        map.put(one,zero);

        Scanner cin = new Scanner(System.in);

        while(cin.hasNext())

        {

        	n=cin.nextBigInteger();

        	System.out.println(solve(n));

        }

	}

}

/*

借鉴别人的代码，学习了一下java大数和HashMap的使用方法，能够当作模版来使用了。

*转载请注明出处，谢谢。

*/