User Tools

Site Tools


python:bitwise_op

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

python:bitwise_op [2013/03/16 17:41]
python:bitwise_op [2013/03/16 17:41] (current)
Line 1: Line 1:
 +==== 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
 +
 +
 +<​code>​
 +x = 10(1010)  ​
 +y =  4(0100) <-- padded with one 0 at left to be equal length ​
 +
 +10 | 4 = 14
 +1010 OR
 +0100 
 +----------
 +1110
 +</​code>​
 +
 +
 +=== 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
 +
 +
 +<​code>​
 +x = 10(1010)  ​
 +y =  4(0100) <-- padded with one 0 at left to be equal length ​
 +
 +10 ^ 4 = 14
 +1010 XOR
 +0100 
 +----------
 +1110
 +</​code>​
 +
 +
 +=== 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
 +
 +
 +<​code>​
 +x = 10 (1010)
 +y = 4  (0100) <-- padded with one 0 at left to be equal length
 +
 +10 & 4 = 0
 +1010 AND
 +0100
 +----------
 +0000
 +</​code>​
 +
 +And another example:
 +
 +<​code>​
 +x = 23 (10111)
 +y = 14 (01110) <-- padded with one 0 at left to be equal length
 +
 +23 & 14 = 6
 +10111 AND
 +01110
 +----------
 +00110
 +</​code>​
 +
 +=== 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
 +
 +<​code>​
 +x = 10 (1010)
 +n = 2
 +
 +10 << 2 = 40
 +XX4321 <-bits positions
 +XX1010  ​
 +
 +4321XX <-bits positions
 +101000
 +        ​
 +10 << 2 = 40
 +</​code>​
 +
 +=== 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
 +
 +<​code>​
 +x = 10 (1010)
 +n = 2
 +
 +10 >> 2 = 2
 +4321 <-bits positions
 +1010 
 +
 +XX43 <-bits positions
 +0010
 +</​code>​
 +
 +And another example:
 +
 +<​code>​
 +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
 +</​code>​
 +
 +
 +=== INVERTED ===
 +
 +
 +The bitwise **inversion of x is defined as -(x+1)**. \\ 
 +It only applies to integral numbers.
 +
 +**~x** the bits of x inverted
 +
 +<​code>​
 +x = 10
 +~x = -(10+1) = -11
 +</​code>​
 +
 +//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 ===
 +
 +== BINARY ADDITION ==
 +
 +Binary Addition 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
 +
 +
 +== REPRESENTATION OF NEGATIVE NUMBERS ==
 +
 +== 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.\\ ​
 +
 +<​code>​
 +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
 +</​code>​
 +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.
 +
 +<​code>​
 +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
 +</​code>​
 +
 +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. 
 +
 +<​code>​
 +3  = 11
 +-2 = 01
 +
 +3-2 = 11
 +      01
 +---------
 +      00 carry 1
 ++      1
 +---------
 +      01 (decimal = 1)
 +</​code>​
 +
 +
 +== 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 \\ 
 +
 +<​code>​
 +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   
 +</​code>​
 +
 +
 +**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
 +
 +<​code>​
 +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
 +</​code>​
 +
 +
 +Addition: 3 + (-2)
 +
 +<​code>​
 +0000 0011 (3)
 +1111 1110 (-2)
 +--------------
 +0000 0001 (1)
 +</​code>​
 +
 +
 +== Excess-K ==
 +
 +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.
python/bitwise_op.txt · Last modified: 2013/03/16 17:41 (external edit)