I wanted a random number generator for skiplist implementation and got the following logic. Can I get an explanation of how here random numbers are getting generated. I see use of bit wise operator but not able to understand the logic.

```
#include <stdint.h>
#include <iostream>
using namespace std;
typedef unsigned int uint32_t;
typedef unsigned long long uint64_t;
class Random {
private:
uint32_t seed_;
public:
explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) {
// Avoid bad seeds.
if (seed_ == 0 || seed_ == 2147483647L) {
seed_ = 1;
}
}
uint32_t Next() {
static const uint32_t M = 2147483647L; // 2^31-1
static const uint64_t A = 16807; // bits 14, 8, 7, 5, 2, 1, 0
uint64_t product = seed_ * A;
seed_ = static_cast<uint32_t>((product >> 31) + (product & M));
if (seed_ > M) {
seed_ -= M;
}
return seed_;
}
};
int main()
{
Random rnd_(0xdeadbeef);
int i = 10;
while(i)
{
cout << rnd_.Next() << "\n";
i--;
}
return 0;
}
```

asked on Stack Overflow Apr 30, 2018 by Aman

**tl;dr**

It takes a long number (which is up to 64 bits (the binary equivalent of decimal place)), splits in two 32 bit long numbers, and adds the first half to the second. The decimal equivalent would be if the starting number would be 12345 and we want to split it by 4^{th} decimal space, we'd split the number into 1 and 2345, and add the two, producing 2346.

The only bit-work seems to be here:

```
seed_ = static_cast<uint32_t>((product >> 31) + (product & M));
```

What that does is right-shift (divide be 2^{31}) product and add the first byte of M.

So if seed was 1957983907, then product is (16807 * 1957983907 = 32907835524949), which is 111011110110111110011110110001100011101010101 (which is a 64bit number, which can be broken up into two (32bit long) parts

```
00000000000000000001110111101101
11110011110110001100011101010101
```

), left shift it 31 would give you 11101111011011 (the "top" two bytes of the above number.)

Then, you do (product & M), which given the following (product on the top, M on the bottom):

```
00000000000000000001110111101101 11110011110110001100011101010101
00000000000000000000000000000000 11111111111111111111111111111111
```

it goes through both numbers, bit by bit, doing an `add`

on each, which gets the second half of M (11110011110110001100011101010101), which is equal to 4091070293.

Then it adds the two, making sure it fits into a 32bit long number, wrapping it if it doesn't.

User contributions licensed under CC BY-SA 3.0