Bithack for Bitmapped Memory Manager

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/?

>>1
I just know a few for unsigned ints in ANSI/ISO C.

Oh wow, nevermind. I found the answer here:
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

It tells you how to get the rightmost set bit by ANDing a number with its two's complement. From there, all I need to do is toggle the bit by XORing the number with the result of the previous operation.

I'm an idiot who can't into Google. Any other thoughts? Did I make any mistakes?

If you're using C, it's best to write the way that's easiest to understand and let the compiler optimize. A compiler like LLVM could turn it into a single clz/ffs/bsf assembly instruction. Your "bithack" would probably be slower because the compiler wouldn't be able to understand it.

>>3

This is called 'bit twiddling'.

From: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious


unsigned int v; // 32-bit word to find the log base 2 of
unsigned int r = 0; // r will be lg(v)

while (v >>= 1) // unroll for more speed...
{
  r++;
}

Everyone should know that.

>>5
Now this is something most compilers could optimize.

>>1
Using x86's bsf instruction.

>>7
U MENA PowerPC's clz

>>4
Of course it is good practice to not be clever with your code. I'm not some newbie naively attempting to be a human compiler. I just know of no standard way of telling a C compiler "see this integer?  turn all the bits off except the rightmost set one" so that it can be optimized to use processor-specific instructions like the ones you mentioned (thank you for that, though, looking them up was very informative).

I would not be surprised if my "bithack" method resulted in a slower program than one that made use of BSF or whatever. I am simply under the impression that when programming in C, you are up shit's creek for communicating these specialized use cases.

Feel free to enlighten me if there is a way. I've heard similar things about SIMD extensions: it's hard for a compiler to understand when it can result in a speedup in plain C, so most people just inline the relevant assembly, but apparently there are some compiler-specific extensions that allow a programmer to say "see this shit right here? use SSE/NEON/whatever on it."

>>8
U MENA ARMv5+'s clz

>>8,10
Shitty dumb goy architectures. x86 is MASTER RACE.

>>11
moar like dubs masterrace amirite xDDD le voldemort knees

>>11
The 8008 which Intel Jews stole to make x86 was designed by Goys at Computer Terminal Corporation.

>>13
you're dumbgoyness is showing -- if we stole it, then it's ours

>>11-14 back to /g/, please.

>>9 I figured it out myself.

http://en.wikipedia.org/wiki/Find_first_set

It turns out, many popular compilers (including GCC) include a library of functions for things like counting leading zeroes or finding the first set bit. These exist entirely so that programmers who need processor-specific features like this can get them without having to use inline assembly and break portability (at least among architectures; using GCC's functions will still prevent you from using other compilers). I'm assuming that if I, say, use a prebuilt function for finding the first set bit and my processor only supports counting the leading zeroes, it will automatically handle the complex task of incrementing the result by one for me.

This is really fascinating, I had no idea that C compilers had features like this. I'm glad I posted this thread, and thank >>4 for his mention of the specific opcodes.

>>15
die