Bit Twiddling in Python – 1 – Basic operations

The 2's Complement form

In the true spirit of the code first approach of this post, we will let the Python interpreter depict the truth. The 2's complement form is a method of representing a binary number. The complement is defined with respect to 2ⁿ. The positive numbers remain unchanged but the negative numbers are represented as 

2ⁿ- the absolute value of the number

To distinguish between positive and negative values, the + values have a leading 0 and the negative values have a leading 1.

The & (AND) operator

In the true spirit of the code first approach of this post, we will let the Python interpreter depict the truth table –

>>> print 0&0 , 1&0, 0&1 , 1&1

0 0 0 1

Python 2.6 added the bin function for converting an int to its binary representation. The representation is preceded by 0b to distinguish from a string. Let’s see what 6 and 7 look like.

>>> bin(6)

'0b110'

>>> bin(7)

'0b111'

>>> 

Using the truth table and the binary representations

 1 1 0

& 

     1 1 1

===============

     1 1 0

Which is 6.

The | (OR)  operator

Again, starting with the truth table –

>>> print 0|0 , 1|0, 0|1 , 1|1

0 1 1 1

Let’s work out a small example, this time slightly bigger expression - 6019 | 7

>>> bin(6019)

'0b1011110000011'

>>> bin(7)

'0b111'

>>> 

Using the truth table and the binary representations

1 0 1 1 1 1 0 0 0 0 0 1 1

|

                         1 1 1

================================

     1 0 1 1 1 1 0 0 0 0 1 1 1

Let’s use the int function to convert this into decimal form and then confirm the correctness –

>>> int('1011110000111' ,2)

6023

>>> 6019 | 7

6023

>>> 

The ^ (XOR ) operator

XOR is just marginally different from the above two operators. An XOR can be thought for distinctness of the bits. XOR result is 1 if and only if the two operand bits are different (which in the case of bits means that one of the bits is 1 and the other is 0). Examining the truth table –

>>> print 0^0 , 1^0, 0^1 , 1^1

0 1 1 0

Again, let us work out an example. We will again do a slightly complicated one namely 500 ^ 501

>>> bin(500)

'0b111110100'

>>> bin(501)

'0b111110101'

Using the truth table and the binary representations

'0b111110100'

^

     '0b111110101'

=======================

     000000001                              

Which is 1.  Let’s confirm the math –

>>> 500 ^ 501

1

>>> 

XOR of any two consecutive gray code numbers is 1, but in general it does not hold for natural numbers. Consider 7 ^ 8. It’s 15 !

The  <<  and  >>  Shift operators

True to its name and the intent expressed by <<, the left shift operator moves bit in the operand by the distance specified as second argument. Let’s try to shift left one bit in the number 5 (101).

101 << 1 should result in 010 which is same as 10 and is the number 2.

>>> 5 << 1

10

Before you throw caution to the wind, beware that if you do serious programming, you may encounter the following common errors –

>>> 75 << 999999999999999999999999999999999999999999

Traceback (most recent call last):

  File "", line 1, in

OverflowError: long int too large to convert to int

>>> 75 << 999999999999

Traceback (most recent call last):

  File "", line 1, in

MemoryError

>>> 75 << 9999999

(emits tones of garbage)

Right Shift >>

Is the opposite of left shift and a couple of examples would clarify further –

>>> 120 >> 1

60

>>> 121 >> 1

60

>>> 

Looking at these examples, you may have guessed by now that left shift by 1 is equivalent of multiplication by 2 and right shift by 1 is same as integer division by 2. Remember, this works only for positive numbers. For negative numbers the truncation is on the wrong side!

The ~ operator

~ is the NOT or the complement operator. When applied on an int x, it returns -x-1.

>>> ~4

-5

>>> ~30000000000000000000000

-30000000000000000000001L

>>> ~-30000000000000000000000

29999999999999999999999L

>>> ~-5

4

If you followed the section on two's complement form, this should appear quite logical.