Fast way to find the lowest set bit in a mask?

BlitzMax Forums/BlitzMax Programming/Fast way to find the lowest set bit in a mask?

ImaginaryHuman

(Posted 2007) [#1]

I have 1 integer containing a bit mask. Various random bits will be set in the integer. It doesn't matter what the overall value of the integer is, the bits are set and cleared individually to indicate various things.

For example it might be %01101010001010010100101001000010. Bit number 0 is on the right (lowest bit), 31 is the upper bit (left).

What is a fast way, using some kind of math or binary operations and NOT a per-bit iterative search, to find the number of the lowest bit which is set (ie return 1 for the second bit and then 6 for the 7th bit etc)?

I currently do bit-tests for all bits in a while-wend loop from 0 to 31, or until a bit is found, and keep a counter of which bit number. This is obviously not a very clever algorithm. Is there some combination of and/or/not/xor/whatever which will return the lowest set bit quickly and in the same amount of time no matter how many bits there are?

Azathoth

(Posted 2007) [#2]

Something like

Function BitGet:Int(value:Int, bit:Int)
	Return value&(1 Shl bit)
EndFunction

It returns non-zero if the bit is set otherwise zero

Edit: Nvm, I thought you were asking to check a bit at a certain position.

ImaginaryHuman

(Posted 2007) [#3]

No, I can to do that already. But to find which is the lowest number bit set, you'd have to test every bit until you find one. That's not efficient. There must be some binary arithmetic type of way to `process` the integer so that it ends up with a bit number.

marksibly

(Posted 2007) [#4]

Strict

Function F( n )
	Global t[]=[..
		0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,..
		31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 ]
	Return t[ (n & -n) * $77cb531 Shr 27 ]
End Function

For Local i=0 Until 32
	Print F( (Rand(65535)|1) Shl i )
Next

Pinched from: http://graphics.stanford.edu/~seander/bithacks.html

ImaginaryHuman

(Posted 2007) [#5]

Hey cool. You're the man!

The "n & -n" is interesting, in that it shows what the lowest bit is. It's the conversion from the bit being set to the `number of the bit` which is the hard part. I couldn't figure out any better way to do it so this should be good enough, and much quicker than a loop that searches for bits.

The form:

Local Found:Int=BitToNumber[(Mask & -Mask) * $77cb531 Shr 27]

is good enough for me.

Thanks.