Path: utzoo!utgpu!attcan!uunet!nuchat!texbell!bigtex!milano!cs.utexas.edu!tut.cis.ohio-state.edu!cwjcc!hal!nic.MR.NET!umn-cs!hall!pmk
From: pmk@hall.cray.com (Peter Klausler)
Newsgroups: comp.arch
Subject: Leading zero and pop count
Message-ID: <10882@hall.cray.com>
Date: 2 Nov 88 16:44:17 GMT
Organization: Cray Research, Inc., Mendota Heights, MN
Lines: 28


In article <998@l.cc.purdue.edu>, Herman Rubin proposes that HW be able to:
>	Find the distance to the next one in a bit stream FAST. It would
> be good to have an exception handler if one is not found.  I am considering
> algorithms not worth implementing if the operation is slow.

This is the "leading zero count" instruction common to Cray instruction sets.
The CFT77 compiler provides an intrinsic LEADZ function to get at this
instruction. The Cray-2 also has a vector version.

The leading zero count and population count (add up the 1 bits) instructions are
fertile ground for some nifty bit-twisting tricks. For example, the code
sequence I generate for the C logical negation operator ("!") is:

	S1	ZS0	; take leading zero count of argument
	S1	S1>6	; shift right six bits

This turns 0 into 1 and everything else into 0 on a 64-bit machine.

Population count can be handy when applied to vector masks.
After constructing an iota vector from a mask, the pop count gives you
its length.

I've never seen these useful operations in another architecture, though.
Have you? I'd be interested in hearing about it. I'm ignorant of HW design,
but they can't be too hard to implement.

-Peter Klausler / Cray Research compiler development / Mendota Heights, MN