# Goodies Lemonsoftare

### Site Tools

python:bitwise_op

# Differences

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

 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 + ​ + + + === 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 + ​ + + + === 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 + ​ + + 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 + ​ + + === 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 + ​ + + === 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 + ​ + + 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 + ​ + + + === 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 + ​ + + //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 + ​ + 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 + ​ + + 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) + ​ + + + == 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 + ​ + + + **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 + ​ + + + Addition: 3 + (-2) + + <​code>​ + 0000 0011 (3) + 1111 1110 (-2) + -------------- + 0000 0001 (1) + ​ + + + == 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.