Using binary strings on storing ordered items in database

Question

In this post, @boisvert mentioned that if using string as the order field's value, it is best shown for a binary string, and then gave an algorithm to calculate the average of two binary strings as follows:

Avalue = 1+0*(1/2)+1*(1/4)+1*(1/8)
Bvalue = 1+1*(1/2)+0*(1/4)+0*(1/8)
average, new value = 1+0*(1/2)+1*(1/4)+1*(1/8)+1*(1/16) new string = "10111"

content     order
-------------------- 
   A         '1011' 
   new!      '10111' 
   B         '1100' 
   C         '1101'

I couldn't understand these very well, what's the value of the first item putting into the DB and the items inserting before/after it? How to calculate the average between '1011' and the new value '10111', or between '111' and '1000'?

Any help is much appreciated.

Answer 1

The binary strings are fractions, not integers; the decimal point is always at the beginning (or after the first digit, in @boisvert's answer; it doesn't make any difference as long as the position of the decimal point is fixed. Of course, it's actually a binary point since these are binary numbers.)

To find the average:

1. If the strings differ in length, put enough 0s at the end of the shorter string so that it is the same length as the longer string.
2. Add the two strings together, using binary addition, always putting the last carry at the beginning, even if it is ´0'. [See algorithm below].
3. Remove any 0s at the end.

Example 1: 1011 and 10111

1. Extend the first string with a 0: 10110 and 10111

2. Find the sum:

       A:  10110
       B:  10111
   Carry: 101100
     Sum: 101101
   

3. No trailing zeros, so the result is 101101

Example 2: 111 and 1000

1. 1110    1000
2. 10110
3. 1011

Starting off and insertion at the end:

The first item put into the database has the label 1. If at any point you need to add an item at the very beginning, use the first label with a 0 before it. Similarly, if you need to add an item at the end, use the first label with a 1 before it.

Binary addition:

Since the strings are the same length, this is easy; set Carry to 0, and scan both strings from back to front. (The output is also produced back-to-front.)

At each position: * If the sum of Carry and the two digits is 1 or 3, output a 1, otherwise output a 0. * If the sum of Carry and the two digits is 2 or 3, set Carry to 1, otherwise set it to 0.

When you've finished all the digits, output the value of Carry.

Practical implementation:

In practice, you wouldn't use binary strings; you'd use some fairly large base, the only requirement being that it is even. But the algorithms are the same. When constructing the representation of your numbers, you need to assign digits to characters in alphabetical order, so that the resulting strings can be sorted alphabetically without converting them to numbers; the database doesn't know how to convert to numbers, but it knows how to sort strings alphabetically.