How to check if all bits are set in a number

Problem statement

Check if a number has all bits set in its binary representation.

Example 1

  • Input: n=5
  • Output: No

Example 2:

  • Input: n=7
  • Output: Yes

Solution

The base or corner case here is n, which is zero. There are no bits set.

The trick here is if all the bits of the input number are set, then adding one to it will make it a perfect square of 2. So, the following expression will check if the n has all bits set or not.

(n & (n+1)) == 0
n n + 1 (n & (n+1)) All bits set?
5 (101) 6 (110) 100 No
7 (111) 8 (1000) 0000 Yes
  • Time complexity: O(1)
  • Space complexity: O(1)

Code

Let's view the code.

class Main{
    static boolean isAllBitsSet(int n){
        return (n & (n + 1)) == 0;
    }
    public static void main (String[] args) {
        int n = 16;
        System.out.println("Are all bits set in " + n + "? " + isAllBitsSet(n));
    }
}

Explanation

  • Lines 3–5: We write a boolean function, static boolean. It returns true or false according to the bit calculating formula discussed above.
  • Line 9: We display the output of the result corresponding to the number n.

Note: The value of n can be changed to any value and tested.

New on Educative
Learn to Code
Learn any Language as a beginner
Develop a human edge in an AI powered world and learn to code with AI from our beginner friendly catalog
🏆 Leaderboard
Daily Coding Challenge
Solve a new coding challenge every day and climb the leaderboard

Free Resources

License: Creative Commons-Attribution NonCommercial-ShareAlike 4.0 (CC-BY-NC-SA 4.0)