In-place binary counters

Amr Ahmed Abd Elmoneim Elmasry; Jyrki Katajainen

doi:10.1007/978-3-642-40313-2_32

In-place binary counters

Amr Ahmed Abd Elmoneim Elmasry, Jyrki Katajainen

1 Citationer (Scopus)

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ⁿ - 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.

Originalsprog	Engelsk
Titel	Mathematical Foundations of Computer Science 2013 : 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings
Redaktører	Krishnendu Chatterjee, Jirí Sgall
Antal sider	12
Forlag	Springer
Publikationsdato	2013
Sider	349-360
ISBN (Trykt)	978-3-642-40312-5
ISBN (Elektronisk)	978-3-642-40313-2
DOI	https://doi.org/10.1007/978-3-642-40313-2_32
Status	Udgivet - 2013
Begivenhed	38th International Symposium on Mathematical Foundations of Computer Science 2013 - Klosterneuburg, Østrig Varighed: 26 aug. 2013 → 30 aug. 2013 Konferencens nummer: 38

Konference

Konference	38th International Symposium on Mathematical Foundations of Computer Science 2013
Nummer	38
Land/Område	Østrig
By	Klosterneuburg
Periode	26/08/2013 → 30/08/2013

Navn	Lecture notes in computer science
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-642-40313-2_32

In-place binary countersAccepteret manuskript, 135 KB

Citationsformater

In-place binary counters. / Elmasry, Amr Ahmed Abd Elmoneim; Katajainen, Jyrki.

Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings. red. / Krishnendu Chatterjee; Jirí Sgall. Springer, 2013. s. 349-360 (Lecture notes in computer science).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Elmasry, AAAE & Katajainen, J 2013, In-place binary counters. i K Chatterjee & J Sgall (red), Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings. Springer, Lecture notes in computer science, s. 349-360, 38th International Symposium on Mathematical Foundations of Computer Science 2013, Klosterneuburg, Østrig, 26/08/2013. https://doi.org/10.1007/978-3-642-40313-2_32

@inproceedings{3724c996aa774f49a639d42ba4b28588,

title = "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 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.",

author = "Elmasry, {Amr Ahmed Abd Elmoneim} and Jyrki Katajainen",

year = "2013",

doi = "10.1007/978-3-642-40313-2_32",

language = "English",

isbn = "978-3-642-40312-5",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "349--360",

editor = "Krishnendu Chatterjee and Jir{\'i} Sgall",

booktitle = "Mathematical Foundations of Computer Science 2013",

note = "38th International Symposium on Mathematical Foundations of Computer Science 2013, MFCS 2013 ; Conference date: 26-08-2013 Through 30-08-2013",

}

TY - GEN

T1 - In-place binary counters

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

N1 - Conference code: 38

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-40313-2_32

DO - 10.1007/978-3-642-40313-2_32

M3 - Article in proceedings

SN - 978-3-642-40312-5

T3 - Lecture notes in computer science

SP - 349

EP - 360

BT - Mathematical Foundations of Computer Science 2013

A2 - Chatterjee, Krishnendu

A2 - Sgall, Jirí

PB - Springer

T2 - 38th International Symposium on Mathematical Foundations of Computer Science 2013

Y2 - 26 August 2013 through 30 August 2013

ER -

In-place binary counters

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater