Bit Twiddling in Python – 3 – Basic hacks

After Part 1 and Part 2, let's look at a few more basic hacks.

Finding if nth bit is set or not

In the last post we found out if the LSB is set or not by AND-ing with 1. So, if x was our integer we did a x& 1. This was also the test used to find out if the number is even or odd. In this task today, we will find out if the nth bit is set. One way of finding this out is extending our old idea. We can simply do a x & (1 << n) .

If x & ( 1 << n) yields 0, we know the bit at nth position is zero. If we end up with a power of 2, the bit at nth position is 1.

Setting the nth bit

This task is almost identical to the previous one, except for the difference we are not limited to find the nth bit, but we have to set it to 1 immaterial of the previous value. This surely smells of a OR truth table. An OR with 1 changes the bit to 1 immaterial of the previous value of the bit.

Algorithm for going to the nth place is the same as before. We can go to the nth location by left-shifting n times.

This leads to the expression x | ( 1<< n)

Here is an example –

>>> bin(x)

'0b101010'

X is 42 here

>>> x = x | ( 1 << 0)

>>> x

43

>>> bin(x)

'0b101011'

Un-Setting the nth bit

This task is the inverse of the previous one. Here we need to make the nth bit zero, immaterial of the previous value. This smells of an AND.

 AND with a zero makes a bit zero, no matter what the previous values were. For going to the nth bit, we continue to use our age-old formula of left shifting by n. We can left shift 1 and then take its complement.  So, the expression becomes

X & ~(1 << n)

Let’s try this on 42 –

>>> x = 42

>>> bin(x)

'0b101010'

The lowest bit that is set is at position 1. Let’s unset that.

>>> x = x& ~(1<<1 b="">

>>> x

40

>>> bin(x)

'0b101000'

Toggling the nth bit

We saw setting and unsetting of the nth bit, let’s combine both. We want to toggle the bit. Is it necessary to know the value of a bit for toggling? A brute force way would certainly demand that and then apply one of the operations from the two above.  A more clever way would be to XOR the bit with 1.

An XOR with 1 results in 1 if the current bit value is 0 and a 0 if the bit is 1.

Moving to nth place remains the same – 1 << n

So the expression becomes

X ^ ( 1<< n)

>>> x = 42

>>> bin(x)

'0b101010'

>>> bin( x ^ (1 << 1))

'0b101000'

Lowest Set bit and lowest unset bit

The first task is about identifying the lowest set bit and turning all other bits to 0. The second task is opposite. Let’s do the first task

X & -X

>>> bin(x)

'0b101010'

>>> bin(x & -x)

'0b10'

The reason it works is pretty simple. We saw in the first post on bit twiddling that negative numbers are represented in the 2’s complement form.  In a 2’s complement form –x is the same ~x + 1

In the second task, we have to find the lowest 0 bit and make it 1, while making all others 0.  Again, we take advantage of the 2’s complement form –

(X+1) & ~X

Let x = 42, we have the lowest unset bit at the 0^th position itself.

>>> x

42

>>> bin(x)

'0b101010'

>>> bin(

... (x+1) & ~ x)

'0b1'