1 에서 n 까지 이 n 개의 정수 간 의 이 또는 값 구하 기 (O (1) 알고리즘)

1301 단어
  : 1 n n        ,  1 xor 2 xor 3 ... xor n



  f(x, y)  x y         。



  f(2^k, 2^(k+1) -1) (       ^     “ ”,xor   “  ”,or   “ ”):

2^k   2^(k+1) -1  2^k  ,   (+k ) 1   2^k,

  k >= 1, 2^k   ,  2^k      (+k )  ,     。

   f(2^k, 2^(k+1) -1) = f(2^k - 2^k, 2^(k+1) -1 -2^k) = f(0, 2^k -1)

   f(0, 2^(k+1) -1) = f(0, 2^k -1) xor f(2^k, 2^(k+1) -1) = 0 (k >= 1)

  f(0, 2^k - 1) = 0 (k >= 2)



  f(0, n)  (n >= 4)  n    1  +k (k >= 2),

f(0, n) = f(0, 2^k - 1) xor f(2^k, n) = f(2^k, n)

 2^k n n+1-2^k  ,   (+k )   m = n+1-2^k  1,      1



 n    ,m   ,   f(0, n) = f(2^k, n) = f(0, n - 2^k)

  n - 2^k   n   ,       ,  :f(0, n) = f(0, n % 4)

  n % 4 == 1  , f(0, n) = f(0, 1) = 1

  n % 4 == 3  , f(0, n) = f(0, 3) = 0



 n    ,m   ,   f(0, n) = f(2^k, n) = f(0, n - 2^k)  or  2^k

    ,   1    ,  n - 2^k   n   ,       ,

  :f(0, n) = nn or  f(0, n % 4)   (nn  n   2  0)

  n % 4 == 0  , f(0, n) = n

  n % 4 == 2  , f(0, n) = nn or  3 = n + 1 (    n = 2   )



    :

f(1, n)  =  f(0, n)  =

   n      n % 4 == 0

   1      n % 4 == 1

   n +1   n % 4 == 2

0      n % 4 == 3



  :

unsigned xor_n(unsigned n)

{

 unsigned t = n & 3;

 if (t & 1) return t / 2u ^ 1;

 return t / 2u ^ n;

}

참고:http://www.저희. com / article / 5002742. htm

좋은 웹페이지 즐겨찾기