Is the value of RAND_MAX always (2^n)-1?

• I don't know any implementation for which RAND_MAX is not one less than a power of two, but that isn't mandated by the standard;

• ((RAND_MAX | (RAND_MAX >> 1)) == RAND_MAX) is indeed a way to test if RAND_MAX is one less than a power of two.

• I'm using

  int alea(int n){ 
    assert (0 < n && n <= RAND_MAX); 
    int partSize = 
      n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); 
    int maxUsefull = partSize * n + (partSize-1); 
    int draw; 
    do { 
      draw = rand(); 
    } while (draw > maxUsefull); 
    return draw/partSize; 
  }
  

to make as evenly distributed as possible random numbers from rand().

I don't know what the guarantees on RAND_MAX are, but you'd better avoid it if possible because of the number of broken implementations around and because it starts cycling quite quickly in today's applications. Getting a uniform distribution is described here.

I recommend Boost.Random instead. The Mersenne twister generator represents a good tradeoff between speed, memory use and quality.

For implementations of rand which use a (variant of a) Linear Congruential Generator (most of them), then RAND_MAX will be a prime number, not necessarily of the form 2ⁿ - 1 (a "Mersenne prime").

Also, 2³¹-1 is a prime number, but if n is not prime, 2ⁿ - 1 is not prime.

(Indeed, if n = ab, then 2ⁿ - 1 = (2^a - 1)(1 + 2^b + 2^2b + ...) )

Around 2⁶⁴, the only Mersenne prime is 2⁶¹ - 1.

And you should really avoid linear congruential generators if you have any half serious requirement about random number generation. Actually, I'd say that except for a tetris game, you should avoid rand() from the C library.