θ(n)bitinspectionschangesworstcase.ppt

Integer Representations and Counting in the Bit Probe Model
M. Zaiur Rahman and J. Ian Munro
Cheriton School puter Science
University of Waterloo
Waterloo On
Canada
Integer Representations
Standard: n bits representing {0..2n}
# bits … optimal
Increment:
Θ(n) bit inspections/changes worst case
O(1) amortized, but not if we include decrement
Redundant Binary Numbers
Use “digits” 0,1,2 but representation is in binary, 2 is a delayed carry
. 01220 = 10100
Space 2n bits (or reduce to about (lg 3) n)
Increment O(1), as we de-amortize the scan to release the rightmost carry
Decrement is tricky, easiest to use digit “-1”
Note the extra lg n bits for the scan pointer
Gray Codes .. Due to Gray ..of course
Binary Reflected Gray Code (BRGC)
Of dimension n (. n bits, numbers [0..2n]
A sequence of 2n strings each of length n
G(n) = (n-1), (n-1)R
(reversal is on the sequence order, not the individual codes)
Increment on a Gray Code
Even parity: flip rightmost 1 bit
Increment on a Gray Code
Even parity: flip rightmost bit
00110000 → 00110001
Increment on a Gray Code
Even parity: flip rightmost bit
00110000 → 00110001
Odd parity: flip the bit to left of rightmost 1
01110000 → 01010000
Increment on a Gray Code
Even parity: flip rightmost bit
00110000 → 00110001
Odd parity: flip the bit to left of rightmost 1
01110000 → 01010000
Costs:1 bit changed, n inspections (worst case)
Or: add parity bit, O(1) amortized insert, 2 bits changed
Integrate parity bit with code (no extra bit [Lucal])
Our First Result: Lower Bound
Theorem: Any representation of [0..2n] using exactly n bits requires Ω(√n) bit inspections in the worst case.
Proof: Model, apply Sunflower Lemma and manipulate
Sunflower Lemma [Ёrdos & Rado]
Sunflower with p petals
Sets S1, …, Sp so SiSj is same for all i,j
Lemma: S1, …, Sp is a system of sets each of size at most q. If m>(p-1)q+1q!, then it contains a subcollection with p petals
Use the lemma with m as small as possible