代码之家 › 专栏 › 技术社区 › Gishu

如何使用Ruby的位运算符计算补码?

bit-manipulation operators ruby

Gishu · 技术社区 · 15 年前

我想要什么:

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

我想这与一点被用来存放标志或其他东西有关…有人能解释这个输出吗?如何在不使用字符串操作的情况下获得一个字符的补码,比如从sprintf输出中剪切最后n个字符以获得“0110”,或者将0替换为1,反之亦然

6 回复 | 直到 15 年前

Cascabel 15 年前

听起来你只想翻转四个位(输入的长度),所以你可能想用1111执行异或运算。

Rutger Nijlunsing 15 年前

Ruby只存储一个(签名的)号码。此数字的内部表示形式与此无关:它可能是fixnum、bignum或其他类型。因此,一个数字中的位数也是未定义的:毕竟它只是一个数字。这与C示例相反,其中int可能是32位(固定)。

那么,~接线员做什么呢?嗯,就像:

class Numeric
    def ~
        return -self - 1
    end
end

…因为这就是“~”在查看2的补码时所表示的。

因此,您的input语句中缺少的是要切换的位数:32位~,不同于一般的~,就像Ruby中一样。

现在,如果您只想位翻转n位,可以执行如下操作:

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

…但是您必须指定要翻转的位数。这不会影响符号标志,因为使用xor时,该标志不在您的范围之内:)

Community CDub 7 年前

见 this question 为什么呢?

您的方法的一个问题是,只有当您只翻转四个有效位时,预期的答案才是真的: 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"

这不会给你期望的输出一句恭维话(1),因为它将1视为“1”,而不是“01”。我不知道函数如何在不将宽度作为参数的情况下推断出需要多少前导零。

Sinan Taifour 15 年前

你在做什么(使用 ~ )算符,确实是一个一的补码。因为Ruby对数字的解释方式,您得到了那些您不期望得到的值。

你真正需要做的将取决于你用这个做什么。也就是说,为什么你需要1的补码?

Scott Dugas 15 年前

如果你使用的是字符串,你可以这样做:

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

如果使用数字,则必须定义有效位的数目,因为:
0110=6;1001=9;
110=6;001=1;

即使忽略了这个标志,你也可能要处理这个问题。

animal 15 年前

记住,如果传入fixnum,您现在就得到一个补码:表示数字的位数在解释器中是固定的,因此在数字9(二进制1001)的二进制表示前面有前导0。通过检查fixnum的大小,可以找到这个位数。(返回的答案以字节为单位)

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

~也在bignum上定义。在这种情况下,它的行为就像所有在bignum中指定的位都被颠倒了,然后如果在该bignum前面有一个1的无限字符串。可以想象,将比特流推到一个bignum中,然后反转整个比特流。但是,您需要在反转之前知道位流的大小,以便在反转后得到有用的结果。

要在你马上回答问题的时候,你可以发现最大的2次方小于你的输入,将它加倍,减去1,然后用你的输入对其结果进行异或运算,并且总是得到一个1的补码,就是你输入数字中的有效位。

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