Basic Bits hacks in Python

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

As a Developer we all want to accomplish a task in the least complexity and time. Bits are proved to be very helpful to achieve it to their operations on integer. There are several time saving methods we are going to discuss that you can adopt to boost the performance on the task.

We have covered the following bit hacks:

  • Compute sign of an integer
  • Detect if two integer have opposite signs
  • Swapping two integer values without third variable
  • Determine if an integer is a power of 2
  • Negate a Integer value
  • Check if the integer is Odd or Even
  • To get the Larger (max) or Smaller (min) of two integers without branching

As we all know that bitwise operations are &, |, ~, ^, <<, >> and they does operations on the bits of the number. They takes integer as an input and operates on the bit representation of the integer.

First of all below is the overview of some basic concept of Bitwise operations in Python before moving on how we can use these bits to get the most out of the bitwise operation.

Overview of Basic Concepts of Bits

  • Binary representation in Python

bin() function is used to get binary values of a number. Similarly int() can be used to convert back to decimal.

>>> bin(6)
'0b110' 

  • Bitwise AND (&)

It takes two values and does a "bitwise AND". Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it's 0.

    x = 14      1110(in binary)
    y = 6       0110(in binary)
>>> x & y
    6           0110(in binary)

  • Bitwise OR (|)

It takes two values and does a "bitwise OR". Each bit of the output is 0 if the corresponding bit of x AND of y is 0, otherwise it's 1.

    x = 14      1110(in binary)
    y = 6       0110(in binary)
>>> x | y
    14          1110(in binary)

  • Bitwise XOR (^)

It takes two values and does a "bitwise XOR". Each bit of the output is 1 if only one of the inputs is 1, else it's 0.

    x = 14      1110(in binary)
    y = 6       0110(in binary)
>>> x ^ y
    8           1000(in binary)

  • Bitwise 1's complement (~)

Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1.
Since python integers are signed, the negative numbers are stored through a mechanism called 2's complement format.

    x = 14      1110(in binary)
>>> ~x
    -15         -1111(in binary)

  • Bitwise left-shift (<<)

Returns x with the bits shifted to the left by y places.

    x = 5      0101(in binary)
    y = 2
>>> x << y
    20        10100(in binary)

  • Bitwise right-shift (<<)

Returns x with the bits shifted to the right by y places.

    x = 5      0110(in binary)
    y = 2
>>> x >> y
    1        0001(in binary)

Twirling hacks using bits

From the above, you should get the basic working of the Bitwise working of the integer. Now, lets twirl these bits knowledge to enhance the functionality of the bits.

  • Compute sign of an integer

It will compute the sign of the integer whether it is negative or positive integer. Sign will output -1 for negative integer, 0 , or +1 for positive value.

    v = -20

>>> sign = (v > 0) - (v < 0)
>>> print(sign)

   -1     # as -20 is negative

  • Detect if two integer have opposite signs

We will use XOR to get the bits of the number and check if it is less than 0 or not. Decimal output of the XOR is then compared to 0. Output will be 'True' if both integers have opposite signs, else 'False'.

    x = -7      -0111
    y = 2        0010
        x ^ y = -0101 = -5(in decimal)

>>> sign = ((x ^ y) < 0)
>>> print(sign)

    'True'

  • Swapping two integer values without third variable

Generally, people use a third variable to swap two integer values which can be expensive. Values can be swapped using the OR operator.

    a = 4        0100
    b = 11       1011
>>> a = a ^ b    a = 1111
>>> b = b ^ a    b = 0100 (4 in decimal)
>>> a = a ^ b    a = 1011 (11 in decimal)
>>> print('a= ', a)
>>> print('b= ', b)

    a= 11
    b= 4

  • Determine if an integer is a power of 2.

We can check if an integer is a power of two. For example, 16 can be represented as 2^4 and 12 cannot be represented as a power of 2.

    v = 16      10000(in binary)
>>> res = (v & (v - 1)) == 0
    True
    
    v = 12      1100(in binary)
>>> res = (v & (v - 1)) == 0
    
    False

In the above example, it will apply the AND operation on 16 and 15, and if there AND operation give 0 then the integer is the power of 2.

  • Negate a Integer value

We can also negate a integer value but we have to use a boolean variable that should be True to help in negating the integer value.

    Negate = True
    v = 3
    
>>> r = (v ^ -fNegate) + fNegate;
>>> print(r)
    
    -3

  • Check if the integer is Odd or Even

  1. A simple logic- To AND operate the integer with 1 to check if the integer is Odd or else Even.
    v = 37
>>> if(v & 1):
>>>     print(v, 'is Odd')
>>> else:
>>>     print(v, 'is Even')

    37 is Odd
  1. To use a boolean variable that is set to False and will tell if the integer is Odd or Even.
    v = 37
    flag = False

>>> while (v):
>>>     flag = not(flag)
>>>     v = v & (v - 1)

    True

As compared to 1st method, 2nd seems to be confusing but it just a matter of logic to get the work done.

  • To get the Larger (max) or Smaller (min) of two integers without branching

To calculate the larger or smaller between the two integer can be very expensive while operating on a huge number of comparison using branching. The bits operation can help to reduce the time.

To get the larger integer

    x = 2
    y = 6

>>> res = x ^ ((x ^ y) & ~(x < y))
>>> print("Larger is: ", res)
    
    Larger is: 6

It works as if x<y, then ~(x<y) will be all ones, so r = x ^ (x ^ y) & ~0 = x ^ x ^ y = y (as y=6 is greater than x=2). Otherwise if x>=y, then ~(x < y) will be all zeros, so r =x ^ ((x ^ y) & 0) = x.

To get the smaller integer

To get the minimum integer the logic is same as of maximum. The only replacement is 'y' in place of 'x'. res = y ^ ((x ^ y) & ~(x < y))

    x = 2
    y = 6

>>> res = y ^ ((x ^ y) & ~(x < y))
>>> print("Smaller is: ", res)
    
    Smaller is: 2

Question

What is the value stored in 'res' in the following expression?

x = 4, y = 7

res = x ^ (x ^ y)

7
4
0100
Error
It is like the example to find the larger element, but here we have x < y so we don't require to compute ~(x < y).

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.