Как повернуть биты целого числа влево - PullRequest
Новая
       71

Как повернуть биты целого числа влево

1 голос
/ 12 февраля 2020

Мне нужно повернуть влево 32 бита целого числа на n в Ruby. Я пытаюсь с канонической реализацией: 

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

Что-то идет не так, используя большие числа: результат переполняется 32 бита. Я предполагаю, что это произошло потому, что теоретический неограниченный размер целого числа в Ruby.

Как это можно сделать без переполнения?

1 Ответ

4 голосов
/ 12 февраля 2020

Ruby автоматически переключится на другое внутреннее представление для размещения больших чисел, поэтому вам нужно ограничить его маскированием: 

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

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

Где mask указывает, какие биты должны быть сдвиг влево, остальное эффективно обрезается перед сдвигом.

Ruby с удовольствием сделает действительно нелепые вещи, такие как 1 << (1 << 16), который выдает число длиной 19 729 цифр. Это также целое число.

Обратите внимание, что если вам нужен этот метод более производительный, вы захотите использовать справочную таблицу, а не вычисления каждый раз, хотя, как всегда, я бы сделал бенчмарк, чтобы убедиться, что этот подход быстрее.

...