Bitwise operation and usage

eozzy picture eozzy · Nov 17, 2009 · Viewed 143k times · Source

Consider this code:

x = 1        # 0001
x << 2       # Shift left 2 bits: 0100
# Result: 4

x | 2        # Bitwise OR: 0011
# Result: 3

x & 1        # Bitwise AND: 0001
# Result: 1

I can understand the arithmetic operators in Python (and other languages), but I never understood 'bitwise' operators quite well. In the above example (from a Python book), I understand the left-shift but not the other two.

Also, what are bitwise operators actually used for? I'd appreciate some examples.

Answer

paxdiablo picture paxdiablo · Nov 17, 2009

Bitwise operators are operators that work on multi-bit values, but conceptually one bit at a time.

  • AND is 1 only if both of its inputs are 1, otherwise it's 0.
  • OR is 1 if one or both of its inputs are 1, otherwise it's 0.
  • XOR is 1 only if exactly one of its inputs are 1, otherwise it's 0.
  • NOT is 1 only if its input is 0, otherwise it's 0.

These can often be best shown as truth tables. Input possibilities are on the top and left, the resultant bit is one of the four (two in the case of NOT since it only has one input) values shown at the intersection of the inputs.

AND | 0 1     OR | 0 1     XOR | 0 1    NOT | 0 1
----+-----    ---+----     ----+----    ----+----
 0  | 0 0      0 | 0 1       0 | 0 1        | 1 0
 1  | 0 1      1 | 1 1       1 | 1 0

One example is if you only want the lower 4 bits of an integer, you AND it with 15 (binary 1111) so:

    201: 1100 1001
AND  15: 0000 1111
------------------
 IS   9  0000 1001

The zero bits in 15 in that case effectively act as a filter, forcing the bits in the result to be zero as well.

In addition, >> and << are often included as bitwise operators, and they "shift" a value respectively right and left by a certain number of bits, throwing away bits that roll of the end you're shifting towards, and feeding in zero bits at the other end.

So, for example:

1001 0101 >> 2 gives 0010 0101
1111 1111 << 4 gives 1111 0000

Note that the left shift in Python is unusual in that it's not using a fixed width where bits are discarded - while many languages use a fixed width based on the data type, Python simply expands the width to cater for extra bits. In order to get the discarding behaviour in Python, you can follow a left shift with a bitwise and such as in an 8-bit value shifting left four bits:

bits8 = (bits8 << 4) & 255

With that in mind, another example of bitwise operators is if you have two 4-bit values that you want to pack into an 8-bit one, you can use all three of your operators (left-shift, and and or):

packed_val = ((val1 & 15) << 4) | (val2 & 15)
  • The & 15 operation will make sure that both values only have the lower 4 bits.
  • The << 4 is a 4-bit shift left to move val1 into the top 4 bits of an 8-bit value.
  • The | simply combines these two together.

If val1 is 7 and val2 is 4:

                val1            val2
                ====            ====
 & 15 (and)   xxxx-0111       xxxx-0100  & 15
 << 4 (left)  0111-0000           |
                  |               |
                  +-------+-------+
                          |
| (or)                0111-0100