Bitwise operators:- Ball, carrot, ampersand, tilde

Question

I want the step by step explanation of the following code:

print(1 | 0 ^ 1 & ~0)

I tried with the output bit (output with first and second bit) and got the answer as 0. The tilde function got me hooked up for some time I found it a bit hard. The answer is 1.

Answer 1

First you must understand what each operator does

| - Bitwise OR: Returns True (1) if either of its operands is 1. e.g.

1 | 0 == True

& - Bitwise AND: Returns True if both of its operands are 1. e.g.

0 & 1 == False

^ - Bitwise XOR: Returns True if only one of its operands is 1. e.g.

0 ^ 1 == True

~ - Bitwise NOT: Flips the bit of its operand.

edit: As noted by Daniel Martin, In Python specifically, it flips all of the bits of an arbitrary integer. The formula would be ~x == -x - 1 e.g.

~0 == -1

Then you must understand the order of bitwise operations

In order of precedence:

~ -> & -> ^ -> |

Solving the expression in that order

1. 1 | 0 ^ 1 & ~0 == 1 | 0 ^ 1 & -1 - ~ is applied first
2. 1 | 0 ^ 1 & -1 == 1 | 0 ^ 1 - & is applied second
3. 1 | 0 ^ 1 == 1 | 1 - ^ is applied third
4. 1 | 1 == 1 - | is applied last

Answer 2

Okay, first let's put some parentheses in that code to show how the order of operations applies in python:

print(1 | 0 ^ 1 & ~0)

becomes

print(1 | (0 ^ (1 & (~0))))

Okay, all good.

Now then, first we'll go through what ~0 means, then we'll consider what 1 & (~0) is, then 0 ^ (1 & (~0)), then 1 | (0 ^ (1 & (~0))).

Because these are all bitwise operations, I'm going to flip back and forth between decimal and binary without warning. I hope you've had a basic introduction to what binary is.

So, first ~0. In languages with integer types that have a specific width, (e.g. in C or C++) ~0 would mean "a value that in binary is all 1 bits, as wide as the type", since ~ means "flip all the bits" and 0 is represented with all bits 0. But since python's integers don't have a specific width that would mean "a value that in binary is an infinite sequence of 1 bits", and so we have to fall back on what it says in the documentation:

The unary ~ (invert) operator yields the bitwise inversion of its integer argument. The bitwise inversion of x is defined as -(x+1). It only applies to integral numbers or to custom objects that override the __invert__() special method.

So ~0 is -1.

Now, what's 1 & (-1) ? Well, in binary 1 is just 1, and -1 is all 1 bits, as large as you might want. So the bitwise & of those two values is just 1, since for bitwise & the output has a 1 bit only where both inputs have a 1 bit.

Now, 0 ^ (1). Well, we know what 0 looks like in binary, and we know what 1 looks like in binary (they look just like decimal), and with ^ the output has a 1 bit only where the output and input differ. So 0 ^ 1 is just 1.

Now 1 | (1). This is just 1, by the definition of |.

In a way, python makes reasoning this out harder than it would be in C or many other languages by not having a fixed size for its integers, so when dealing with ~0 you have to briefly imagine that there's this infinite string of 1s that you're dealing with, but it isn't that bad.