Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uupsi!cmcl2!adm!smoke!gwyn
From: gwyn@smoke.brl.mil (Doug Gwyn)
Newsgroups: comp.compression
Subject: Re: Sound compression
Message-ID: <16168@smoke.brl.mil>
Date: 16 May 91 03:55:55 GMT
References: <16198@helios.TAMU.EDU> <19524@crdgw1.crd.ge.com> <104045@sgi.sgi.com>
Organization: U.S. Army Ballistic Research Laboratory, APG, MD.
Lines: 42

In article <104045@sgi.sgi.com> rpw3@sgi.com (Rob Warnock) writes:
>By the way, there was a paper in CACM (??? sorry, forgot the ref) a number
>of years ago which proved that there is no closed functional form without
>conditionals which will compute "the highest-order one bit".

And of course that "theorem" is wrong:  using the operand to index
into a table can immediately produce the appropriate answer.

For large word sizes or small machines, that will often be impractical,
but it can serve as a basis for an implementation using smaller tables
(which does require use of conditionals):

	int ffo( register unsigned long x )
		{
		static int	bitnum[256] =
			{      -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
				4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
				5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
				5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
				6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
				6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
				6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
				6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
				7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
			};

		if ( (x & 0xFF000000) != 0 )
			return 24 + bitnum[x >> 24];
		else if ( (x & 0x00FF0000) != 0 )
			return 16 + bitnum[x >> 16];
		else if ( (x & 0x0000FF00) != 0 )
			return	8 + bitnum[x >>  8];
		else
			return	    bitnum[x      ];
		}