Given an integer, write a function to determine if it is a power of two. This is not new, and the solution has been posted at Using a Faster Approach to Judge if a Integer is power of Two.
The solution is based on the fact that if the number if power of two, then do an logic-and operation with its minus-one will become zero.
1 2 3 4 5 6 | class Solution { public: bool isPowerOfTwo(int n) { return (n > 0) && ((n & (n - 1)) == 0); } }; |
class Solution { public: bool isPowerOfTwo(int n) { return (n > 0) && ((n & (n - 1)) == 0); } };
Now, here is a bruteforce interesting solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | class Solution { public: int arr[50] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824 }; bool isPowerOfTwo(int n) { for (int i = 0; i < 31; i++) { if (arr[i] == n) { return true; } } return false; } }; |
class Solution { public: int arr[50] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824 }; bool isPowerOfTwo(int n) { for (int i = 0; i < 31; i++) { if (arr[i] == n) { return true; } } return false; } };
and, similarly:
1 2 3 4 5 6 7 8 | class Solution { private: unordered_set<int> power2{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824}; public: bool isPowerOfTwo(int n) { return power2.find(n) != power2.end(); } }; |
class Solution { private: unordered_set<int> power2{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824}; public: bool isPowerOfTwo(int n) { return power2.find(n) != power2.end(); } };
Or just the pure comparisons:
1 2 3 | bool isPowerOfTwo(int n) { return n==1||n==2||n==4||n==8||n==16||n==32||n==64||n==128||n==256||n==512||n==1024||n==2048||n==4096||n==8192||n==16384||n==32768||n==65536||n==131072||n==262144||n==524288||n==1048576||n==2097152||n==4194304||n==8388608||n==16777216||n==33554432||n==67108864||n==134217728||n==268435456||n==536870912||n==1073741824; } |
bool isPowerOfTwo(int n) { return n==1||n==2||n==4||n==8||n==16||n==32||n==64||n==128||n==256||n==512||n==1024||n==2048||n==4096||n==8192||n==16384||n==32768||n==65536||n==131072||n==262144||n==524288||n==1048576||n==2097152||n==4194304||n==8388608||n==16777216||n==33554432||n==67108864||n==134217728||n==268435456||n==536870912||n==1073741824; }
And the following is based on recursion:
1 2 3 4 5 6 | class Solution { public: bool isPowerOfTwo(int n) { return n == 0 ? false : (n == 1 ? true : (n % 2 == 1 ? false : isPowerOfTwo(n / 2))); } }; |
class Solution { public: bool isPowerOfTwo(int n) { return n == 0 ? false : (n == 1 ? true : (n % 2 == 1 ? false : isPowerOfTwo(n / 2))); } };
Do you have other fun solutions? Share below!
See also: Teaching Kids Programming – Algorithms of Power of Two and Check Integer is the Power of Two
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
371 wordsloading...
Last Post: Retrieving BIOS Information using VBScript
Next Post: 32-bit Visual Studio and Delphi 2007/XE8 Eat Memory (any 64-bit IDE)?
log(2^x) = log(n)
x*log(2) = log(n)
x = log(n) / log(2)
If x is Integer then n is a power of two, otherwise not.
wouldn’t an ordered set be faster than an unordered one.
i.e. order log2N rather than N/2