Select one number at a time between 1 & 10 billion in random order

Problem

I have a need to pick one unique random number at a time between 0 and 10,000,000,000 and do it till all numbers are selected. Essentially the behavior I need is a pre-built stack/queue with 10 billion numbers in random order, with no ability to push new items into it.

Not so good ways to solve:

There's no shortage of inefficient ways in my brain. Such as,

• persist generated numbers and check newly generated random number is already used, at some point this gets us into indefinite wait before a usable number is produced.
• Persist all possible numbers in a table and pop a random row and maintain new row count for next pick etc. Not sure if this is good or bad.

Questions:

1. Are there other deterministic ways besides storing all possible combinations and using random?

   • Like maintaining windows of available numbers and randomly select a window first and randomly select a number within that window etc. eg: like this

2. If not, what is the best type to store numbers in reasonably small amount of space?

   • 50+% of numbers wont fit in a 32 bit (int), 64 bit (long) is waste. Cos largest number fits in 34 bits, wasting 30 bits per number (>37GB total).

If this problem hasn't been solved already.

3. What is a good data structure for storing & picking a random spot and quickly adjust the structure for next pick to be fast?