RE: [Algorithms] Bit fiddling

[Tom F. <to...@mu...>]

You can avoid the loop by using a bit of assembler that most CPU have and
equivalent of these days - scan for lowest-set bit.


int LowestBitConsecutive ( u_int value, u_int consecutiveBitCount )
{
	switch ( consecutiveBitCount )
	{
	case 2:
		value &= value >> 1;
		break;
	case 3:
		value &= ( value >> 1 ) & ( value >> 2 );
		break;	
	case 4:
		value &= ( value >> 1 ) & ( value >> 2 ) & ( value >> 3 );
		break;
	[...etc... up to the max number of consecutive bits you want.]
	}

	if ( value == 0 )
	{
		// BSF doesn't return a result if there are no set bits
		return -1;
	}
	else
	{
		// BSF - Bit Scan Forwards - places the bit position of
		// the lowest-set bit into the result.
		u_int result;
		_asm{
			bsf	result, value
		};
		return result;
	}
}


I suspect the other version may be more efficient, and obviously far more
portable, but hey - I got rid of the loop :-)


Tom Forsyth - Muckyfoot bloke.

What's he up to now (and can I have a go)?
http://www.eidosinteractive.com/downloads/search.html?gmid=86


> -----Original Message-----
> From: John Mckenna [mailto:jmc...@re...]
> Sent: 03 February 2002 17:06
> To: Algorithms
> Subject: RE: [Algorithms] Bit fiddling
> 
> 
> >From: Joe Ante [mailto:jo...@li...]
> 
> >Are there any tricks to create the lowest index to a 
> >consecutive number of bits. If there are no n consecutive
> >bits in the bitmask it should return -1 or some other
> >unique number.
> 
> Here's another approach.  It still has a loop - I think 
> that's unavoidable.
> 
> int LowestBitConsecutive ( u_int value, u_int consecutiveBitCount )
> {
> 	u_int mask = (1 << consecutiveBitCount) - 1;
> 	u_int notValue = value ^ 0xffffffff;
> 	u_int workingMask = mask;
> 	u_int prevMask = 0;
> 	int match = notValue & workingMask;
> 	u_int shift = 1;
> 	while ( (match != 0) && (prevMask < workingMask) )
> 	{
> 		shift = 2*u_int(match & -match);
> 		prevMask = workingMask;
> 		workingMask = mask * shift;
> 		match = notValue & workingMask;
> 	}
> 	if ( prevMask < workingMask )
> 	{
> 		return LowestBit( shift );
> 	}
> 	else
> 	{
> 		return -1;
> 	}
> }
> 
> It's based on one of the standard string-searching 
> algorithms: build a mask
> (the string you're searching for), and start with it lined up 
> at the low end
> of the word.  Each iteration, shift it up to just past the 
> lowest mis-match
> (it would be better to shift it up to just past the highest 
> mis-match, but
> that's harder to find).
> 
> If the mask gets shifted off the top of the word, it's time to stop
> searching (that's what the prevMask < workingMask test does).
> 
> If you wanted the highest index instead, you could start with 
> the mask at
> the high end of the word, and search down.  That way the 
> lowest mismatch
> test would be finding the correct bit, and the loop would exit sooner.
> -Virus scanned and cleared ok
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>