08 Sep 2017

First up, I have to admit that this post is a bit of disappointment for some people. I can feel ya, folks. In my defense, I really wanted to *fix* this somehow somewhere; because understanding the code at bit level can guarantee better **algorithmic thinking**.

Computer processes data only in 1’s and 0’s … bla.. bla.. you know the story, right. The point is that using binary number system, or at least understanding it, can result in more *cool* code with efficient performance. As this series is all about algorithms, let me present a bunch of cool *hacks* (if you will) that can boost the run time of your code.

- For Example
- We use built-in function for taking higher powers. Most languages have this function
`pow()`

for this. But using bit operations, you can compute higher powers much faster than the given function.

with that and more, let’s start playing with bits.

**Note:** Keep a pen/pencil and a piece of paper with you while reading this post.

Before going into any details, familiarize yourself with basic bit operations.

- Bit Operations
`&:`

performs bitwise**AND**operation

`|:`

performs bitwise**OR**operation

`~:`

inverts the bits of given numbers; bitwise**NOT**

`^:`

performs bitwise**XOR**, exclusive OR

`<<:`

left shift; shifts all the bits to the left by the given amount

`>>:`

right shift; shifts all the bits to the right by the given amount

Read more: Python Wiki

Note that the given operation is performed bitwise even if the given value is decimal or in any other system.

Numbers in binary consist of only 1’s and 0’s, sometimes it’s required to know how many 1’s or active bits the number contains. Here’s is how to do that:

```
def count( value ):
count = 0 # no. of active bits
while value: # until the number is reduced to zero
# value = value & (value - 1)
value &= value - 1
count += 1
return count
```

If you grab a pen and paper, work this out and you’ll be surprised to see how remarkable it looks in operation.

Simple function that checks if the given number is a power of two. Using normal programming approach

```
def isPowerOf2(num):
if not num:
return False
while num % 2 is 0:
num /= 2
return num==1
```

Using bit manipulation

```
def isPowerof2(num):
return (num and not (num & (num - 1)))
```

Run a paper test on this and see the difference yourself!

Given the example above; if you need to find some power of 2, using library functions can cost more time. The easy way to do it using bit operations is:

```
# i is the power of 2
1 << i
# that's it!!
```

Left and right shift can double and half the given number, respectively. As left shift moves all bits to the left, the doubled value is returned. Similarly, right shift divides the value by 2, python equivalent of `//`

operator.

**Warning:** Beware of the possible loss of data because of bit limits.

If you want to check if a particular *i*-th bit (from right) is set in a number `N`

, AND it with a binary number with only 1 at that place followed by all zeros.

```
def isSet(N, i):
if (N & ( 1 << i )):
return True
return False
```

This binary expression will always yield some arbitrary number if i-th bit is set, otherwise 0.

In contrary to the last example, if you want to *set* *i*-th bit (from right) in a number `N`

, do this:

```
def set(N, i):
return (N | (1 << i))
```

You can get the idea how small bitwise expressions can do great things. See the properties of binary numbers and come up with your own expressions (comment them and I’ll add them in this post with credit). I haven’t included any working example and I want you to do that yourself as explaining step-by-step at this level can be very hectic and I’m too laazZzzyyy to do that.

See the results in this IPython Notebook. In case of any errors, open an issue in 100 Algorithms repo OR comment below.

You may also like...

Twitter Facebook Google+