The index of the first bit

Question

I can see in http://hackage.haskell.org/package/base-4.7.0.0/docs/Data-Bits.html#v:bit how to convert from an Int, n, to a Bit that has the nth bit set, using

bit :: Int -> a

However, how can I do the inverse of this? (Assuming the input Bit just has 1 bit set in it?)

Answer 1

Since base-4.8.0.0 there are

countLeadingZeros :: FiniteBits b => b -> Int
countTrailingZeros :: FiniteBits b => b -> Int

Those index the most-significant and least-significant set bits starting from the most-significant and least-significant ends respectively. Subtract from finiteBitSize :: FiniteBits b => b -> Int to count from the other end.

Answer 2

popCount $ x-1 does that, effectively by counting the number of trailing zeroes. Subtracting 1 turns the trailing zeroes into ones and resets the only one that should be there.

---

This is easy to adapt to a more general case without the assumption that only one bit of the input is set: popCount $ complement x .&. (x-1)

The main idea is the same, and the ANDing with the complement of x gets rid of the ones that aren't newly created by the subtraction (which are the only ones that should be counted).