xor: how come so slow?

[Steve Holden]

Lawrence D'Oliveiro wrote:
> In message <010a9c3f$0$20653$c3e8da3 at news.astraweb.com>, Steven D'Aprano
> wrote:
> 
>> On Sat, 18 Oct 2008 09:16:11 +1300, Lawrence D'Oliveiro wrote:
>>
>>> Data can come in fractional bits. That's how compression works.
>> If you don't believe me, try compressing a single bit and see if you get
>> a "fractional bit".
> 
> If both states of the bit are not equally likely, then you do indeed have a
> fractional bit, since
> 
>     nrbits = (- logbase2(P[bit = 0]) - logbase2(P[bit = 1])) / 2

What's happening here is that the two different meanings of "bit" are
being confused. A bit is both a binary digit and a measure of information.

Obviously you can't create a bit stream with half a bit in it.

In a coding system where all messages of N binary digits are equally
likely then each message contains N bits of information content. This is
the theoretical upper bound on the information content.

In most practical systems, however, the messages have differing
probabilities; then an N-binary-digit message conveys less than N bits
of information, as Lawrence indicated above. Fractional bits are
perfectly valid as a measure of information content.

regards
 Steve
-- 
Steve Holden        +1 571 484 6266   +1 800 494 3119
Holden Web LLC              http://www.holdenweb.com/