tegers never generates negative values. The successive xor values are
7,2,29,11,5,249,0,7,4.A benefit of the xor operation is that it is symmetric: x xor y is y xor x. This means that inverting the order of the original list, we would simply invert the order of the list of differences. Obviously, computing the xor is quite fast.
Once we have the list of differences as non-negative numbers, we can then try to store them by using as few bits as possible. Unfortunately, in our case, we could to the conclusion that we need 8 bits to store the differences. We remarked however that for all but one value, 3 bits per difference would suffice.
So a sensible solution is to code the first 3 bits of each differences:
001, 010, 101, 101, 101, 111, 000, 111, 100. And then we add a pointer to the second last difference to indicate that we are missing 5 bits (11111). The cost of coding this exception is about 13 bits. So the total storage cost would be (8+3+9*3+13=51). In this case, frame-of-reference is preferable to delta coding, but both are preferable to the original 8-bit coding which used 80 bits.
There are many possible variations. For example, you can also use exception technique with the frame-of-reference approach when almost all values fit in a range of values, except for a few.
Further reading: the document SZIP Compression in HDF Products and the corresponding CCSDS 120.0-G-2 data compression standard describe the application of delta coding for scientific data. Michael Dipperstein’s page provides a nice overview of generic compression techniques. The specific exception technique I described is from the NewPFD scheme first described in:
H. Yan, S. Ding, T. Suel, Inverted index compression and query processing with optimized document ordering, in: WWW ’09, 2009.
See also my blog post How fast is bit packing?