题目：数组中有三个数只出现一次，其它的数恰好出现两次，找出这三个数。

    先考虑“只有两个数出现一次”的情况：可以找到一种方法，将数组划分为两部分，且让这两个数分别在不同部分，这样每部分所有数的异或值，恰好分别等于这两个数。一种简单的分法就是，先计算出这两个数的异或值M（等价于求数组中所有数的异或值），求出M值的二进制表示中的最低位1（其它位的1也可以，只不过麻烦点）在 +k位，然后根据 +k位是否为1，将原数组分为两部分。

    回到原题，假设这三个不同的数是：A、B、C，它们的异或值 X = A xor B xor C，X值可能为0，也可能不为0。当X值不为0时（比如：这三个数为3、5、7，X值为1），很难找到一种方法，将原来的数组划分为两部分，使得这三个数不都在同一部分。因而，要先对原来的数组进行一次替换：将每个数与X进行异或。这样原来的三个数就变成了：

B xor C、A xor C、A xor B。记a = B xor C、b = A xor C、c = A xor B。新的异或值 x = a xor b xor c = 0。

    由于A、B、C互不相等，显然它们间的异或值a、b、c都不为0，且互不相等。（若a等于b，则 0 = a xor b = (B xor C) xor (A xor C) = A xor B != 0自相矛盾）

若三个数的异或值为0，且其中一个数在 +n位（n为任意值）上为1，则另两个数在 +n位上必然一个为1，另一个为0（不然的话，这三个数的异或值就不会为0），因而根据 +n位为1，可以将这三个数分成两部分。

设f(x)为x的二进制表示中最低位1的位置，则f(a)、f(b)、f(c)这三个数中有且只有两个数相等。证明：不妨设f(a)、f(b)、f(c)中最小的是f(a)，k = f(a)，则b、c在 +k位上必然是一个为1，一个为0，不妨设b在 +k位为1，则根据f(x)的定义以及f(a)最小，可得f(b)等于f(a)，f(c)大于f(a)。因而，新数组的数x对应的所有f(x)的总异或值等于f(c)。

假设f(a)等于f(b)，m = f(c)，由于c在 +m位上为1，不妨设 b在 +m位也为1，则a在 +m位为0。根据 +m位是否为1，可将新数组分为两部分，每部分的异或值恰好都是 a = B xor C，可以求出数A（等于a xor X）。 将数A放入原来的数组，问题转为“只有两个数出现一次”的情况，利用前面提到的方法算出另两个数。总共需遍历数组4次。

代码：

#include <cstdio>

#include <cassert>

static inline int extract_rightmost_one(unsigned value) { return value & -value; }

// if a != b, m = extract_rightmost_one(a), n = extract_rightmost_one(b),

//             k = extract_rightmost_one(a ^ b)

// then m == n != k   or   m == k != n   or n == k != m

void print_three_unique_number(const int arr[], unsigned len)

{

 assert (len >= 3 && len % 2);

 const int* const beg = arr;

 const int* const end = arr + len;

 int xor3 = 0;

 for (const int* p = beg; p != end; ++p) xor3 ^= *p;

 int flag1 = 0;

 for (const int* p = beg; p != end; ++p) flag1 ^= extract_rightmost_one(*p ^ xor3);

 assert(flag1 != 0 && (flag1 & (flag1 - 1u)) == 0u); // flag1 == 2^^k

 int xor2 = 0;

 for (const int* p = beg; p != end; ++p) {

    const int value = *p ^ xor3;

    if (value & flag1) xor2 ^= value; //or:

    // if ((value & flag1) == 0) xor2 ^= value;

 }

 const int number1 = xor2 ^ xor3;

 const int flag2 = extract_rightmost_one(xor2);

 int number2 = (number1 & flag2) ? number1 : 0; // put number1 into the array

 for (const int* p = beg; p != end; ++p) {

    if (*p & flag2) number2 ^= *p;

 }

 const int number3 = xor2 ^ number2;

 printf("%d %d %d\n", number1, number2, number3);

}

上面的代码并不严格符合C++标准，而是假定机器采用补码表示负数（不采用补码表示的老古董，一般人也碰不到）。 另外要特别注意的是，一些计算最好先转为无符号数，避免溢出，最后再转回有符号数。因为标准假定有符号数间的计算不发生溢出，当实际上发生溢出时，就是UB行为，编译器若进行些激进的优化就得不到正确结果。

先看一道面试题：

长度为n的数组，由数字1到n组成，其中数字a不出现，数字b出现两次，其它的数字恰好出现一次。怎样通过只读遍历一次数组，找出数字a和b。

由于只能遍历一次，在遍历数组arr时，算出 a和b的差值，以及a和b的平方差，通过解方程，即可求得a和b。具体做法为：

设：

      s1 = 1 + 2 + ... + n           (= n * (n + 1) / 2)

      s2 = arr[0] + arr[1] + ... + arr[n - 1]

      r1 = 1 + 4 + ... + n^2          (= n * (n + 1) * (2 * n + 1) / 6)

      r2 = arr[0]^2 + arr[1]^2 + ... + arr[n - 1]^2

     c = a - b = s1 - s2

     d = a^2 - b^2 = r1 - r2

    显然：  a + b = (r1 - r2) / (s1 - s2)

根据a+b的值和a-b的值，很容易就可算出a和b。

算法虽然简单，但实现起来，却有一个很大问题：计算 s1、s2、r1、r2这4个数时，计算过程中可能出现溢出，造成结果不准。由于最终目的是为了计算出c和d，一个改进的方法是：

 c = s1 - s2 = (1 - arr[0]) + (2 - arr[1]) + ... + (n - arr[n - 1])

 d = (1 - arr[0]^2) + (4 - arr[1]^2) + ... + (n^2 - arr[n - 1]^2)

但这样的做法，并不能解决问题，n稍微大点，照样存在溢出问题。

那么怎样才能避免计算溢出呢？答案很简单，用模运算！每进行一次加减运算时，都取结果为原结果除以一个足够大的常数M的余数。这样加减运算中，就不会现现溢出问题。最后再由 c % M、d % M，推测出c、d的具体值。比如说，计算s2改为计算：

   s2 % M = ((((arr[0] % M) + arr[1]) % M + ...) % M + arr[n - 1]) %M

从表面上看，采用模运算后，计算量会增加很多。但实际上，若M取合适的值时，计算量并不会增加！！

先回顾下计算机基本知识：两个各N位（寄存器为N位）的二进制无符号整数a和b相加，若结果溢出了，CPU会怎么处理？当然是将溢出的那一位忽略掉（可能还要设置下溢出标志），得到的结果实际上是：(a + b) mod 2^N。无符号数间的算术运算，本质上就是模运算。现在的CPU都采用二补数来表示负整数，本质上也是运用模运算（教科书将二补数表示的负整数简单定义为：对正整数取反后加1），这与无符号数间的运算是一致的，在实现上，比用其它方法（比如说一补数）表示负整数，要优美易实现。

在32位平台下， -x mod 2^32 = 2^32 – x (x > 0)，

因而-1的二进制表示就是：0xFFFFFFFF

了解了这些，就不会奇怪C/C++标准的规定：无符号数间的运算是模运算不会溢出；有符号数转为无符数，采用模运算后的值。（为了兼容没采用二补数的机器，无符号数转为有符号数时，若无符号数的数值超出了有符号数可表示的范围，结果是平台相关的。）

因而，在对32位CPU平台，可以先将有符号数转为无符号数，再取M = 2 ^32。需要特别注意的是，应该采用多少位的无符号数保存计算中用到的数值，如何避免模运算可能带来的问题：

①　无符号数类型的选择：

a、b的取值范围为：[1, n]，

c % M = (a - b) % M 的取值范围为：[1, n] (a > b时)，   [M - n, M - 1] (a < b时)

这两个范围不能重叠，而因 n < M - n 即 2 * n < M

若 M取2^32的话，且 n < 2^31， 可以采用32位无符号数表示c的值。

根据c % M值在哪一个范围，可以确定a > b还是a < b，

由于运算过程中都是采用无符号数计算，当 a < b时，必须进行如下调整：

        c % M 调整为 (-c) % M

        d % M 调整为 (-d) % M

这样才能保证结果的正确性。

② 用公式计算所有数字的和、平方和时，可能出现的问题：

   模运算满足： (a * b) % M  = ((a % M) * (b % M)) % M

     但不满足： (a / b) % M  = ((a % M) / (b % M)) % M

   在计算 (n * (n + 1) / 2) % M时， 不能写成：

      s = ((n * (n + 1)) % M / 2) % M，

   而应该写成：

     if  (n % 2 == 0)   s = ((n / 2) * (n + 1)) % M

     else             s = (((n + 1) / 2) * n) % M

   或者：s = (INT((n + 1) / 2) * (n + (n + 1) % 2)) % M （其中INT(x)为取小数x的整数部份）。

完整代码：

#include <climits>
#include <cassert>

#define SMALL_ARRAY 0

struct Pair {
  int zero;
  int twice;
};

//32位CPU平台，长度n一定小于2^16次方时，表示一个数的平方值，可用32位无符号数类型，效率很高。
//长度n若在[2^16, 2^31]区间，就必须用到64位无符号数类型，效率较高。
//长度n若在[2^31, 2^32)时，表示 所有数的和sum，就必须改用64位无符号数类型，效率不高。  
Pair find_number(const int arr[], unsigned len)
{
  const unsigned bits = CHAR_BIT * sizeof(unsigned);
#if SMALL_ARRAY
  const unsigned max_len = 1u << (bits / 2u);
  typedef unsigned int uint;
#else
  const unsigned max_len = 1u << (bits - 1);
  typedef unsigned long long uint;
#endif

  assert(arr && len >= 2 && len < max_len);
  const unsigned* const data = (const unsigned*)arr;
  unsigned sum = 0;
  uint square_sum = 0;
  for (unsigned i = 0; i < len; ++i)  {
    const unsigned value = data[i];
    sum += value;
    square_sum += (uint)value * value;     //注意两个数的乘积是否会溢出  
  }
  
  //1 + 2 + 3 +  + len = len * (len + 1) / 2
  const uint sum_all = (len + 1) / 2u * (uint)(len + (len + 1) % 2u);
  
  //1^2 + 2^2 + 3^2 +  + len^2 = len * (len + 1) * (2 * len + 1) / 6
  const unsigned len2 = 2u * len + 1;
  const uint square_sum_all = len2 % 3u == 0 ? len2 / 3u * sum_all : sum_all / 3u * len2;
  
  unsigned difference = (unsigned)sum_all - sum;
  uint square_difference = square_sum_all - square_sum;
  const bool is_negative = difference > INT_MAX;

  if (is_negative) {
    difference = -difference;
    square_difference = -square_difference;
  } 
   
  assert(difference != 0 && square_difference % difference == 0);
  const unsigned sum_two = square_difference / difference;
  
  assert((sum_two + difference) % 2u == 0);
  const unsigned larger  = (sum_two + difference) / 2u;
  const unsigned smaller = (sum_two - difference) / 2u;
  
  if (is_negative) {
    const Pair result = { smaller, larger};
    return result;
  }
  const Pair result = { larger, smaller};
  return result;
}


int main()
{

}

喝汽水问题

                                                  by flyinghearts

有1000瓶汽水，喝完后每3个空瓶能换1瓶汽水，问最后最多可以喝几瓶汽水，此时剩余几个空瓶？

不妨假设，共有n瓶汽水，每a个空瓶能换b瓶汽水（a > b）。刚开始有n瓶汽水，喝完后就有n个空瓶，多喝的汽水是靠空瓶换来的，每进行一次空瓶换汽水，就能多喝b瓶汽水、空瓶数目就减少了a-b个（a个空瓶换了b瓶汽水，喝完后得到b个空瓶）。

(下面用 [x] 表示x的整数部分)

1 如果允许从别处（老板或其他顾客处）借空瓶（当然，有借有还）

空瓶换汽水次数：   [n / (a - b)]

最后剩余空瓶：     n % (a - b)

总共可以喝到汽水： n + [n / (a - b)] * b

2 不允许借空瓶

 空瓶换汽水过程中，一但空瓶数小于a，则停止交换。

 对 n < a，显然，空瓶换汽水次数为0，总共可以喝到汽水n瓶，最后剩余空瓶n个

 对 n >= a：（下面提供三种解法）

  解法一    空瓶换汽水次数k等于满足n – (a-b)*t < a的最小非负整数t:

              t > (n-a)/(a-b)，最小的t为 [(n-a)/(a-b)] + 1 = [(n-b)/(a-b)]

              剩余的空瓶数：n – (a-b)*t

= n – (a-b)*([(n-b)/(a-b)])

                           = b + (n-b) - (a-b)*([(n-b)/(a-b)])

= b + (n-b)%(a-b)

解法二   先预留a个空瓶，将剩余的n-a个空瓶进行换汽水，换的过程中，若空瓶不够a个，则从预留的a个空瓶中“借”，因而，

空瓶换汽水次数：[(n-a)/(a-b)] + 1 = [(n-b)/(a-b)]（预留的a个空瓶也能换一次）

最后剩余空瓶： (n-b) % (a-b) + b（预留的a个空瓶换得b瓶汽水）

解法三   最后一次空瓶换汽水得到的b瓶汽水，喝完后得到b个空瓶，因而最后剩余空瓶数必然大于b个，先预留b个空瓶，将剩余的n-b个空瓶进行换汽水，若空瓶不够a个，则从预留的b个空瓶中“借”（由于能进行空瓶换汽水，空瓶数>= a – b，因而“借”完后，可以保证空瓶数大等于a），

           空瓶换汽水次数：[(n-b)/(a-b)]，

最终剩余空瓶数：b + (n-b) % (a-b)

（对解法三，n>=b时结论成立，对解法一、二，可以验证n >=b时，结论也成立）

因而，对 n >= b

空瓶换汽水次数：   [(n-b)/(a-b)]

最后剩余空瓶：     b + (n-b) % (a-b)

总共可以喝到汽水： n + [(n-b)/(a-b)] * b

对原题：

 n = 1000，a = 3, b = 1， a – b = 2

 若允许借空瓶    

可以喝到汽水： 1000 + 1000 / 2 = 1500

剩余空瓶：1000 % 2 = 0

若不允许借空瓶

可以喝到汽水： 1000 + (1000 - 1) / 2 = 1499，

剩余空瓶：     1 + (1000 - 1) % 2 = 2

import std.stdio : writef;

uint fib_matrix(uint num) // 矩阵法求fibonacci数

{

 if (num <= 1) return num;

 --num;

 uint ret = 1, next = 1;

 for (uint a = 1, b = 0; num != 0; num >>= 1) {

    if (num & 1) {

       auto tmp = next;

       next = (a + b) * next + a * ret;

       ret = a * tmp + b * ret;

      }

      auto tmp = a;

      a = a * (a + 2 * b);

      b = b * b + tmp * tmp;

 }

 return ret;

}

uint fib(uint num)

{

 if (num <= 1) return num;

 uint left_most_one = num; //小等于num的最大2的k次幂

 for (uint value = num; value &= (value - 1); ) left_most_one = value;

 uint ret = 1, next = 1;

 while (left_most_one >>= 1) {

    if (num & left_most_one) {

       auto tmp = ret;

      ret = ret * ret + next * next;

      next = (tmp * 2 + next) * next;

    } else {

       auto tmp = ret;

      ret = (next * 2 - ret) * ret;

      next = tmp * tmp + next * next;

    }

 }

 return ret;

}

uint fib_basic(uint num)

{

 if (num <= 1) return num;

 uint prev = 0, current = 1;

 for (uint i = 2; i <= num; ++i) {

    auto tmp = prev;

    prev = current;

    current += tmp;

 }

 return current;

}

unittest {

 foreach (i; 0 .. 48) {

    auto a = fib_basic(i), b = fib_matrix(i), c = fib(i);

    if (a != b || a != c)

      writef("%s %s %s %s\n", i, a, b, c);

 } 

}

void main()

{

}