| In-place binary counters | |
| Authors: | Amr Elmasry and Jyrki Katajainen |
| Published in: | Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 8087, Springer-Verlag (2013), 349-360 |
| Full text: |  PDF (146 kB) |
| DOI: | 10.1007/978-3-642-40313-2_32 |
| Copyright: | © Springer-Verlag GmbH Berlin Heidelberg |
| 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 2n −1, our counter uses an array of at most n bits plus few words of ⌈lg(1 + n)⌉ 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. |
| Related: |  HTML (Slides) |
| BibLATEX: | @inproceedings{EK2013bC,
author = {Amr Elmasry and Jyrki Katajainen},
title = {In-place binary counters},
booktitle = {Proceedings of the 38th International Symposium on Mathematical
Foundations of Computer Science},
series = {Lecture Notes in Computer Science},
volume = {8087},
publisher = {Springer-Verlag},
year = {2013},
pages = {349--360},
}
|