1. Encoding

2. Example code
     Encoding    Decoding  

3. See also

4. References

Encoding

The code of zero is "0"; to code a positive number:

1. Initialize the step count variable C to 1.
2. Write the binary representation of the number without the leading "1" to the beginning of the code.
3. Let M be the number of bits written in step 2.
4. If M is not 0, increment C, repeat from step 2 with M as the new number.
5. Write C "1" bits and a "0" to the beginning of the code.

The code begins:

To decode a Levenstein-coded integer:

1. Count the number of "1" bits until a "0" is encountered.
2. If the count is zero, the value is zero, otherwise
3. Start with a variable N, set it to a value of 1 and repeat count minus 1 times:
4. Read N bits, prepend "1", assign the resulting value to N

The Levenstein code of a positive integer is always one bit longer than the Elias omega code of that integer. However, there is a Levenstein code for zero, whereas Elias omega coding would require the numbers to be shifted so that a zero is represented by the code for one instead.

Example code

Encoding

void levenshteinEncode(char* source, char* dest)

    IntReader intreader(source);    BitWriter bitwriter(dest);    while (intreader.hasLeft())    {        int num = intreader.getInt();        if (num == 0)            bitwriter.outputBit(0);        else        {            int c = 0;            BitStack bits;            do {                int m = 0;                for (int temp = num; temp > 1; temp>>=1)  // calculate floor(log2(num))                    ++m;                for (int i=0; i < m; ++i)                    bits.pushBit((num >> i) & 1);                num = m;                ++c;            } while (num > 0);            for (int i=0; i < c; ++i)                bitwriter.outputBit(1);            bitwriter.outputBit(0);            while (bits.length() > 0)                bitwriter.outputBit(bits.popBit());        }    }

}

Decoding

void levenshteinDecode(char* source, char* dest)

    BitReader bitreader(source);    IntWriter intwriter(dest);    while (bitreader.hasLeft())    {        int n = 0;        while (bitreader.inputBit())     // potentially dangerous with malformed files.            ++n;        int num;        if (n == 0)            num = 0;        else        {            num = 1;            for (int i = 0; i < n-1; ++i)            {                int val = 1;                for (int j = 0; j < num; ++j)                    val = (val << 1) | bitreader.inputBit();                num = val;            }        }        intwriter.putInt(num);           // write out the value    }    bitreader.close();    intwriter.close();

}

See also

• Elias omega coding
• Iterated logarithm

References

• Y-pb-pr
• Y pb pr
• Y'PbPr
• Y/pb/pr
• YPBPR
• YPC
• YPC/PJC
• YPD
• Yp Desert
• YPDN
• YPE
• Ypenburg
• Yperiet
• Y. pestis
• Y.pestis
• Yp-F1
• YP-F1
• YPFB
• YPH
• YP Holdings
• Ypióca
• Ypióca Group
• YPJ
• YPL
• YPM