From: Hugh Sasse Staff Elec Eng <hgs@...>
Date: 2001-07-27T23:39:21+09:00
Subject: [ruby-talk:18634] Most Sig. NonZero bit, efficiently?

I see that integer types (Bignum and Co.) support [] to get the kth bit out.
They don't seem to have each (which is interesting) so what is the
most effective way to get the most significant non-zero bit in a bignum?

Obviously log to base 2 is heavy machinary for this task, and the only
other way I can see to do this is:

top = my_number.size * 8
while ((my_number[top] == 0) && (top > 0) ) { top -= 1 }

but this seems a little primitive.

Why do I need this stuff?  I'm trying to create Cyclic Redundancy Check
information for marshalled data I'm sending over UDP.  AFAIK UDP guarantees
nothing -- arrival, ordering, or intact data may, or may not happen.
The CRC algorithm relies on a bitwise long-division-like process, but using
XOR instead of divide, so hence the need to align MSBs frequently.

        Hugh