Topic describes

This is a power of 231. 2 in LeetCode, and the difficulty is easy.

Tag: Math, bit operation

Given an integer n, determine whether the integer is a power of 2. If so, return true; Otherwise, return false.

If there is an integer x such that n == 2×2^x2x, then n is considered to be a power of 2.

Example 1:

Input: n = 1 Output: true Description: 20 = 1Copy the code

Example 2:

Input: n = 16 Output: true Description: 24 = 16Copy the code

Example 3:

Input: n = 3 Output: falseCopy the code

Example 4:

Input: n = 4 Output: trueCopy the code

Example 5:

Input: n = 5 Output: falseCopy the code

Tip:

  • –
    2 31 2^{31}     <= n <=
    2 31 2^{31}     – 1

Advancements: Can you solve this problem without loops/recursion?

Simple approach

First of all, the numbers less than or equal to 000 must not be, and 111 must be.

After processing these boundaries, try to divide NNN clean. if the remaining number is 111, it starts with a power of 222.

Code:

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n % 2= =0) n /= 2;
        return n == 1; }}Copy the code
  • Time complexity: O(log⁡n)O(\log{n})O(logn)
  • Space complexity: O(1)O(1)O(1)

lowbit

For those of you familiar with tree arrays, lowbit is a quick way to get the lowest value of 1 in the binary representation of x.

If a number NNN is a power of 222, then it has the property that lowbit(n) = n (the binary representation of the power of 222 must have the highest bit 111 and the lowest bit 000).

Code;

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0&& (n & -n) == n; }}Copy the code
  • Time complexity: O(1)O(1)O(1)
  • Space complexity: O(1)O(1)O(1)

The last

This is No.231 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.