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.
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.
&: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
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
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.