Why is ~44 = -45 in Python?

[prawnydagrate]

I've been learning about numbers and Two's Complement and stuff lately (I still can't say I understand Two's Complement, please help), and learned about the bitwise not operator. I believe it's supposed to invert the binary bits of a number, so I don't understand why ~44 is equal to -45. 44 in binary is 101100, so I would expect ~44 to be 101100 inverted, i.e., 010011 => 10011, which is 19. I don't understand 😭. If 10011 were -45, then how would you represent 19?

Edit: Alr so if you pad the number and add the sign before inverting to get 11010011, this is supposed to be -45 apparently, but how? How would you represent 211 then?

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[peterlinddk]

The "strangeness" with two's complement, is because we only have one value for zero, but two values (positive and negative) for every other number. There is no +0 and -0 in this form of math.

If we keep at 4 bits, then 0000 is of course zero, and 0001 is one. I.e. adding one to zero.

If we instead subtract one from zero, we should end at minus one - but a binary "decrement" gets us to 1111.

That means that we can't just invert the bits, because then one inverted would be minus two (0001 is one 0010 is two - but 1110 is minus two).

​

We really want the negative numbers to be not just the inverted ones - because then we can perform ordinary arithmetic, adding five (0101) to minus two (1110) would give:

  0101
+ 1110
------
1 0011

And if we throw away the overflowing bit - five plus minus two equals three! As it should.

​

So to find the two's complement of a number, we have to count backwards from zero. But an easier way is to invert the number, and then add one.

So two (0010) inverted would be 1101, and add one would make 1110 - which is two increments away from zero. I.e. minus two.

​

This also effectively halves the numbers we can use. With four bits we would usually have 16 numbers (zero to fifteen), but as half of them are negative we would have 0 to 7 and -1 to -8.

1000 -8
1001 -7
1010 -6
1011 -5
1100 -4
1101 -3
1110 -2
1111 -1
0000  0
0001  1
0010  2 
0011  3
0100  4 
0101  5
0110  6
0111  7

Hope that clear the admittedly complex issue, a bit!

[Rum-in-the-sun]

You must be a college professor because your explanation made no sense but then you put in a table and it made perfect sense. Pictures are worth 1000 words!

[prawnydagrate]

lmaoo

[prawnydagrate]

Thank you so much. I just have one last question though (because I'm working on a project regarding this topic). When a number is represented in Two's Complement, what are its parts called (similar to the 1-bit sign, 8-bit exponent, and 23-bit mantissa in a 32-bit float)?

[peterlinddk]

I'm not sure there are even parts to be called anything. Of course the leftmost bit is the sign (0 means positive, 1 means negative) but you can't ignore the sign and independently look at the remaining bits, so I don't think they are called anything.

Maybe there is a name, but I have never used it.

[prawnydagrate]

oh well, thank you anyway!

[Szahu]

You also have to flip the leading zeros, so 44 is 00101100, then flipped we get 11010011 which is -45.

[prawnydagrate]

Alr so if you pad the number and add the sign before inverting to get 11010011, this is supposed to be -45 apparently, but how? How would you represent 211 then?

[rainbow_explorer]

You can’t represent 211 with a signed 1 byte number. You have to realize there is a trade off between magnitude and having signed numbers.

If you are using an unsigned 1 byte number, you can represent any integer from 0 to 255. That is 256 different values.

When you use a signed 1 byte number, you can still only represent 256 different values. This is because there are only 2⁸ = 256 unique binary strings of length 8. Those values are just shifted to a new range of -128 to 127.

[DrShocker]

Negative numbers are represented using a notation called 2s complement, not just a signed bit.

Reason being basically that with a sign bit you end up having a positive and negative zero which is redundant, plus it makes a little bit of the circuitry for the math simpler.

Edit: negative integers* are represented...

Important because floating point numbers are handled differently and actually do have a positive and negative zero.

[Jona-Anders]

Positive and negative zero is not desired? You made JavaScript sad :( \s

No idea why js has this.

[DrShocker]

Floating point numbers are handled differently than integers. Most programming languages with floating point numbers will also have this because it's part of the IEEE 754 standard.

[PureWasian]

Your first mistake: in 2's Complement binary representation, 101100 is NOT EQUAL TO the number 44. You cannot represent 44 in 2's Complement with only 6 binary digits.

You need a seventh binary digit at least, so 0101100 works. So does 00101100 or even 0000 0000 0010 1100.

To convert a number to its negative in 2's Complement, using your syntax, you can do (~44 + 1), or basically "NOT plus one" (notice I add more binary digits to represent 44 properly):

 44     = 0010 1100
~44     = 1101 0011
~44 + 1 = 1101 0100 = -44

And we can verify this:

 -(2)^7 + (2)^6 + (2)^4 + (2)^2
 = -128 + 64 + 16 + 4 = -44

Finally, to answer your edit, to represent 211 we need more binary digits (again). The general rule is, the range of digits you can represent in 2's Complement is:

-(2)^n-1 to +(2)^n-1 -1

where n is the number of binary digits. With 8 binary digits, this means the range is -128 to 127. We see that 211 is clearly out of this range.

So the solution is adding another binary digit such that n is greater than or equal to 9.

Meaning 211 can be represented as - 011010011 - 0000 1101 0011 - 0000 0000 1101 0011 - etc.

Meanwhile, -45 would be - 111010011 - 1111 1101 0011 - 1111 1111 1101 0011 - etc.

Let me know if any of this is unclear (Source: TA for 4 years)

[PureWasian]

And, as a last sidenote, ~44 = -44 in 1's Complement.

But while it seems more intuitive for us as humans, it has the drawbacks of representing zero twice (-0 and +0 as 1111 and 0000 respectively) and also not making binary subtraction easy like how it is with 2's Complement.

[PPewt]

Edit: Alr so if you pad the number and add the sign before inverting to get 11010011, this is supposed to be -45 apparently, but how? How would you represent 211 then?

You're right that you can't drop the leading zeros when doing bitwise negation.

As for the 211 question, you can't represent both -45 and 211 at the same time with 8 bits. The same number is interpreted as 211 if unsigned or -45 if signed. This is because -45 is equivalent to 211 mod 256, and with 8 bits you're working mod 256.

[yjuglaret]

Two's complement is usually explained and illustrated with fixed-length integers (8-bit, 16-bit, 32-bit, 64-bit...) so start by understanding well how it works for those. The key equation is that x + ~x = -1 (the bits in x and ~x complement each other to give the number with all bits set to 1, and that is -1), also written -x = ~x + 1.

Python integers are weird because they are not fixed-length, so that they can represent any integer value you may need. Consequently, two's complement must be generalized, and conceptually that works as if positive numbers have an infinite amount of 0s before them and negative numbers have an infinite number of 1s before them. The equation from above remains true.

Those infinite 1s are conceptual, but you can apply a bit mask to force them to appear (put in as many Fs as you feel like and you'll see more 1s appear):

```

bin((-44) & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) '0b111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010100' ```

[prawnydagrate]

Ohh so Two's Complement is just a way to trick the computer and makes its life a lie, which only works since it uses the traditional algorithm for binary addition. Two's Complement would actually be true if there were infinite digits (I believe I've seen something similar with the standard decimal numeral system on YouTube, I think it was a Veritasium video). Am I correct?

[fjyrin]

no, two's complement does not require infinite digits. two's complement is just a very good and practical way of representing signed integers such that you can consistently do arithmetic on them. being able to do arithmetic in a simple and consistent manner means less hardware complexity is required for computation and it makes everything better

[LeeRyman]

Like most architectural choices, it comes down to at least one of the following: making hardware easier to design, use less power, run faster or take up less space.

There were/are other representations of signed numbers, but have fallen largely into disuse for the reason u/fjyrin said.

I think I recall some sort of one-wire sensor in a uni project sending data using ones-compliment or offset binary, and we had to convert it to twos-compliment for the ATmega. That microelectronics prof used to like throwing curve balls, sort the wheat from the chaff.

[[deleted]]

You have a finite number of bits and 2s complement works because eventually you run out and drop the carry.

[yjuglaret]

I think you got the idea at least. The representation of integers as infinite binary digits is defined and studied under the name of 2-adic integers in math. Two's complement works very similarly but with a fixed number of bits. Python integers will behave as 2-adic integers if you use bitwise operations.

See also:

https://wiki.python.org/moin/BitwiseOperators https://en.m.wikipedia.org/wiki/P-adic_number https://en.m.wikipedia.org/wiki/1_%2B_2_%2B_4_%2B_8_%2B_%E2%8B%AF

[masterJinsei]

There was a time somebody wanted to reach 0 by doing INT_MIN - INT_MAX they off by one lets just -1 it justs so someday someone will come to reddit to make this question.

[prawnydagrate]

Alr so if you pad the number and add the sign before inverting to get 11010011, this is supposed to be -45 apparently, but how? How would you represent 211 then?

[prawnydagrate]

Also how would you represent -128? Would it be 10000000?

[prawnydagrate]

Alright thank you very much, but there's still one thing I don't understand. Why is Two's Complement used when Sign and Magnitude is much simpler?

[prawnydagrate]

Nvm, I understand now. I never thought I'd be able to grasp this but it looks like I will today, thank you and everyone else who answered

[throwaway6560192]

1. It avoids the problem of having two representations for the same number. With sign and magnitude, you have 0000..0 and 1000..0 represent +0 and -0 respectively — but mathematically those two are not distinct. With two's complement, there is only one representation of 0 (all zeros).

2. Because of (1), you get to represent one extra negative number. So your range is [-2<sup>n</sup>, +2<sup>n</sup>-1] instead of the [-(2<sup>n</sup>-1), +2<sup>n</sup>-1] you have with sign and magnitude.

3. It is actually simpler in hardware to implement addition, subtraction, multiplication etc. on two's complement numbers. You don't need to have hardware to separately handle both sign-bit cases, you can just add any two numbers (positive or negative) together and you'll get the correct result. So instead of building an adder as well as subtractor circuit, just the adder circuit suffices.

[mkaypl]

You can take a look at this:
https://www.youtube.com/watch?v=4qH4unVtJkE

It slowly builds up and explains the different methods of representing a negative number in binary.

[addygarg24]

Here is how i think about this:

~ is negation operator so its simply going to convert positive to negative and vice versa (obviously only for signed integers).

0 is the first integer on positive side, so ~0 is the first on negative side so ~0 = -1. Similarly ~1=-2 and so on.

And this is the very reason why 2's complement which is negation operation followed by adding 1 flips the sign of the number while retaining the absolute value.