# Clarification of pseudo random number generator

I am asked to create a pseudo-random number generator using the following algorithm:

The generator will generate every integer from `1` to `N-1` exactly once

The algorithm for `N=2^n`

• Initialize an integer `R` to be equal to `1` every time the tabling routine is called and then on each successive call for a random number:
• set `R=R*5`
• mask out all but the low-order `n+2` bits of the product and place the result in R
• set `p=R/4`

What does the algorithm mean when it says mask out all but the low order `n+2` bits of the product?

## migrated from stackoverflow.comJul 7 '11 at 18:01

This question came from our site for professional and enthusiast programmers.

for n = 1 you would mask the 3 least bits

assuming big endian you'd have this bit layout

``````128 64  32  16  8   4   2   1
X   X   X   X   X   O   O   O
``````

O's would be the bits you wanted to keep and you'd use the bitwise and operator with the value 7 since you need the 4, 2, and 1 bits high in order to mask (bitwise AND) them. `myProduct &= 0x07; // force all bits except the 3 least to be 0`

• But R is an integer no? what are the bits of an integer – Ellipsis... Jul 6 '11 at 5:16
• All data types are represented by a certain numbe of bytes wether it's an integer or a float or class. If a bit is 1 then it gets the value I set above it. So when you have the value 3 in an int you can think of the bits being `00000011` since you need the 2 and the 1 to make 3. This site goes into more detail: helpwithpcs.com/courses/binary-numbers.htm – JohnKlehm Jul 6 '11 at 6:16
• Essentially the "mask out" step translates to `R &= Math.pow(2, n + 2);` This code isn't quite right so don't just turn this in for your homework. I'm hoping by the time you figure out what is missing you'll not have needed my hint anyway :) – JohnKlehm Jul 6 '11 at 6:30

Here is a worked example, using the Python interpreter to help with the binary conversion

``````>>> bin(1234567)
'0b100101101011010000111'
``````

suppose n=4, then I need to mask all but the last 6 bits. Which should give

``````>>> n=4
>>> 0b000111
7
``````

wikipedia's binary page has some information about bitwise operations. Here we are interested in the AND operation

``````>>> 1234567 & 0b111111
7
``````

One way to arrive at this mask is to compute the number one larger (since it is a power of 2) and subtract one from it

``````>>> (1<<n+2)-1
63
>>> bin(63)
'0b111111'
``````

`(1<<n+2)-1` can be simplified to `(4<<n)-1`, but in this instance there is another way

``````>>> 1234567 % (4<<n)
7
``````

I have replaced the bitwise AND(`&`) with modulus(`%`) which has the same effect of masking the lowest n+2 bits

modulus is slightly more work for the CPU than bitwise operations, so if best performance is essential you should use the bitwise method