On this post, we will look into how to use “Bitwise Operators” to manipulate bits of a number. Bit manipulation is a useful tool that can sometimes perform complicated tasks in a \simple manner.

We will work on integer values and assume each number has $32$ bits in them. If a number has only $0$ or $1$ as its digit, then assume that it is in binary form. All position of bits is $0$ indexed.

Since binary values can only be $0$ or $1$, we sometimes refer them like light bulbs. A bit being “Off” means it has value $0$ and being “On” means it has value $1$. Bit $1$ is also referred as “Set” and bit $0$ as “Reset”.

We need to have a strong grasp of how AND, OR, Negation, XOR and Shift Operators work to understand how bit manipulation works. If you have forgotten about them, then make sure you revise.

Checking Bit at Position X

Given a number $N$, find the value of its bit at position $X$. For example, if $N=12=(1100)_2$ and $X=2$, then value of bit is $1$.

So how do we find it? We can find this value in three steps:

1. Let, $mask = 1 << X$
2. Let, $res = N \ \& \ mask$
3. If $res$ is $0$, then bit is $0$ at that position, else bit is $1$.

Let us see it in action with the example above, $N = 12$ and $X = 2$.

$1100$
$\underline{0100} \&$ ( $1 << 2$ is just $1$ shifted to left twice )
$0100$

Now, what happened here? In step $1$, when we left shifted $1$ $X$ times, we created a number $mask$ which has bit $1$ only at position $X$. This is a useful application of left shift operator. Using this, we can move $1$ bit anywhere we want.

Next, at step $2$, we find the result of performing AND operator between $N$ and $mask$. Since $mask$ has $0$ in all positions except $X$, the result will have $0$ in all places other than $X$. That’s because performing AND with $0$ will always give $0$. Now, what about position $X$. Will the result at position $X$ have $0$ too? That depends on the bit of $N$ at position $X$. Since, the $X$ bit in the mask is $1$, the only way result will have $0$ at that position if $N$ has $0$ in that position.

So, when all position of $res$ is $0$, that is $res$ has value $0$, we can say that $N$ has $0$ bit in position $X$, otherwise it doesn’t.

Set Bit at Position $X$

Given a value $N$, turn the bit at position $X$ of $N$ to $1$. For example, $N=12=1100$ and $X=0$, then $N$ will become $13=1101$.

This can be done in two steps:

1. Let, $mask = 1 << X$
2. $N = N \ | \ mask$

$1100$
$\underline{0001} \ |$
$1101$

In step $1$, we shift a $1$ bit to position $X$. Then we perform OR between $N$ and $mask$. Since $mask$ has 0 in all places except $X$, in the result, all those places remain unchanged. But $mask$ has $1$ in position $X$, so in result position $X$ will be $1$.

Reset Bit at Position $X$

Given a value $N$, turn the bit at position $X$ of $N$ to $0$. For example, $N=12=1100$ and $X=3$, then $N$ will become $4=0100$.

This cane be done in three steps:

1. Let, $mask = 1 << X$
2. $mask = \sim mask$
3. $N = N \ \& \ mask$

$1100$
$\underline{0111} \ \&$ ( We first got $1000$ from step $1$. Then used negation from step 2.)
$0100$

In step $1$ we move $1$ bit to position $X$. This gives us a number of $1$ in position $X$ and $0$ in all other places. Next, we negate the $mask$. This flips all bits of $mask$. So now we have $0$ in position $X$ and $1$ in all other places. Now when we perform AND between $mask$ and $N$, it forces the bit at the $X$ position to $0$ and all other bits stay intact.

Toggle Bit at Position X

Given a value $N$, toggle the bit at position $X$, i.e if the bit at $X$ is $0$ then make it $1$ and if it is already $1$, make it $0$.

This can be done in two steps:

1. Let, $mask = 1 << X$
2. $N = N \ \wedge \ mask$

First, we shift bit $1$ to our desired position $X$ in step $1$. When XOR is performed between a bit and $0$, the bit remains unchanged. But when XOR performed between a bit and $1$, it toggles. So all position except $X$ toggles during step 2, since all position in mask except $X$ is $0$.

Coding Tips

When coding these in C++, make sure you use lots of brackets. Bitwise operators have lower precedence than $==$ and $!=$ operator which often causes trouble. See here.

What would be the output of this code:

if ( 0 & 6 != 7 ) printf ( "True\n" );
else printf ( "False\n" );

You might expect things to follow this order: $0 \ \& \ 6 = 0$ and $0 \ \neq 7$, so “True” will be output. But due to precedence of operators, the output comes out “False”. First $6 \ != 7$ is checked. This is true, so $1$ is returned. Next $0 \ \& \ 1$ is performed which is $0$.

The best way to avoid these kind of mishaps is to use brackets whenever you are using bitwise operators. The correct way to write the code above is:

if ( (0 & 6) != 7 ) printf ( "True\n" );
else printf ( "False\n" );

This prints “True” which is our desired result.

Conclusion

These are the basics of bit manipulation and by no means the end of it. There are lots of other tricks that are yet to be seen, such as “Check Odd or Even”, “Check Power of Two”, “Right Most Bit”. We will look into them some other day.

Reference

1. forthright48 – Bitwise Operators
2. CPPReference – C++ Operator Precedence

• Category: CPPS