Fast sparse list walker

A computer readable medium for identifying active bits in a vector, the computer readable medium comprising instructions for:

• receiving a pointer associated with a vector of bits, wherein the pointer is associated with a current bit within the vector of bits;
• grouping the vector of bits into groups of a mathematical power of two, which is any non-negative integer powers of two;
• determining one or more current groups which are the groups of the mathematical power of two comprising the current bit;
• analyzing, in response to receiving the pointer, the one or more current groups of the power of two;
• identifying, in response to the analyzing, a largest group of the power of two in the one or more current groups comprising all empty bits;
• and
• setting the pointer to point to a bit following a last bit in the identified largest group of the power of two comprising all empty bits.

An information processing system for identifying active bits in a vector, the information processing system comprising:

• a memory;
• a processor communicatively coupled to the memory;
• and
• a circuit communicatively coupled to the memory and the processor, wherein the circuit is adapted to:
• receive a pointer associated with a vector of bits, wherein the pointer is associated with a current bit within the vector of bits;
• group the vector of bits into groups of a mathematical power of two, which is any non-negative integer powers of two;
• determine one or more current groups which are the groups of the mathematical power of two comprising the current bit;
• analyze, in response to receiving the pointer, the one or more current groups of the power of two;
• identify, in response to the analyzing, a largest group of the power of two in the one or more current groups comprising all empty bits;
• and
• setting the pointer to point to a bit following a last bit in the identified largest group of the power of two comprising all empty bits.