1.無序數(shù)組的二分應(yīng)用

無序數(shù)組，相鄰不等，找出一個局部最小?？捎枚?。
思路：

• 首先判定兩端是不是比其相鄰的小，如果是直接返回局部最小的位置。
• 否則，說明中間必定存在局部最小。選取兩者的middle，判斷middle是都是局部最小，如果是返回middle。
• 否則，根據(jù)趨勢重復(fù)步驟二。

2.異或運(yùn)算

基本概念

異或：相同為0，不同為1。
同或：相同為1，不同為0。

異或的基本性質(zhì)

• 0^N == N, N^N == 0
• 異或運(yùn)算滿足交換律和結(jié)合律

運(yùn)用舉例

• 1.不增加額外變量，互換兩個值，a = a^b;b = a^b;a = a^b
• 2.一個數(shù)組中有一種數(shù)字出現(xiàn)了奇數(shù)次，其他數(shù)字都出現(xiàn)了偶數(shù)次，怎么找到并打印這個數(shù)。int result = a[0
  ]^a[1]...a[n].
• 3.怎么把一個int類型的數(shù)字N，提取出最右側(cè)的1來。N&（(~N)+1）
• 4.一個數(shù)組中有兩種數(shù)字出現(xiàn)了奇數(shù)次，其它數(shù)都出現(xiàn)了偶數(shù)次，怎么找到并打印這兩種數(shù)字。
  運(yùn)用結(jié)論3。
  （a) 首先將所有數(shù)字進(jìn)行異或，得出結(jié)果eor，這個結(jié)果等于這兩個數(shù)字異或的結(jié)果。
  (b) 接著將數(shù)組中的數(shù)字根據(jù)這個異或結(jié)果進(jìn)行分組，兩組中分別找出數(shù)字。具體操作為，（i)提取eor中最右側(cè)的1，rightone（ii）如果arr[i]&rightone！=0，滿足條件的進(jìn)行異或，最終得到結(jié)果onlyone（iii）另一個結(jié)果為eor^onlyone
• 某個數(shù)字二進(jìn)制中1的個數(shù)。每次提取最右側(cè)的1，再將最右側(cè)的1給抹零，比如數(shù)字N的二進(jìn)制中1的個數(shù)
  int count = 0;
  while(N!=0){int right = N&((~N) +1);count++;N = N^right}