# Integer Representations towards Efficient Counting in the Bit Probe Model

In * Proc. 8th Annual Conference on Theory and Applications of Models of Computation*, volume 6648 of * Lecture Notes in Computer Science*, pages 206-217. Springer Verlag, Berlin, 2011.

## Abstract

We consider the problem of representing numbers in
close to optimal space and supporting increment, decrement, addition
and subtraction operations efficiently. We study the problem in the
bit probe model and analyse the number of bits read and written to
perform the operations, both in the worst-case and in the
average-case. A counter is * space-optimal* if it represents any
number in the range [0,...,2^{n}-1] using exactly *n* bits. We
provide a * space-optimal counter* which supports increment and
decrement operations by reading at most *n*-1 bits and writing at most
3 bits in the worst-case. To the best of our knowledge, this is the
first such representation which supports these operations by always
reading strictly less than *n* bits. For * redundant counters*
where we only need to represent numbers in the range [0,...,*L*] for
some integer *L* < 2^{n}-1 using *n* bits, we define the efficiency of
the counter as the ratio between *L*+1 and 2^{n}. We present various
representations that achieve different trade-offs between the read and
write complexities and the efficiency. We also give another
representation of integers that uses *n* + *O*(log *n* ) bits to
represent integers in the range [0,...,2^{n}-1] that supports
efficient addition and subtraction operations, improving the space
complexity of an earlier representation by Munro and Rahman
[Algorithmica, 2010].

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 2011. All rights reserved.

**Online version**

tamc11.pdf (367 Kb)

**DOI**

10.1007/978-3-642-20877-5_22

**Links**

**BIBT**_{E}X entry

@incollection{tamc11,
author = "Gerth St{\o}lting Brodal and Mark Greve and Vineet Pandey and S. Srinivasa Rao",
booktitle = "Proc. 8th Annual Conference on Theory and Applications of Models of Computation",
doi = "10.1007/978-3-642-20877-5_22",
isbn = "978-3-642-20876-8",
pages = "206-217",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Integer Representations towards Efficient Counting in the Bit Probe Model",
volume = "6648",
year = "2011"
}