今天主要是来研究梅森旋转算法，它是用来产生伪随机数的，实际上产生伪随机数的方法有很多种，比如线性同余法，
平方取中法等等。但是这些方法产生的随机数质量往往不是很高，而今天介绍的梅森旋转算法可以产生高质量的伪随
机数，并且效率高效，弥补了传统伪随机数生成器的不足。梅森旋转算法的最长周期取自一个梅森素数，
由此命名为梅森旋转算法。常见的两种为基于32位的MT19937-32和基于64位的MT19937-64。
由于梅森旋转算法是利用线性反馈移位寄存器（LFSR）产生随机数的，所以我们先来认识线性反馈移位寄存器。
首先，移位寄存器包括两个部分
（1）级，每一级包含一个比特，比如11010110是一个8级的移位寄存器产生的
（2）反馈函数，线性反馈移位寄存器的反馈函数是线性的，非线性反馈移位寄存器的反馈函数是非线性的
一个，当然这个最大周期跟反馈函数有很大关系，线性反馈函数实
际上就是这个级的移位寄存器选取“某些位”进行异或后得到的结果，这里的“某些位”的选取很重要，得到线性反馈
函数之后，把这个移位寄存器的每次向右移动一位，把最右端的作为输出，把“某些位”的异或结果作为输入放到最左
端的那位，这样所有的输出对应一个序列，这个序列叫做M序列，是最长线性移位寄存器序列的简称。
上面“某些位”的选取问题还没有解决，那么应该选取哪些位来进行异或才能保证最长周期为，这是一个很重要
的问题。选取的“某些位”构成的序列叫做抽头序列，理论表明，要使LFSR得到最长的周期，这个抽头序列构成的多项
式加1必须是一个本原多项式，也就是说这个多项式不可约，比如。
下面以一个4位的线性反馈移位寄存器为例说明它的工作原理。
如果的值分别是1 0 0 0，反馈函数选取，那么得到如下序列
可以看出周长为15。在这一个周期里面涵盖了开区间内的所有整数，并且都是没有固定顺序出现的，有
很好的随机性。
之前说过，，梅森旋转算法的周期为，那么说明它是一个19937级的线性反馈移位寄存器，实际上基于32位
的MT19937-32只需要用到32位，那么为什么要选择周长为的算法呢？ 那是因为这样做随机性很好。
梅森旋转算法是基于线性反馈移位寄存器的一直进行移位旋转，周期为一个梅森素数，果然是名副其实。
代码：
#include <iostream>#include <string.h>#include <stdio.h>#include <time.h> using namespace std; bool isInit;int index;int MT[624]; //624 * 32 – 31 = 19937 void srand(int seed){index = 0;isInit = 1;MT[0] = seed;//对数组的其它元素进行初始化for(int i = 1; i < 624; i++){int t = 1812433253 * (MT[i – 1] ^ (MT[i – 1] >> 30)) + i;MT[i] = t & 0xffffffff; //取最后的32位赋给MT[i]}} void generate(){for(int i = 0; i < 624; i++){// 2^31 = 0x80000000// 2^31-1 = 0x7fffffffint y = (MT[i] & 0x80000000) + (MT[(i + 1) % 624] & 0x7fffffff);MT[i] = MT[(i + 397) % 624] ^ (y >> 1);if (y & 1)MT[i] ^= 2567483615;}} int rand(){if(!isInit)srand((int)time(NULL));if(index == 0)generate();int y = MT[index];y = y ^ (y >> 11);//y右移11个bity = y ^ ((y << 7) & 2636928640); //y左移7个bit与2636928640相与，再与y进行异或y = y ^ ((y << 15) & 4022730752); //y左移15个bit与4022730752相与，再与y进行异或y = y ^ (y >> 18);//y右移18个bit再与y进行异或index = (index + 1) % 624;return y;} int main(){srand(0); //设置随机种子int cnt = 0;for(int i = 0; i < 1000000; i++){if(rand() & 1)cnt++;}cout<<cnt / 10000.0<<"%"<<endl;return 0;}
实际上在很多语言中的随机数函数都已经采用了梅森旋转法实现，比如Python中的随机数模块random就是采用了梅
森旋转算法来产生伪随机数列，C++11中也有梅森旋转算法实现的随机数生成器。
梅森旋转算法在信息指纹技术中的应用
在百度或者Google这样的搜索引擎中，爬虫要对爬取的网页进行判重，这个是通过信息指纹来实现的。具体来说就
是把每一个网址随机地映射到128位二进制，这样每一个网址只占用16个字节的空间，这个128位的随机数就是这个
网址的信息指纹，可以证明，只要产生的随机数足够好，那么就可以保证几乎不可能有两个网址的信息指纹相同，就
如同不可能有两个人的指纹相同一样，而梅森旋转算法是产生高质量伪随机数的算法。
有关梅森旋转算法的详细资料，参考Wiki：
如果爱，请深爱;如不爱，请离开。
