Take the 2-minute tour ×

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

share|improve this question
add comment

6 Answers

up vote 4 down vote accepted

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

share|improve this answer
P.S. I don't do Ruby but in Python, 9^15 returns 6 (i.e. 1001 xor 1111 is 0110). –  Jefromi Jul 29 '09 at 17:14
The 9^15 => 6 in Ruby too. Thanks.. my brain cells seem to have called it a day. Need some sleep.. I guess. –  Gishu Jul 29 '09 at 18:07
1^0b1111 == 1, not 2. How do you decide how many leading zeros to use? –  AShelly Jul 29 '09 at 19:01
1^15 => 14 actually. Like Rutger points out below, the number_of_bits to consider needs to be an input param to this function. –  Gishu Jul 30 '09 at 5:18
add comment

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.


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

def maskbits n
  while (mask!=prev)

def ones_complement n

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.

share|improve this answer
I did read that question but I still need this function. Updated question with more specs.. –  Gishu Jul 29 '09 at 17:30
Nice algorithm for finding the significant bits. –  jacobsimeon Jan 10 '13 at 0:17
add comment

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

...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)

...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 :)

share|improve this answer
Had to give Jefromi the accepted.. for the concept and being early :) Your answer is more Rubyish than what i hacked up.. liked adding the method to the Numeric class. Reads better. –  Gishu Jul 29 '09 at 18:09
That won't work for floats, shouldn't you have defined it on the Integer class? –  Adrian Jun 19 '10 at 2:31
add comment

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?

share|improve this answer
I'm using this to match a pattern in a stream of bits. I do need it :) –  Gishu Jul 29 '09 at 17:34
add comment

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.

share|improve this answer
Yes this is my fallback approach. I'd be reading in a 10**4 or 10**6 stream of 1s and 0s... was thinking the bitwise representation might be a more appropriate choice. Don't know how well the strings option would perform or even work.. –  Gishu Jul 29 '09 at 17:37
add comment

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
share|improve this answer
This doesn't work for a bit pattern like 0001 (decimal 1), for which I would expect 1110. The number_of_bits to consider must be passed in as input. –  Gishu Jul 30 '09 at 8:51
add comment

Your Answer


