算法-从1,...,99,2015这100个数中任意选择若干个数（可能为0个数）求异或，试求异或的期望值

题目： 从1,2,3，…..98,99,2015这100个数中任意选择若干个数（可能为0个数）求异或，试求异或的期望值。 解题思路： 这是阿里巴巴的一道笔试题目，这并不是一道编程类的题目（虽然可以用编程来解决），这更像一道数理统计的题目，由于期望性质：

那么我们可以先考虑取到的若干个数的某一位： 由于异或的特性， 对任意一个二进制位，取奇数个1异或后会得到1，取偶数个1异或后会得到0，与取0的个数无关。由于2015的二进制为：111 1101 1111，99的二进制为： 000 0110 0011。这意味着对于任何一次（0个除外）选取，选取的到若干个数的二进制数中，11位中每一位都有可能取到1，那么如果取到的1是奇数个，该位置异或后的结果就是1。 经过上面的分析，我们就可以设事件为第i位取到k个1，其中k为奇数，第i位一个共有n个1，m个0，那么事件的概率为：

于是我们可以得出一个很有意思的结论，在异或之后的二进制数中，每一位取到1的概率是0.5，那么取到0也是0.5，对于离散事件，我们就能求期望了，当然还是0.5。 那么对全部的11位整体考虑，就会用到上面期望的性质，它是11个二进制为的期望的加和：

这个问题还可以延伸一下，如果把原问题的2015换成1024，那么结果是什么呢？ 关键的问题在于2015或1024对结果的印象到底在哪里，我们计算的其实是取若干个数中某一位为1的数目是奇数的概率，那么： 1024 ：‭100 0000 0000‬ 99：000 0110 0011 这意味着，2^7,2^8,2^9着三位永远只能是0，根本就没有1，所在在计算最后的期望的时候把这三位记为0就好了，所以结果是275.5。

代码实现： 其实我们可以用代码测试一下，当采用足够大的时候，可以用均值估计期望，所以采用次数设置为10000000。

#include "iostream"    

using namespace std;

int sample(int *a)
{
    //避免生成随机数相等
    bool flag[100];
    //单次采样个数
    int  M = rand()%101;
    int  k = 0;
    int result =0;
    while (k<M)
    {
        //采样值
        int m = rand()%100;
        if(k==0)
        {
            result = a[m];
            flag[m]=0;
            k++;
        }
        if(flag[m])
        {
            flag[m]=0;
            result = result^a[m]; 
            k++;
        }       
    }
    return result;
}
int main()
{
    const int N = 100;
    int  arr[N];
    for (int i = 0;i<N-1;i++)
        arr[i]=i+1;
    arr[N-1] = 2015;
    //采样次数
    int totalnum = 10000000;
    double s=0;
    for (int j = 0;j<totalnum;j++)
    {
        s= s+sample(arr);
    }
    s = s/totalnum;
    cout<<s<<endl;
    getchar();
    return 0;
}

讲真，这个代码的效率不算好，因为为了避免生成随机数重复的情况（比如，取了两个99，但是这种情况在实际情况中不会发生），所以设置了bool型flag[100]数组，它就像一个简易的hash表，索引就是100下下标，值为0，1。某次生成随机数n，当flag[n]为flash时这个数就是重复了，那么就重新生成。 所以取若干次这个条件，如果若干次越大，那么重复的可能性就越高，重复计算也就越多，但是目前并没有找到更好的方法。