Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

    • Check if a number is a power of 2 with a single bitwise operation

    Given a positive integer n, you are asked to find out if it’s a power of 2. It’s possible to do that with a single bitwise operation. If we consider the bitwise representation of a number that’s a power of 2, then it has a single 1 in the representation and the rest are 0s.
    2^n number
    Binary representation
    8
    1000
    32
    100000
    128
    10000000
    Random Number
    Binary representation
    7
    111
    67
    1000011
    144
    10010000
    This can be seen from the definition of binary representation. Every position with a 1 corresponds to the addition of that power of 2 (67 = 1 + 2 + 0 + 0 + 0 + 0 + 64, 8 = 0 + 0 + 0 + 8). So, having a single 1 in the binary representation of a number means that there are no other powers of 2 in the sum other than that one. So, the problem becomes checking if there is only a single 1 in the binary representation of n.
    An easy way of doing that is by doing a bitwise & of n and n-1. If the result is 0 ⇒ it’s a power of 2.
    For any number that’s not a power of 2, the result of n & (n-1) will be different from 0:
    • 7 & 6 = 111 & 110 = 110 (6)
    • 67 & 66 = 1000011 & 1000010 = 1000010 (66)
    • 144 & 143 = 10010000 & 10001111 = 10000000 (128)
    Yet, for the powers of 2, it’s always 0:
    • 8 & 7 = 1000 & 111 = 0
    • 32 & 31 = 100000 & 11111 = 0
    • 128 & 127 = 10000000 & 1111111 = 0
    💡
    Intuition When considering the numbers n and n-1, the most significant bit of those two is preserved only when the binary representation of n has other 1s other than the most significant bit. If n is a power of 2 ⇒ the binary representation has only a single 1, and thus when subtracting 1, n-1 loses the most significant bit (it becomes 0 and the rest of the bits turn to 1). For other numbers (6, 67, 144, etc.) their binary representations contain several 1s. Therefore, when subtracting 1 from them, they don’t lose their most significant bits.

    Input

    The first line of the input contains a single integer n (2 ≤ n ≤ ).

    Output

    The program should print Yes if n is a power of 2 and No otherwise.

    Examples

    Input
    Output
    8
    Yes
    17
    No
    2048
    Yes
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue