In unsigned binary arithmetic the formula “n|(n−1)” for the last number in the range indicates that 0 denotes the entire range of integers. It is good to be able to represent this maximal range but that range is already represented by the integer with only the high bit on and it would be good to represent the empty range. 0 seems to be an ugly special case but here is an adequate resolution I think. We define the task as representation of particular ranges of k bit numbers, from 0 thru 2^k−1. We evaluate n&(n−1) and n|(n−1) above as k+1 signed binary 2’s complement numbers whereby 0 represents the range [0, −1] which is indeed empty. k is likely to be somewhat less than 64 in any case. This is efficient but tricky.

This scheme allocates ranges of integers. Here we pursue the uses of the abstract version of the idea. In particular these integers may be used as virtual or real addresses. The cost of fragmentation may be greatly lessened with virtual address since it is presumably unnecessary to allocate real RAM or disk until when and if the object grows.

A general problem is growing blocks. When the resident of a block must grow beyond its current power of 2 then it is generally necessary to move the object. (Alternatively a tentative reservation for the next block may be made but we don’t explore that here.) Whether objects need to grow is highly algorithm dependent and even application dependent. Just now I can’t think of anything that ‘needs to grow’ except arrays. Arrays are good when it is natural to identify an element with an integer index from a compact set of integers. Arrays are also good for locality of reference such as hardware exploits in turning an array into a stream or vice-versa. An array in virtual memory that is mapped to discontiguous pages is nearly as good.

This is almost the same trick in another context.