Как вычислить свое дополнение, используя побитовые операторы Ruby?

Question

Что я хочу:

assert_equal 6, ones_complement(9)   # 1001 => 0110
assert_equal 0, ones_complement(15)  # 1111 => 0000
assert_equal 2, ones_complement(1)   # 01 => 10

размер входа не фиксирован, как в 4 битах или 8 битах. скорее это бинарный поток.

Что я вижу:

v = "1001".to_i(2)                 => 9

Там немного переворачивается оператор ~

(~v).to_s(2)                       => "-1010"
sprintf("%b", ~v)                  => "..10110"
~v                                 => -10

Я думаю, что это как-то связано с использованием одного бита для хранения знака или чего-то еще ... может кто-нибудь объяснить этот вывод? Как получить дополнение, не прибегая к строковым манипуляциям, таким как вырезание последних n символов из вывода sprintf для получения «0110» или замена 0 на 1 и наоборот

Answer 1

Ruby просто хранит (подписанный) номер. Внутреннее представление этого числа не имеет значения: это может быть FixNum, BigNum или что-то еще. Следовательно, число битов в числе также не определено: это всего лишь число. Это противоречит, например, C, где int, вероятно, будет 32 бита (фиксированный).

Так что же тогда делает оператор ~? Ну, просто что-то вроде:

class Numeric
    def ~
        return -self - 1
    end
end

... так как именно это '~' представляет при взгляде на числа дополнения 2.

То, чего не хватает в вашем входном операторе, - это количество бит, которое вы хотите переключить: 32-битное ~ отличается от общего ~, как в Ruby.

Теперь, если вы просто хотите перевернуть n-бит, вы можете сделать что-то вроде:

class Numeric
    def ones_complement(bits)
        self ^ ((1 << bits) - 1)
    end
end

... но вы должны указать количество бит, которые нужно перевернуть. И это не повлияет на флаг знака, так как тот вне вашей досягаемости с XOR:)

Answer 2

Звучит так, будто вы хотите перевернуть только четыре бита (длину вашего ввода) - так что вы, вероятно, захотите выполнить XOR с 1111.

Answer 3

См. этот вопрос , почему.

Одна проблема с вашим методом заключается в том, что ожидаемый ответ верен только в том случае, если вы перевернете четыре значащих бита: 1001 -> 0110.

Но число сохраняется с ведущими нулями, и оператор ~ также сбрасывает все старшие биты: 00001001 -> 11110110. Тогда ведущий 1 интерпретируется как отрицательный знак.

Вам действительно нужно указать, что функция должна делать с числами, такими как 0b101 и 0b11011, прежде чем вы сможете решить, как ее реализовать. Если вы когда-нибудь захотите перевернуть 4 бита, вы можете сделать v^0b1111, как предложено в другом ответе. Но если вы хотите перевернуть все значащие биты, все становится сложнее.

редактировать

Вот один из способов перевернуть все значащие биты:

def maskbits n
  b=1
  prev=n;
  mask=prev|(prev>>1)
  while (mask!=prev)
    prev=mask;
    mask|=(mask>>(b*=2))
  end
  mask
end

def ones_complement n
  n^maskbits(n)
end

Это дает

p ones_complement(9).to_s(2)  #>>"110" 
p ones_complement(15).to_s(2) #>>"0"
p ones_complement(1).to_s(2)  #>>"0"

Это не дает желаемого результата для ones_compliment (1), потому что он обрабатывает 1 как «1», а не «01». Я не знаю, как функция могла бы определить, сколько ведущих нулей вы хотите, не принимая ширину в качестве аргумента.

Answer 4

Помните, что вы получаете дополнение к одному прямо сейчас с помощью ~, если вы передаете Fixnum: число битов, представляющих число, является фиксированной величиной в интерпретаторе, и, таким образом, перед двоичным представлением перед нулями стоят первые 0. число 9 (двоичное 1001). Вы можете найти это количество бит, изучив размер любого Fixnum. (ответ возвращается в байтах)

1.size            #=> 4
2147483647.size   #=> 4

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

Чтобы ответить на вопрос, задав его сразу, вы можете найти наибольшую степень 2, меньшую, чем ваш вход, удвоить ее, вычесть 1, затем XOR результат этого с вашим входом и всегда получить единичные дополнения. только значащие биты в вашем входном номере.

def sig_ones_complement(num)
  significant_bits = num.to_s(2).length
  next_smallest_pow_2 = 2**(significant_bits-1)
  xor_mask = (2*next_smallest_pow_2)-1
  return num ^ xor_mask
end

Answer 5

Если вы работаете со строками, вы можете сделать:

s = "0110"
s.gsub("\d") {|bit| bit=="1"?"0":"1"}

Если вы работаете с числами, вам нужно определить количество значащих бит, потому что:
0110 = 6; 1001 = 9;
110 = 6; 001 = 1;

Даже если игнорировать знак, вам, вероятно, придется с этим справиться.

Answer 6

То, что вы делаете (используя оператор ~), действительно является дополнением. Вы получаете те значения, которые не ожидаете из-за того, как Ruby интерпретирует число.

То, что вам действительно нужно сделать, будет зависеть от того, для чего вы это используете. То есть зачем вам 1 дополнение?