Keith Devens .com

Entry 1297

Adam asks, "Is there some ultra-leet way given a 16 bit int with a single bit sent to determine which bit is set? That doesn't involve a 64k lookup table with a lot of zeros in it?"

Well, if only one bit is set it can only be one of 16 possible numbers, so the most expensive way to do it is to just do 16 comparisons. And if it happens to be the first one you test against, you only have to do one comparison

Is there any better way to do it? Hmm, since the number's going to be a power of two, I suppose you can do sort of a binary search on it, say "is it greater than 2^8? Yes, check 2^12, otherwise check 2^4", etc. Is there any better way than that? How many comparisons would that be?

Permalink | Comments? | id 1297

01:55 (utc-5)