c++ - C++ 中的线性同余生成器、运算符 & 和 >>

Question

我正在研究线性同余生成器。公式为:

Xn+1 = (a * Xn + c) mod m

我在C++中发现了这样一段实现LCG的代码:

class LCG {
public:
    LCG();
    LCG(unsigned int newSeed);
    ~LCG();
    void setSeed(unsigned int newSeed);
    unsigned int getSeed(void);
    unsigned int next(void);
private:
    unsigned int seed;
    const static unsigned int a = 214013U;
    const static unsigned int c = 2531011U;
};

LCG::LCG() { seed = 1; }
LCG::LCG(unsigned int newSeed) { setSeed(newSeed); }
LCG::~LCG() { }
void LCG::setSeed(unsigned int newSeed) { seed = newSeed; }
unsigned int LCG::getSeed(void) { return seed; }
unsigned int LCG::next(void) {
    seed = (seed * a + c) & 0xffffffff;
    return (seed >> 16) & 0x7fff;
}

在最后两行代码中，我不明白操作符&和>>的用法。如果有人能帮助我，我将不胜感激。

Answer 1

第一个“&”在你的公式中做“mod”，m=2^32。 (大概这是针对 64 位整数架构的，因为它对 32 位整数来说是空操作。)

第二行是整数除以 2^16，然后是 (mod 2^15) -- 在数学上等同于 (seed/65536) % 32768。

采用其他计算方法的原因是这些“按位”运算符的时间效率几乎高于等效的“数学”运算。