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?


2 Answers 2


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, 2011 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, 2011 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, 2011 at 6:30

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

>>> bin(1234567)

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

>>> n=4
>>> 0b000111

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

>>> 1234567 & 0b111111

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
>>> bin(63)

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

>>> 1234567 % (4<<n)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.