Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!dali.cs.montana.edu!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!wuarchive!m.cs.uiuc.edu!ux1.cso.uiuc.edu!peltz
From: peltz@cerl.uiuc.edu (Steve Peltz)
Newsgroups: comp.compression
Subject: Re: Sound compression
Keywords: sound compression
Message-ID: <1991May22.192645.16551@ux1.cso.uiuc.edu>
Date: 22 May 91 19:26:45 GMT
References: <104045@sgi.sgi.com> <91May15.140250edt.750@neuron.ai.toronto.edu> <105539@sgi.sgi.com>
Sender: usenet@ux1.cso.uiuc.edu (News)
Organization: UIUC Computer-based Education Research Lab
Lines: 36

In article <105539@sgi.sgi.com> rpw3@sgi.com (Rob Warnock) writes:
>Let's re-open the question to others: What *other* fast, practical methods
>are there to find the "leftmost bit" a.k.a. "binary logarithm" of an integer,
>besides:

Here's what is used on our system (Cyber 60 bit word one's complement; I'm
translating to C). It requires a fast population count and shifting.

#define blur(i,o) d = d | ((d = d | ((o) >> i)) >> (2 * i))
#define hibit(x)  bitcnt(blur(16, blur(4, blur(1, d = x)))

This also obviously depends on order of operation; let's see if I can unroll it
a bit.

	/* blur(1, d=x) */
	d = x;
	d |= d >> 1;
	d |= d >> 2;
	/* blur(4, ...) */
	d |= d >> 4;
	d |= d >> 8;
	/* blur(16, ...) */
	d |= d >> 16;
	d |= d >> 32;
	return bitcnt(d);

d is a signed 60-bit value, so right shifting does shift in the sign bit, but
that doesn't matter for the algorithm.

I don't know if there is another origin for this algorithm, but it is listed
in our library as having been written by Mike Huybenz, Feb '77.

For a 32 bit value, the last shift isn't necessary.
--
Steve Peltz
Internet: peltz@cerl.uiuc.edu	PLATO/NovaNET: peltz/s/cerl