CODEWITHSUNDEEP
rubybinarybit-manipulationbitwise-operatorsinteger-overflow
Yohji
Yohji

Reputation: 170

How to left rotate bits of an Integer

I need to left-rotate 32 bits of an Integer by n in Ruby. I'm trying with the canonical implementation:

class Integer
    def rotl32 n
        return (self << n) | (self >> (32 - n))
    end
end

Something is going wrong using large numbers: the result overflows 32 bits. I guess it happened because the theoretical unlimited size of an Integer in Ruby.

How can it be done without overflowing?

Upvotes: 1

Views: 168

Answers (1)

tadman
tadman

Reputation: 211670

Ruby will automatically switch to a different internal representation in order to accommodate larger numbers, so you'll need to cap it with masking:

class Integer
  def rotl32(n)
    mask = (1 << (32 - n)) - 1

    ((self & mask) << n) | (self >> (32 - n))
  end
end

Where mask indicates which bits should be shifted left, the rest effectively trimmed off before shifting.

Ruby will gladly do really ridiculous stuff like 1 << (1 << 16) which produces a number 19,729 digits long. This is also an Integer.

Note if you need this method more performant you'd want to use a look-up table rather than computing every time, though as always I'd benchmark to make sure that approach is faster.

Upvotes: 4

Related Questions