Count Monobit Integers - Solution & Explanation

Problem Overview: Count how many integers in the given range are monobit. A monobit integer has exactly one set bit (1) in its binary representation. In other words, its binary form looks like 1, 10, 100, 1000, etc.

Approach 1: Simulation with Bit Check (O(n) time, O(1) space)

The straightforward approach is to iterate through every integer in the range and check whether it contains exactly one set bit. A number has a single set bit if the expression x & (x - 1) equals zero while x > 0. This works because subtracting 1 flips the lowest set bit and all bits to its right, so the bitwise AND removes that bit entirely for powers of two.

During the scan, perform this constant‑time check for each number and increment a counter whenever the condition holds. This technique relies on a classic Bit Manipulation trick that quickly detects whether a number is a power of two. Since each integer is processed once, the runtime is linear with respect to the size of the range.

This method is simple, readable, and efficient for the typical constraints of an easy problem. The logic involves basic Enumeration: iterate through candidates and validate them using a constant‑time property of their binary form.

Why the bit trick works: Numbers with exactly one set bit are powers of two. Their binary representation contains a single 1. When you compute x & (x - 1), that single bit disappears, producing zero. Any number with multiple set bits leaves at least one bit after the operation.

Recommended for interviews: The simulation approach using x & (x - 1) is what interviewers typically expect. It shows familiarity with core bit manipulation patterns. A brute-force method that counts bits using loops also works, but the bit trick demonstrates stronger understanding and runs with the same O(n) time while keeping the code concise.