protected static class PSIntMap.BitmapNode<E> extends PSIntMap.Node<E>
While storage index computation seems complicated and expensive, there are efficient algorithms to count leading/trailing bits by means of binary operations and minimal branching, which is suitable for JIT compilation (see http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup)key = 289 = 0b01001.00001, shift = 5, assuming node already contains key 97 = 0b00011.00001 => idx = (key >>> shift) & 0x1f = 0b01001 = 9 bitmap = 1000001000 : bit 9 from key 289 (0b01001.), bit 3 from key 97 (0b00011.) node element index for key 289 (level index 9) = 1 (one set bit to the right of bit 9)
If the bit count of a BitmapNode is 2 and an element is removed, this gets demoted into q OneNode. If the bit count of a BitmapNode is 31 and an element is added, this gets promoted into a FullNode