CODEWITHSUNDEEP
haskellbit-manipulationghc
dfeuer
dfeuer

Reputation: 48591

How can I shift all the zeros off?

This is a follow-up to my last question. I managed to implement a pretty fast "bit queue builder" as

data BitQueueB = BQB !Word !Word

by pushing elements in from the left (starting with a guard bit), then when I'm done "building" the queue, counting the trailing zeros and shifting them off, installing a new guard bit on the left.

However, this solution doesn't really do anything for GHC < 7.10, since that's when countTrailingZeros was introduced. I also can't help wondering if there's some more magical way to accomplish this shift, or is leftward counterpart.

The point

I have a two-word representation of a double word, guaranteed to have at least one bit set. I'm looking for the fastest way to shift the double word to either the left or the right until the first set bit is shifted off, without using either countLeadingZeros or countTrailingZeros.

One thought

My poor intuition in these matters suggests that if there could be some way to use multiplication if I switch to shifting left, but maybe that's just wishful thinking.

Upvotes: 3

Views: 153

Answers (1)

user555045
user555045

Reputation: 64904

To the left is more annoying. Not actually tested:

m = x
m |= m >> 1
m |= m >> 2
m |= m >> 4
m |= m >> 8
m |= m >> 16
x = x * (0x80000000 / (m >> 1))

This moves the highest set bit to the top by first computing the highest power of two present in the number, and then multiplying by the amount necessary to turn that into the highest possible power of two. It doesn't like it when the top bit is already set (it would divide by 0) and it needs the number of bits to be known. So it's probably better to just count the leading zeros instead of this, or maybe there's something better but I don't know of it.

The version to the right (for completeness?) is nicer, just

x / (x & -x)

Where x & -x is a relatively well-known trick to isolate the lowest set bit.

Upvotes: 2

Related Questions