In-Place Binary Counters

Abstract We introduce a binary counter that supports increments and decrements in O (1) worst-case time per operation. (We assume that arithmetic operations on an index variable that is stored in one computer word can be performed in O (1) time each.) To represent any integer in the range from 0 to 2 n − 1, our counter uses an array of at most n bits plus few words of \(\lceil \lg (1 + n) \rceil\) bits each. Extended-regular and strictly-regular counters are known to also support increments and decrements in O (1) worst-case time per operation, but the implementation of these counters would require O ( n ) words of extra space, whereas our counter only needs O (1) words of extra space. Compared to other space-efficient counters, which rely on Gray codes, our counter utilizes codes with binary weights allowing for its usage in the construction of efficient data structures.

Authors

• Amr Elmasry
• Jyrki Katajainen

Keywords

No keywords are indexed for this paper.