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.

Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

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