## Power of Two

Given an integer, write a function to determine if it is a power of two.### Analysis:

An straightforward way is to keep doing "divide by 2" for the number and check if current number "mod 2" is zero. However this is pretty slow (it still can pass the OJ).More efficient way is to use bit manipulation.

If one number is a power of 2, then its binary must starts with 1 and all the lower bits are 0. e.g.,

2 10

4 100

8 1000

16 10000

...

Also, we have to find a "mask" to check this format, what "mask" should we use?

Let's see some examples:

1 01

3 011

7 0111

15 01111

...

Well, it is not hard to see that, if one number "n" is a power of 2, then "n-1" must have all 1s in its binary format. Therefore,

*"n & n-1" must be 0.*### Code(C++):

class Solution { public: bool isPowerOfTwo(int n) { return ( (n>0) && (n & (n-1))==0 ) || (n==1); } };

### Code(Python):

aclass Solution(object): def isPowerOfTwo(self, n): """ :type n: int :rtype: bool """ return n>0 and n & (n-1)==0 or n==1

Thank You for posting it!

ReplyDelete123 hp oj5746 printer support

Or can we take log base 2 of n, if ans is integer, that means it's power of 2.

ReplyDeleteOr can we take log base 2 of n, if ans is integer, that means it's power of 2.

ReplyDeleteVery nice and informative post

ReplyDelete123 HP Officejet 4650

Hi, I am really exiting while reading your blog. It is very informative and easy to understand for all level skilled users.

ReplyDeleteFree Technical Support for HP Printers

very interesting , good job and thanks for sharing such a good blog.

ReplyDelete123.hp.com/setup

I am really happy to say it’s an interesting post to read . I learned w information from your article , you are doing a great job . Thanks for a information

ReplyDelete123.hp.com/setup 4625

Excellent post, thanks for this resource!

ReplyDelete123 hp setup

Really its very useful information that you have shared and thanks for sharing the information with us.

ReplyDeleteHp Officejet 5746 Troubleshooting

Very interesting,good job and thanks for sharing such a good

ReplyDeleteblog.your article is so convincing that I never stop myself to say

something about it.You’re doing a great job.Keep it up.

123 hp setup

I am looking for some good blog sites for studying. I was searching over search engines and found your blog site. Well i like your high quality blog site design plus your posting abilities. Keep doing it.

ReplyDelete123 HP COM SETUP