Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am currently learning about bitwise operation, so bear with me. I understand AND, OR, and shifting. What I don't understand is bit flipping.

So, 5 is 0101. When someone says to me "flip those", it would result in 1010 which is 10. So why does ~5result in -6?

I think I got this very wrong. Can someone enlight me?

(I am putting this here because I think it is a general programming question and not a specific one, which would belong to stack overflow).

Edit 1 Thanks to mcfinnigan's comment I learned that there is a "most significant bit" that defines if a number is positive or negative (correct me if I'm wrong). This would explain why positive results are ending up negative and vice versa. However, IMO the example above would result in -10 then.

Edit 2 Thanks to Don 01001100 and S.Lott, I finally got it.

share|improve this question
3  
You are correct as far as the bits are concerned, it's merely the interpretation of those bits you disagree on. –  delnan Feb 24 '12 at 14:00
2  
In signed values such as integers, the leftmost bit represents the sign. Also, the number representation is likely Two's Complement - see here : en.wikipedia.org/wiki/Two's_complement –  mcfinnigan Feb 24 '12 at 14:04
add comment

3 Answers

up vote 10 down vote accepted

If you're using a two's complement signed integer, then the first bit indicates the sign, and the remaining bits count down from -1, with -1 represented as all "1" bits, so, counting down, you have:

 7: 0111
 6: 0110
 5: 0101
 4: 0100
 3: 0011
 2: 0010
 1: 0001
 0: 0000
-1: 1111
-2: 1110
-3: 1101
-4: 1100
-5: 1011
-6: 1010
-7: 1001
-8: 1000
share|improve this answer
    
So: flipping 0101 (which has a msb of 0) gives 1010, but with msb 1 (negative), which means -2 + -8 = -6. right? –  pduersteler Feb 24 '12 at 14:19
1  
1010 means -8 + 2 = 6. You can think of the first bit being "1" as "give me the largest negative number possible", which is -8 for four bits, and then the remaining bits are what you add to it, 2 in this case. –  Don 01001100 Feb 24 '12 at 14:23
    
So this is not making all bits negative, but the leftmost / largest, and the rest ones are still positive? –  pduersteler Feb 24 '12 at 14:24
    
might be worth mentioning why 2s complement is like this i.e what advantage it has over 1s complement –  jk. Feb 24 '12 at 14:41
add comment

As explained in the Wikipedia article on one's complement, there are at least three different systems for representing signed binary numbers:

  • sign magnitude: This is the system where you the most significant bit represents the sign, and the rest of the word represents the magnitude of the number. In this system, an 8-bit representation of -5 would be 10000101. This is simple conceptually, but it has some problems. For example, for 8-bit numbers, 00000000 - 00000001 = 11111111, which is to say that 0 - 1 = -127. To do math with sign magnitude numbers, you have to consider the sign bit separately from the rest of the value.

  • one's complement: Negative numbers are represented by inverting all the bits. Again, this is conceptually simple, but suffers from the fact that there are two representations of 0: 00000000 and 11111111.

  • two's complement: Negative numbers are formed by taking the one's complement of the number and adding 1. This system avoids the issues explained above: there's only one representation of 0, and it doesn't require any special treatment for the sign bit.

It's worth pointing out that in all three systems, you can tell the sign of a number by looking at the most significant bit. With sign magnitude, you have to move the most significant bit if you change the size of a number's representation: 1101 becomes 10000101 when you move from a 4-bit representation to 8-bit. With one's complement and two's complement, you can instead "sign extend" the number, which means that you just replicate the most significant bit: 1101 becomes 1111101.

So, 5 is 0101. When someone says to me "flip those", it would result in 1010 which is 10. So why does ~5 result in -6?

Two's complement is the standard today, so you need to do more than flip the bits. You also need to add 1. To form -5, you start with 0101, flip all the bits to get 1010, and then add 1 to arrive at 1011. You can verify that this really is -5 by changing the sign again: start with 1011, flip the bits to get 0100, and add 1 to arrive at 0101, which is 5.

share|improve this answer
add comment

You're not quite right. I'll use 32-bit 2's complement values, since they're pretty common.

It's not 00000000 00000000 00000000 00001010

(Which is not 9, BTW, check your math more carefully.)

It's 11111111 11111111 11111111 11111010

Which is -6

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.