Time for action – twiddling bits

We will go over three tricks—checking whether the signs of integers are different, checking whether a number is a power of two, and calculating the modulus of a number that is a power of two. We will show an operators-only notation and one using the corresponding NumPy functions:

  1. The first trick depends on the XOR or ^ operator. The XOR operator is also called the inequality operator; so, if the sign bit of the two operands is different, the XOR operation will lead to a negative number. ^ corresponds to the bitwise_xor function. < corresponds to the less function.
    x = np.arange(-9, 9)
y = -x
print "Sign different?", (x ^ y) < 0
print "Sign different?", np.less(np.bitwise_xor(x, y), 0)

    The result is shown as follows:

    Sign different? [ True  True  True  True  True  True  True  True  True False  True  True
  True  True  True  True  True  True]
Sign different? [ True  True  True  True  True  True  True  True  True False  True  True
  True  True  True  True  True  True]

    As expected, all the signs differ, except for zero.

  2. A power of two is represented by a 1, followed by a series of trailing zeroes in binary notation. For instance, 10, 100, or 1000. A number one less than a power of two would be represented by a row of ones in binary. For instance, 11, 111, or 1111 (or 3, 7, and 15, in the decimal system). Now, if we bitwise the AND operator a power of two, and the integer that is one less than that, then we should get 0. The NumPy counterpart of & is bitwise_and; the counterpart of == is the equal universal function.
    print "Power of 2?
", x, "
", (x & (x - 1)) == 0
print "Power of 2?
", x, "
", np.equal(np.bitwise_and(x,  (x - 1)), 0)

    The result is shown as follows:

    Power of 2?
[-9 -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8] 
[False False False False False False False False False  True  True  True
 False  True False False False  True]
Power of 2?
[-9 -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8] 
[False False False False False False False False False  True  True  True
 False  True False False False  True]
  3. The trick of computing the modulus of four actually works when taking the modulus of integers that are a power of two, such as, 4, 8, 16, and likewise. A bitwise left shift leads to doubling of values. We saw in the previous step that subtracting one from a power of two leads to a number in binary notation that has a row of ones, such as, 11, 111, or 1111. This basically gives us a mask. Bitwise-ANDing with such a number gives you the remainder with a power of two. The NumPy equivalent of << is the left_shift universal function.
    print "Modulus 4
", x, "
", x & ((1 << 2) - 1)
print "Modulus 4
", x, "
", np.bitwise_and(x, np.left_shift(1, 2) - 1)

    The result is shown as follows:

    Modulus 4
[-9 -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8] 
[3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0]
Modulus 4
[-9 -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8] 
[3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0]

What just happened?

We covered three bit-twiddling hacks—checking whether the signs of integers are different, checking whether a number is a power of two, and calculating the modulus of a number that is a power of two. We saw the NumPy counterparts of the operators ^, &, <<, and < (see bittwidling.py):

import numpy as np

x = np.arange(-9, 9)
y = -x
print "Sign different?", (x ^ y) < 0
print "Sign different?", np.less(np.bitwise_xor(x, y), 0)
print "Power of 2?
", x, "
", (x & (x - 1)) == 0
print "Power of 2?
", x, "
", np.equal(np.bitwise_and(x,  (x - 1)), 0)
print "Modulus 4
", x, "
", x & ((1 << 2) - 1)
print "Modulus 4
", x, "
", np.bitwise_and(x, np.left_shift(1, 2) - 1)
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset