# Goodies Lemonsoftare

### Site Tools

python:bitwise_op

### BITWISE OPERATIONS IN PYTHON

29.09.2011

#### BITWISE OR

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.

OR 0 1
0 0 1
1 1 1

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```

#### XOR (BITWISE EXCLUSIVE OR)

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.

XOR 0 1
0 0 1
1 1 0

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```

#### BITWISE AND

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.

AND 0 1
0 0 0
1 0 1

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```

#### SHIFTED LEFT

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```

#### SHIFTED RIGHT

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```

#### INVERTED

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)

#### APPENDIX

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

##### USEFUL FUNCTIONS

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

##### Sign-and-magnitude

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```
For 8bits signed we're gonna have: -127..128

##### One's complement

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)```

##### Two's complement

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

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```

```0000 0011 (3)