Bitwise Operators: Given a number, check if all the bits of the number are set

Problem Statement:

Given a number, check if all the bits of the number are set

Example:

Input: 7
Output: Yes

Solution 1:

For every bit of the number in its binary form check if “n & 1 == 0”, if its true, return No, else return Yes at the end of the loop.

Time Complexity: O(b) // b is the bits in binary representation
Space Complexity: O(1)

Solution 2:

Step 1: Add 1 to n, store it as num

Step 2: num & (num – 1) == 0 then all the bits are set, else it is not set.

Reasoning:

If all the bits are set on a number, adding 1 to it will make that number a perfect power of 2.

Then we check if the number is perfect power of 2.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

string solution_1(int n)
{
    if (n == 0)
        return "No";

    while (n > 0) {
        if ((n & 1) == 0)
            return "No";
            
        n = n >> 1;
    }
    return "Yes";
}

string solution_2(int n)
{
    if (n == 0)
        return "No";

    if (((n + 1) & n) == 0)
        return "Yes";

    return "No";
}

int main()
{
    int n = 7;
    cout << solution_1(n)<<endl;
    cout << solution_2(n)<<endl;
    return 0;
}

Output

Yes
Yes