Saturday, July 18, 2015

LeetCode OJ - Power of Two

Problem:

Please find the problem here.

Solution:

This expression for detecting power of two is quite famous. Let look into how it works.

Step 1: We flip all the bits

00100 -> 11011

Step 2: We add 1

11011 -> 11100

Step 3: We do a bitwise AND with the original

00100 AND 11100 -> 00100

Step 4: If it is the original number, we are done!

The key idea to the success of this expression is that the bit wise flip and plus 1 effectively flips all the bits except the least significant ones (up to the first 1, inclusive). Together with the bitwise AND we are then effectively checking if there exists exactly one 1 in the bit stream.

Be careful with 0 and negative.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/power-of-two/

#include "LEET_POWER_OF_TWO.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_POWER_OF_TWO
{
    class Solution
    {
    public:
        bool isPowerOfTwo(int n)
        {
            return (n > 0) && ((n & ((~n)+1)) == n);
        }
    };
};

using namespace _LEET_POWER_OF_TWO;

int LEET_POWER_OF_TWO()
{
    Solution solution;
    cout << (solution.isPowerOfTwo(0) == false) << endl;
    cout << (solution.isPowerOfTwo(1) == true) << endl;
    cout << (solution.isPowerOfTwo(2) == true) << endl;
    cout << (solution.isPowerOfTwo(3) == false) << endl;
    cout << (solution.isPowerOfTwo(4) == true) << endl;
    cout << (solution.isPowerOfTwo((1 << 30) + 1) == false) << endl;
    cout << (solution.isPowerOfTwo(1 << 30) == true) << endl;
    cout << (solution.isPowerOfTwo((1 << 30) - 1) == false) << endl;
    cout << (solution.isPowerOfTwo(1 << 31) == true) << endl;
    return 0;
}

No comments :

Post a Comment