How to compute one's complement using Ruby's bitwise operators ?

Question

What I want:

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

the size of the input isn't fixed as in 4 bits or 8 bits. rather its a binary stream.

What I see:

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

There's a bit flipping operator ~

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

I think its got something to do with one bit being used to store the sign or something... can someone explain this output ? How do I get a one's complement without resorting to string manipulations like cutting the last n chars from the sprintf output to get "0110" or replacing 0 with 1 and vice versa

Answer 1

It sounds like you only want to flip four bits (the length of your input) - so you probably want to XOR with 1111.

Answer 2

See this question for why.

One problem with your method is that your expected answer is only true if you only flip the four significant bits: 1001 -> 0110.

But the number is stored with leading zeros, and the ~ operator flips all the leading bits too: 00001001 -> 11110110. Then the leading 1 is interpreted as the negative sign.

You really need to specify what the function is supposed to do with numbers like 0b101 and 0b11011 before you can decide how to implement it. If you only ever want to flip 4 bits you can do v^0b1111, as suggested in another answer. But if you want to flip all significant bits, it gets more complicated.

edit

Here's one way to flip all the significant bits:

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

This gives

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

This does not give your desired output for ones_compliment(1), because it treats 1 as "1" not "01". I don't know how the function could infer how many leading zeros you want without taking the width as an argument.

Answer 3

What you are doing (using the ~) operator, is indeed a one's complement. You are getting those values that you are not expecting because of the way the number is interpreted by Ruby.

What you actually need to do will depend on what you are using this for. That is to say, why do you need a 1's complement?

Answer 4

If you're working with strings you could do:

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

If you're working with numbers, you'll have to define the number of significant bits because:
0110 = 6; 1001 = 9;
110 = 6; 001 = 1;

Even, ignoring the sign, you'll probably have to handle this.

Answer 5

Ruby just stores a (signed) number. The internal representation of this number is not relevant: it might be a FixNum, BigNum or something else. Therefore, the number of bits in a number is also undefined: it is just a number after all. This is contrary to for example C, where an int will probably be 32 bits (fixed).

So what does the ~ operator do then? Wel, just something like:

class Numeric
    def ~
        return -self - 1
    end
end

...since that's what '~' represents when looking at 2's complement numbers.

So what is missing from your input statement is the number of bits you want to switch: a 32-bits ~ is different from a generic ~ like it is in Ruby.

Now if you just want to bit-flip n-bits you can do something like:

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

...but you do have to specify the number of bits to flip. And this won't affect the sign flag, since that one is outside your reach with XOR :)

Answer 6

Remember that you are getting the one's complement right now with ~ if you pass in a Fixnum: the number of bits which represent the number is a fixed quantity in the interpreter and thus there are leading 0's in front of the binary representation of the number 9 (binary 1001). You can find this number of bits by examining the size of any Fixnum. (the answer is returned in bytes)

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

~ is also defined over Bignum. In this case it behaves as if all of the bits which are specified in the Bignum were inverted, and then if there were an infinite string of 1's in front of that Bignum. You can, conceivably shove your bitstream into a Bignum and invert the whole thing. You will however need to know the size of the bitstream prior to inversion to get a useful result out after it is inverted.

To answer the question as you pose it right off the bat, you can find the largest power of 2 less than your input, double it, subtract 1, then XOR the result of that with your input and always get a ones complement of just the significant bits in your input number.

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