Aarhus University Seal

Integer Representations towards Efficient Counting in the Bit Probe Model

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review


  • J99

    367 KB, PDF document


  • Gerth Stølting Brodal
  • Mark Greve
  • ,
  • Vineet Pandey, Computer Science & Information Systems, BITS Pilani, India
  • Srinivasa Rao Satti
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(logn ) 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
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)206-217
Number of pages12
Publication statusPublished - 2011
Event8th Annual Conference on Theory and Applications of Models of Computation. TAMC 2011 - Tokyo, Japan
Duration: 23 May 201125 May 2011


Conference8th Annual Conference on Theory and Applications of Models of Computation. TAMC 2011

Bibliographical note

Title of the vol.: Theory and Applications of Models of Computation. Proceedings / Mitsunori Ogihara and Jun Tarui (eds.)
ISBN: 978-3-642-20876-8

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 41505401