Path: utzoo!utgpu!watmath!clyde!att!pacbell!ames!mailrus!purdue!i.cc.purdue.edu!k.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: comp.arch
Subject: Re: Leading zero and pop count
Summary: A bit stream need not even be aligned on byte boundaries
Message-ID: <1021@l.cc.purdue.edu>
Date: 20 Nov 88 10:47:56 GMT
References: <10882@hall.cray.com> <3300039@m.cs.uiuc.edu>
Organization: Purdue University Statistics Department
Lines: 34

In article <3300039@m.cs.uiuc.edu>, wsmith@m.cs.uiuc.edu writes:
> 
> >One thing that is difficult to do in software (counter examples are welcomed
> >please!) and easy to do in hardware is to reverse a bit stream.
> 
> What exactly to you mean by bit stream?   

	[Rest of article deleted.]

By _bit stream_ I mean a consecutive collection of bits.  These bits can have
an arbitrary starting and stopping point.

As an example of the use of bit streams, there are methods for generating
non-uniform random variables which make heavy use of the following bit stream
operations.

	Find the distance to the next one in a bit stream.

	Branch on the next bit in the stream.

In these situations, the bits read are removed from the stream (i.e., the 
pointer is advanced).  Also, it is necessary to create an exception if the
stream is exhausted.  Since these are tools, and other algorithms are
available which are computationally more complex but are better suited to
computer architecture, slow methods of accomplishing the ends will not be
used.  (BTW, the different methods yield different results.)

It should be evident that a procedure which only looks at a few bits is
computationally simpler than the addition of two numbers.  But if it takes
20 times as long, it will be only used if absolutely necessary.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)