Generating random boolean values is a common challenge in programming tasks, especially when randomness is required for gaming or testing data.

With that said, let’s explore some methods to generate boolean values as quickly as possible.

## Random Generators

In our **previous discussion on the **`Random`

** class in C#**, covered in the article titled “Random Class in C#“, we explored some different random generators available in .NET. We identified two main types: **the pseudo-random generator class, **`Random`

**, and the cryptographically secure generator class, RandomNumberGenerator.**

For most everyday programming tasks, we rely on the `Random`

class. However, when dealing with security or cryptographic requirements, using the appropriate random generator, usually `RandomNumberGenerator`

, is crucial. We have explored the `RandomNumberGenerator`

in greater detail in our Create Cryptographic Numbers With RandomNumberGenerator article.

While cryptographically secure randomness might not be necessary in every scenario, it’s advisable to prioritize security whenever possible. **However, it’s worth noting that **`RandomNumberGenerator`

** tends to be significantly slower than the **`Random`

** generator.**

### Random Classes for Our Testing Purposes

In .NET, random generators **don’t offer a specific method for generating random boolean values**. However, they do provide a general-purpose method for generating an array of various values, including booleans.

We’ll demonstrate creating `bool`

values from `int`

, `long`

, `double`

, `byte`

, and `boolean array`

. Let’s define the `IRandomGenerator`

interface before proceeding:

public interface IRandomGenerator { int NextInteger(int fromInclusive, int toExclusive); long NextLong(long fromInclusive, long toExclusive); double NextDouble(); void GetItems<T>(ReadOnlySpan<T> choices, Span<T> destination); }

**This interface will encompass all the methods required for various algorithms to generate random boolean values.**

Next, we need to create a concrete implementation of this interface. We do that using the RandomNumberGenerator and Random classes, and the implementation can be found by clicking on both links.

The results are clear and unmistakable:

| Method | NumberOfIntegers | Mean | |---------------------------- |----------------- |--------------:| | SystemRandomGenerator | 1000 | 2.017 us | | CryptographyRandomGenerator | 1000 | 46.283 us | | SystemRandomGenerator | 1000000 | 1,957.859 us | | CryptographyRandomGenerator | 1000000 | 45,801.955 us |

`RandomNumberGenerator`

proves to be **more than 20 times slower **in heavy usage scenarios. Therefore, if cryptographic precision isn’t necessary for our task, it’s unsuitable for our purposes.

## Generating Random Booleans

By measuring the speed of .NET built-in random generators, we’ve determined that the `Random`

class offers the best performance in terms of speed.

Implementing the same interface is advantageous for consistency and ease of comparison. **Different classes will implement different algorithms, but they will implement the same interface:**

internal interface IBooleanGenerator { bool NextBool(); }

### Generating a Random Boolean Using Integers

The concept is straightforward. We’ll generate an `int`

, **either 0 or 1, and if it’s 0, we’ll return true; otherwise, we’ll return false:**

public class NextIntegerGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator { public bool NextBool() => randomGenerator.NextInteger(0, 2) == 0; }

This implementation of the `IBooleanGenerator`

interface takes one of the random generators we discussed earlier as a parameter.

The `NextBool()`

method calls the underlying generator to produce an `int`

, either `0`

or `1`

, and from that, it constructs the `bool`

value.

### Generating a Random Boolean Using Doubles

We can apply a similar concept to floating-point numbers. The original generator always produces numbers between 0.0 and 1.0. **Therefore, we can return true if the generated number is greater than 0.5:**

public class NextDoubleGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator { public bool NextBool() => randomGenerator.NextDouble() > 0.5; }

We are again implementing the `IBooleanGenerator`

interface which accepts a random generator that implements the `IRandomGenerator`

interface.

In this case, only the `SystemRandomGenerator`

is suitable, as the `CryptographyRandomGenerator`

does not implement the `NextDouble()`

method.

### Generating a Random Boolean Using GetItems

Our next method in the toolbox is the `GetItems()`

method, **capable of generating an array of various types of elements**. Since it’s a generic method, it can also generate `bool`

values:

public class GetItemsGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator { public bool NextBool() { Span<bool> destination = stackalloc bool[1]; randomGenerator.GetItems([false, true], destination); return destination[0]; } }

The structure of the `GetItemsGenerator`

class mirrors that of the previous `NextDoubleGenerator`

and `NextIntegerGenerator`

. However, this time, we utilize the `GetItems()`

method.

The `GetItems()`

**accepts a **`ReadOnlySpan`

** of possible values and then** **fills a Span with randomly selected items from it**

**.**

To generate `bool`

values, we provide an array **containing all possible boolean values [ true, false]**, along with a destination

`Span`

with length 1. We use a `stackalloc`

array to minimize memory allocations. ### Base Benchmarking Methods

We will use the `Random`

generator because it is faster than the `RandomNumberGenerator`

generator. Also, we have prepared two helper methods for the benchmark, which you can find inside the BenchmarkBase.

The `BenchmarkBase`

class will serve as the foundation for all our benchmarking activities.

We’ve implemented several algorithms and set up the foundational benchmarking methods. **Now, it’s time to measure our initial results. **We’ll test the creation of one thousand and one million random booleans using the `SystemRandomGenerator`

and various algorithms:

| Method | NumberOfBooleans | Mean | Allocated | |--------------------- |----------------- |--------------:|----------:| | NextIntegerGenerator | 1000 | 6.387 us | 24 B | | NextDoubleGenerator | 1000 | 7.847 us | 24 B | | GetItemsGenerator | 1000 | 15.948 us | 24 B | | NextIntegerGenerator | 1000000 | 6,247.900 us | 72 B | | NextDoubleGenerator | 1000000 | 7,839.197 us | 120 B | | GetItemsGenerator | 1000000 | 15,467.424 us | 36 B |

The results of the `NextIntegerGenerator`

and `NextDoubleGenerator`

are pretty similar, but the performance of the `GetItemsGenerator`

is notably worse.

This outcome is expected, considering that the `GetItemsGenerator`

populates one million arrays with one boolean to create one million booleans, whereas the other generators accomplish this more directly.

Let’s investigate if using the `GetItems()`

method for generating larger arrays at once makes any difference in performance.

### GetItems() Method Can Already Generate an Array of Booleans

Let’s be fair in evaluating the performance of the `GetItems()`

method by measuring how this benchmark compares with the others.

Instead of generating one million arrays with one boolean each, we’ll generate a single array with one million booleans. **This approach will provide a more accurate representation of the GetItems() method’s performance. **This time,

**we’ll need to store all the results since the GetItems() method returns the entire array**, and the other methods must do the same.

Let’s compare the performance of this new method with the rest of them:

| Method | NumberOfBooleans | Mean | Allocated | |------------------------ |----------------- |----------------:|----------:| | GetItemsDirectGenerator | 1000 | 171.8 ns | 96 B | | NextIntegerGenerator | 1000 | 2,025.5 ns | 24 B | | NextDoubleGenerator | 1000 | 2,351.9 ns | 24 B | | GetItemsGenerator | 1000 | 10,895.0 ns | 24 B | | GetItemsDirectGenerator | 1000000 | 88,762.3 ns | 97 B | | NextIntegerGenerator | 1000000 | 1,980,366.4 ns | 26 B | | NextDoubleGenerator | 1000000 | 2,365,063.9 ns | 26 B | | GetItemsGenerator | 1000000 | 10,470,485.6 ns | 120 B |

This time, the direct call to the `GetItems()`

method **yields results similar to the NextIntegerGenerator.**

However, it’s crucial to note that a direct call to `GetItems()`

**doesn’t respect our IBooleanGenerator interface**. Our objective isn’t to generate an array of booleans at once but rather

**to have a method that can quickly generate a single boolean when needed.**

### GetItems() Method With Buffer

If we want to use this generator, we can significantly enhance its speed using the internal buffer. To make it respect our `IBooleanGenerator`

interface, we can internally** have a small buffer of booleans and replace it whenever we run out of new booleans**:

public class GetItemsWithBufferGenerator(IRandomGenerator randomGenerator, int bufferLength) : IBooleanGenerator { private static readonly bool[] _allPossibilities = [false, true]; private readonly bool[] _buffer = new bool[bufferLength]; private int _currentBufferIndex = bufferLength; public bool NextBool() { if (_currentBufferIndex >= _buffer.Length) { randomGenerator.GetItems<bool>(_allPossibilities, _buffer); _currentBufferIndex = 0; } return _buffer[_currentBufferIndex++]; } }

**With that enhancement and the buffer of 128 elements, the code is still not as fast as a simple NextIntegerGenerator():**

| Method | NumberOfBooleans | Mean | Allocated | |---------------------------- |----------------- |-------------:|----------:| | NextIntegerGenerator | 1000 | 6.416 us | 24 B | | GetItemsWithBufferGenerator | 1000 | 8.895 us | 192 B | | NextIntegerGenerator | 1000000 | 6,324.178 us | 72 B | | GetItemsWithBufferGenerator | 1000000 | 8,450.456 us | 288 B |

**However, we can explore an alternative approach.** We’ve observed that generating a single `int`

, `byte`

, `double`

, or any other type is the primary bottleneck in our algorithms.

## Generate a Random Bool Using a Single Bit

Currently, our fastest method involves translating the `int`

result into a `bool`

. However, we’re generating an integer on each iteration. **But an int can have 4,294,967,296 different values**! And we translate this into two values (

`true`

/`false`

). This appears to be a significant waste of resources.Since `int`

in .NET is four bytes long, equivalent to 32 bits, and **each bit can represent either zero or one** (`true`

or `false`

), we can leverage this. We can direct the underlying random generator to **produce an integer within the range from int.MinValue to int.MaxValue and then extract 32 random booleans from it.**

Let’s test if this approach yields better performance:

public class NextIntegerBitsGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator { private const int BitsInByte = 8; private const int MaxBitIndex = sizeof(int) * BitsInByte; private int _randomInteger; private int _currentBufferIndex = MaxBitIndex; public bool NextBool() { if (_currentBufferIndex >= MaxBitIndex) { _randomInteger = randomGenerator.NextInteger(int.MinValue, int.MaxValue); _currentBufferIndex = 0; } return (_randomInteger & (1 << _currentBufferIndex++)) != 0; } }

We begin by determining the number of bits in a `byte`

(`BitsInByte`

) and the total number of bits in a single `int`

(`MaxBitIndex`

).

Next, we maintain two variables: `_randomInteger`

to store the current random integer and `_currentBufferIndex`

to track the current index we’re on while traversing the integer bits.

In the algorithm itself, we check the bit at the current index and **return true if it’s set or false if it’s not set**. If we exhaust all the bits in the

`int`

, we generate a new random `int`

and reset the index to zero.Now, the moment of truth: is this algorithm faster than the current fastest one? Let’s benchmark them:

| Method | NumberOfBooleans | Mean | Allocated | |------------------------- |----------------- |-------------:|----------:| | NextIntegerBitsGenerator | 1000 | 4.219 us | 32 B | | NextIntegerGenerator | 1000 | 6.428 us | 24 B | | NextIntegerBitsGenerator | 1000000 | 4,303.753 us | 35 B | | NextIntegerGenerator | 1000000 | 6,223.402 us | 72 B |

The results are clear: **we have a new winner, NextIntegerBitsGenerator().**

### Bits Representation, Little Endian vs. Big Endian.

We might question whether this algorithm is correct when considering how `int`

values are represented in computer memory. **We know that there are two distinct representations of bytes in multibyte types in computers**: `Little Endian`

and `Big Endian`

systems, each having a different approach to int representation. However, this is precisely why we want all possible negative and positive integers.

As all negative and positive integers together encompass any combination of bits across these bytes, we’re indifferent to which number these bits represent. **We understand that all possible numbers will generate all possible combinations of bits.**

To make this statement more straightforward, consider this: **we don’t care if the combination of bits ‘0011’ represents the number 12 or 3.**

However, it’s worth noting a **slight inconsistency**: the number `int.MaxValue`

can never be generated; thus, this particular combination of bits will never occur. **But remember, this is only one combination out of 4,294,967,296 possible combinations.**

### Generate a Random Boolean Using an Array of Bytes Instead of an Integer

As before, when we talked about `GetItems()`

method, we can again find another method that we can use instead of `NextInteger()`

and that is `NextBytes()`

method. Similar to `GetItems()`

, the method `NextBytes()`

also returns an array of bytes, and we can then check the bits of each generated byte.

But again, measuring this approach shows that it is not faster than `NextIntegerBitsGenerator()`

.

### From Integer to Long

Using the bits of an `int`

is currently the fastest option. But we can use the long type as well to generate random bool values:

public class NextLongBitsGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator { private const int BitsInByte = 8; private const int MaxBitIndex = sizeof(long) * BitsInByte; private long _randomLong; private int _currentBufferIndex = MaxBitIndex; public bool NextBool() { if (_currentBufferIndex >= MaxBitIndex) { _randomLong = randomGenerator.NextLong(long.MinValue, long.MaxValue); _currentBufferIndex = 0; } return (_randomLong & (1L << _currentBufferIndex++)) != 0; } }

**There is a very important detail here.** When shifting bits, we have to use type `long`

, and that is why there is a constant `1L`

and not just `1`

. Without this, if we use `1`

we would shift an `int`

instead of `long`

, and the **results would be wrong!**

So, let’s check the result:

| Method | NumberOfBooleans | Mean | Ratio | Allocated | |------------------------- |----------------- |-------------:|------:|----------:| | NextLongBitsGenerator | 1000 | 4.064 us | 0.97 | 40 B | | NextIntegerBitsGenerator | 1000 | 4.199 us | 1.00 | 32 B | | | | | | | | NextLongBitsGenerator | 1000000 | 4,067.125 us | 0.99 | 43 B | | NextIntegerBitsGenerator | 1000000 | 4,101.540 us | 1.00 | 80 B |

If we are creating a lot of tests, sometimes one is faster, and sometimes the other is faster. These are pretty close.

## Fairness of our Random Boolean Algorithms

Now that we have found the winner, it is also time to check **if our algorithms are fair** (producing consistently fair results).

Randomness is very tricky, and despite that it is unlikely, there is a possibility that if we throw a die ten times, we will get six at each throw. Even though this is theoretically possible, we would probably conclude that the die is unfair.

So, when generating ten million boolean values, we expect to generate around five million `true`

values and five million `false`

values. But why don’t we check:

Generator: true / False | From the middle GetItemsGenerator: 4998654 / 5001346 | 0,0002692 NextDoubleGenerator: 5000626 / 4999374 | 0,0001252 NextIntegerGenerator: 4999618 / 5000382 | 0,0000764 NextIntegerBitsGenerator: 4996202 / 5003798 | 0,0007596 NextLongBitsGenerator: 5000193 / 4999807 | 0,0000386

By running this test many times, we see that all of our generators are fair and produce almost the same amount of random boolean values.

## Conclusion

In this article, we’ve explored various algorithms for generating booleans. For a significant period, the most straightforward algorithm, which involves selecting integer numbers 0 as true and 1 as false, was the fastest option.

However, we’ve also discovered faster algorithms that leverage single bits for generating random boolean values, offering increased efficiency.

It’s safe to say that we can always rely on the simplest possible algorithm. However, if we desire or require a bit more speed, we can opt for manipulating bits and utilize the NextIntegerBitsGenerator or NextLongBitsGenerator algorithm.