29.09.2011

A bitwise OR takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits.
For each pair, the result is 1 if the first bit is 1 OR the second bit is 1 OR both bits are 1; otherwise, the result is 0.

x | y bitwise or of x and y

x = 10(1010)  
y =  4(0100) <-- padded with one 0 at left to be equal length 

10 | 4 = 14
1010 OR
0100 
----------
1110

A bitwise exclusive OR takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits.
It shouts 1 if the two bits are different, and 0 if they are the same.

x ^ y bitwise exclusive or of x and y

x = 10 (1010) y = 4 (0100) ←- padded with one 0 at left to be equal length

x = 10(1010)  
y =  4(0100) <-- padded with one 0 at left to be equal length 

10 ^ 4 = 14
1010 XOR
0100 
----------
1110

A bitwise AND takes two binary representations of equal length and performs the logical AND operation on each pair of corresponding bits.
For each pair, the result is 1 if the first bit is 1 AND the second bit is 1; otherwise, the result is 0.

x & y bitwise and of x and y

x = 10 (1010)
y = 4  (0100) <-- padded with one 0 at left to be equal length

10 & 4 = 0
1010 AND
0100
----------
0000

And another example:

x = 23 (10111)
y = 14 (01110) <-- padded with one 0 at left to be equal length

23 & 14 = 6
10111 AND
01110
----------
00110

A left shift x by n bits is defined as multiplication of x with pow(2, n).
Negative shift counts raise a ValueError exception.
A long integer is returned if the result exceeds the range of plain integers.

x « n x shifted left by n bits

x = 10 (1010)
n = 2

10 << 2 = 40
XX4321 <-bits positions
XX1010  

4321XX <-bits positions
101000
        
10 << 2 = 40

A right shift x by n bits is defined as division x by pow(2, n).

x » n x shifted right by n bits

x = 10 (1010)
n = 2

10 >> 2 = 2
4321 <-bits positions
1010 

XX43 <-bits positions
0010

And another example:

x = 1233 (10011010001)
n = 5 (101)

1233 >> 5 = 38
11 10 9 8 7 6 5 4 3 2 1    
1  0  0 1 1 0 1 0 0 0 1 

X X X X X 11 10 9 8 7 6
0 0 0 0 0 1  0  0 1 1 0

The bitwise inversion of x is defined as -(x+1).
It only applies to integral numbers.

~x the bits of x inverted

x = 10
~x = -(10+1) = -11

Note: For the purpose of shift and mask operations, integers are assumed to have a binary, two’s complement notation using 32 or more bits, and hiding no bits from the user (http://docs.python.org/reference/datamodel.html)

Binary Addition Appendix

0 + 0 = 1
1 + 0 = 1
0 + 1 = 1
1 + 1 = 10

bin(x) → decimal x transformed to binary
int(“binary_string”, 2) - binary→decimal

Allocating one sign bit to represent the sign: set that bit (often the most significant bit MSB) to 0 for a positive number, and set to 1 for a negative number.
The remaining bits in the number indicate the magnitude (or absolute value)

A consequence of this representation is that there are two ways to represent zero, 00000000 (0) and 10000000 (−0).
Sign-and-magnitude is the most common way of representing the significand in floating point values.

MSB 8 7 6 5 4 3 2 1 LSB
    0 0 0 0 1 0 1 0

and the negative one
MSB 8 7 6 5 4 3 2 1 LSB
    1 0 0 0 1 0 1 0

The one's complement form of a negative binary number is the “bitwise NOT” applied to it. (like sign-and-magnitude representation, one's complement has two representations of 0: 00000000 (+0) and 11111111 (−0))

This numeric representation system was common in older computers; the PDP-1, CDC 160A and UNIVAC 1100/2200 series, among many others, used one's-complement arithmetic.

MSB 8 7 6 5 4 3 2 1 LSB
    0 0 0 0 1 0 1 0

and the negative one
MSB 8 7 6 5 4 3 2 1 LSB
    1 1 1 1 0 1 0 1

To add two numbers represented in this system, one does a conventional binary addition, but it is then necessary to add any resulting carry back into the resulting sum.

3  = 11
-2 = 01

3-2 = 11
      01
---------
      00 carry 1
+      1
---------
      01 (decimal = 1)

The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two (specifically, from 2^N for an N-bit two's complement).
The two's complement of the number then behaves like the negative of the original number in most arithmetic, and it can coexist with positive numbers in a natural way.

In two's-complement, there is only one zero (00000000).
Addition of a pair of two's-complement integers is the same as addition of a pair of unsigned numbers (except for detection of overflow, if that is done)

An N-bit two's-complement numeral system can represent every integer in the range −2^(N−1) to 2^(N−1)-1 so for 8 bits you'll have -128..127

CALCULUS METHOD 1

1. write out the number in binary
2. invert the digits
3. add one to the result

8bits example

1. 10 -> 
MSB 8 7 6 5 4 3 2 1 LSB
    0 0 0 0 1 0 1 0

2. invert it
MSB 8 7 6 5 4 3 2 1 LSB
    1 1 1 1 0 1 0 1

3. add one
MSB 8 7 6 5 4 3 2 1 LSB
    1 1 1 1 0 1 0 1 
+   0 0 0 0 0 0 0 1
=   1 1 1 1 0 1 1 0   

CALCULUS METHOD 2

1. Starting from the right, find the first '1'
2. Invert all of the bits to the left of that one

8bits example

1. 10 ->
MSB 8 7 6 5 4 3 2 1 LSB
    0 0 0 0 1 0 1 0  -> first '1' is on position 2 so we have

MSB 8 7 6 5 4 3 2 1 LSB
    X X X X X X 1 0

2. invert the remaining bits

MSB 8 7 6 5 4 3 2 1 LSB
    1 1 1 1 0 1 1 0

Addition: 3 + (-2)

0000 0011 (3)
1111 1110 (-2)
--------------
0000 0001 (1)

Excess-K, also called biased representation, uses a pre-specified number K as a biasing value. A value is represented by the unsigned number which is K greater than the intended value. Thus 0 is represented by K, and −K is represented by the all-zeros bit pattern. This is a generalization of the aforementioned two's-complement, which is virtually the excess-2N−1 representation.