Name: Anonymous 2012-03-28 12:53
Does anyone know a "bithack" (for lack of a better word, preferably a one or two line operation) for detecting the first set (or unset, either way) bit in an integer? In other words, if I have an integer like so:
0b00110101
and apply the "bithack" operation to it, it would return something like:
0b00100000
I understand that the effect will probably depend on the endianness of my processor's architecture. If there is a faster version that instead returns the first unset bit, that'd be ok as well.
Why do I want to know this?
I'm writing a simple bitmapped memory manager for managing a constant-size region of memory that has been separated into equally-sized chunks. You can easily memory in this way with a bitmap, one bit for each chunk (or # of chunks / 8 bytes of memory). A 0 indicates a free chunk, and a 1 indicates a chunk currently in use (or vice-versa, if it's easier to program that way). "Allocating" new chunks within this block of memory is easy, then: Find the first unset bit in the bitmap, mark it as set, and transform it into the address of the chunk. To free, do the opposite: Take the address of the chunk, get the corresponding bit, and unset it.
It's a trivial problem to solve if you use a byte, the smallest machine-addressable data size, to store each bit of the bitmap, but that uses 8x the memory that would have been used with a single bit per chunk approach, while possibly being slower.
With a single bit per chunk, I can easy find the first word with an unset bit (if a word has no unset bits, it should equal 0xFFFFFFFF, or equal 0 if it has no set bits), it's just the process of finding the first unset/set bit that I'm having trouble doing without being totally naive and using a billion branches. Any thoughts, /prog/?
0b00110101
and apply the "bithack" operation to it, it would return something like:
0b00100000
I understand that the effect will probably depend on the endianness of my processor's architecture. If there is a faster version that instead returns the first unset bit, that'd be ok as well.
Why do I want to know this?
I'm writing a simple bitmapped memory manager for managing a constant-size region of memory that has been separated into equally-sized chunks. You can easily memory in this way with a bitmap, one bit for each chunk (or # of chunks / 8 bytes of memory). A 0 indicates a free chunk, and a 1 indicates a chunk currently in use (or vice-versa, if it's easier to program that way). "Allocating" new chunks within this block of memory is easy, then: Find the first unset bit in the bitmap, mark it as set, and transform it into the address of the chunk. To free, do the opposite: Take the address of the chunk, get the corresponding bit, and unset it.
It's a trivial problem to solve if you use a byte, the smallest machine-addressable data size, to store each bit of the bitmap, but that uses 8x the memory that would have been used with a single bit per chunk approach, while possibly being slower.
With a single bit per chunk, I can easy find the first word with an unset bit (if a word has no unset bits, it should equal 0xFFFFFFFF, or equal 0 if it has no set bits), it's just the process of finding the first unset/set bit that I'm having trouble doing without being totally naive and using a billion branches. Any thoughts, /prog/?