Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!decwrl!sgi!rpw3@rigden.wpd.sgi.com
From: rpw3@rigden.wpd.sgi.com (Rob Warnock)
Newsgroups: comp.compression
Subject: Re: Sound compression
Keywords: sound compression
Message-ID: <104045@sgi.sgi.com>
Date: 15 May 91 05:14:31 GMT
References: <16198@helios.TAMU.EDU> <19524@crdgw1.crd.ge.com>
Sender: guest@sgi.sgi.com
Reply-To: rpw3@sgi.com (Rob Warnock)
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 74

In article <19524@crdgw1.crd.ge.com> davidsen@crdos1.UUCP
(bill davidsen) writes:
+---------------
|   Sorry I don't have source any more, but the way to quickly find the
| high one bit (on a 2's complement machine) is:
| 
|   h1bit = n & (-n)
+---------------

Sorry, this is quite incorrect! This will find the *lowest*-order one bit set!

To find the *highest*-order bit set (a.k.a. a "priority encoder") you need a
find-highest-one function, or a loop, or a "comb". The find-highest function
exists in some CPU instruction sets (e.g., the PDP-10's "JFFO", the Am29000's
"CLZ") but not in others (e.g., the VAX's "FFS" finds the *lowest* bit).

Many software implementations use some version of a binary tree search:

	bit_num_of_highest_one(unsigned int x)
	{
		int answer, i;

		if (x == 0)
			return -1;
		for (answer = 0, i = NBITSPERWORD/2; i; i >>= 1) {
			mask = (~0) << i;
			if (x & mask) {
				x >>= i;
				answer += i;
			}
		}
		return answer;
	}

Often the loop is unrolled, since the wordlength is usually fixed for a given
machine. A co-worker (Brendan Eich) first showed me the "comb" approach:

	bit_num_of_highest_one(unsigned int x)
	{
		int answer = 0;

		if (x == 0)
			return -1;
		if (x & 0xffff0000)
			answer += 16, x &= 0xffff0000;
		if (x & 0xff00ff00)
			answer += 8, x &= 0xff00ff00;
		if (x & 0xf0f0f0f0)
			answer += 4, x &= 0xf0f0f0f0;
		if (x & 0xcccccccc)
			answer += 2, x &= 0xcccccccc;
		if (x & 0xaaaaaaaa)
			answer += 1;
		return answer;
	}

While this is cute, it's not necessarily any faster than an unrolled version
of the "search" code above, since the 32-bit constants needed for the "comb"
version tend to take two instructions to generate on current RISCs.

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".


-Rob

-----
Rob Warnock, MS-1L/515		rpw3@sgi.com		rpw3@pei.com
Silicon Graphics, Inc.		(415)335-1673		Protocol Engines, Inc.
2011 N. Shoreline Blvd.
Mountain View, CA  94039-7311