Integer representations towards efficient counting in the bit probe model

We consider the problem of representing integers in close to optimal number of bits to support increment and decrement 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. We propose representations, called counters, with different trade-offs between the space used and the number of bits probed. A counter is space-optimal   if it represents any integer in the range [0,…,2n−1][0,…,2n−1] using exactly n bits. We provide a space-optimal counter   which supports increment and decrement operations by reading at most n−1n−1 bits and writing at most 3 bits in the worst-case. This is the first space-optimal representation which supports these operations by always reading strictly less than n bits. For redundant counters   where we only need to represent integers in the range [0,…,L−1][0,…,L−1] for some integer L<2nL<2n using n bits, we define the space-efficiency   of the counter as the ratio L/2nL/2n. We provide representations that achieve different trade-offs between the read/write-complexity and the efficiency.We also examine the problem of representing integers to support addition and subtraction operations. We propose a representation of integers using n   bits and with space efficiency at least 1/n1/n, which supports addition and subtraction operations, improving the efficiency of an earlier representation by Munro and Rahman [11]. We also show various trade-offs between the operation times and the space complexity.