Power of 2
Lesson 9 of 17 in Coddy's Bit Manipulation course.
If you've played enough with binary numbers then until now you must have realized that all the power of 2 only include 1 set bit ( set bit refers to '1' ). For example- (2)10 = (10)2 , (4)10 = (100)2 , (8)10 = (1000)2 and so on.
Here, in this lesson we are going to discuss about the problem-
Find whether a given number is a power of 2 or not using bit manipulation.
Okay! So how will the above observation help us? Let's find out.
- Let's say (8)10 is given to us and we know it is a power of 2.
- On subtracting 1 from it we get (7)10 which is equivalent to (0111)2.
- If we perform AND ( & ) operation on 7 and 8, we get a 0.
- Interesting right? Let's check for another number which is also a power of 2. Take (32)10 which is equivalent to (100000)2, and subtract 1 from it that is (31)10 = (011111)2. We get a 0 again!
- So, to generalize this, can we say for the number, let's call it x, to be a power of 2, ( x & (x-1) ) will always be '0'?
And using this observation we can easily solve the question without having to use any math library and it's power function, nor do we have to use any loop, we just solved in O(1) time complexity! Isn't that cool? That's how bit manipulations can help us optimize our programs to a good level and also makes the code less complicated.
Challenge
EasyGiven a number, determine whether it is even or not using bit manipulation.
Try it yourself
#include <iostream>
using namespace std;
bool IsPowerOf2(int num) {
// Write code here
}All lessons in Bit Manipulation
2Bit Algorithms
Power of 2Number occurring odd times Number of set-bits Rotate bits of a number IRotate bits of a number II