We will now cover three tricks—checking whether the signs of integers are different, checking whether a number is a power of 2, and calculating the modulus of a number that is a power of 2. We will show an operators-only notation and one using the corresponding NumPy functions:
- The first trick depends on the
XORor^operator. TheXORoperator is also called the inequality operator; so, if the sign bit of the two operands is different, theXORoperation will lead to a negative number (see https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-bitwise-operation).The following truth table illustrates the
XORoperator:Input 1
Input 2
XOR
True
True
False
False
True
True
True
False
True
False
False
False
The
^operator corresponds to thebitwise_xor()function, and the<operator corresponds to theless()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.
- A power of
2is represented by a1, followed by a series of trailing zeroes in binary notation. For instance,10,100, or1000. A number one less than a power of2will be represented by a row of ones in binary. For instance,11,111, or1111(or3,7, and15in the decimal system). Now, if we bitwiseANDa power of2, and the integer that is one less than that, then we should get0.The truth table for the
ANDoperator looks like the following:Input 1
Input 2
AND
True
True
True
False
True
False
True
False
False
False
False
False
The NumPy counterpart of
&isbitwise_and(), and the counterpart of==is theequal()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]
- The trick of computing the modulus of 4 actually works when taking the modulus of integers that are a power of
2such as4,8,16, and so on. A bitwise left shift leads to doubling of values (see https://wiki.python.org/moin/BitwiseOperators). We saw in the previous step that subtracting one from a power of2leads to a number in binary notation that has a row of ones such as11,111, or1111. This basically gives us a mask. Bitwise-ANDing with such a number gives you the remainder with a power of2. The NumPy equivalent of<<is theleft_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]
We covered three bit twiddling hacks—checking whether the signs of integers are different, checking whether a number is a power of 2, and calculating the modulus of a number that is a power of 2. We saw the NumPy counterparts of the operators ^, &, <<, and < (see bittwidling.py):
from __future__ import print_function
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))