Skip to main content

Count valid unset bits in numbers from 1 to n in java

Java program for Count valid unset bits in numbers from 1 to n. Here mentioned other language solution.

/*
   Java program for
   Count valid unset bits in all numbers from 1 to n
*/
public class BitCount
{
	// Returns number of set bits of given number
	public int countSetBit(int num)
	{
		int x = num;
		x = x - ((x >>> 1) & 1431655765);
		x = (x & 858993459) + ((x >>> 2) & 858993459);
		x = (x + (x >>> 4)) & 252645135;
		x = x + (x >>> 8);
		x = x + (x >>> 16);
		x = x & 63;
		// Number of set bit
		return x;
	}
	// Handles the request of count the all 
	// unset bits from (1 to n)
	public void countUnsetBit(int n)
	{
		int result = 0;
		// Execute loop from 1 to n
		for (int i = 1; i <= n; ++i)
		{
			// Total bits - Active bits
			result += ((int)(Math.log(i) / Math.log(2.0) + 1.0)) - 
              countSetBit(i);
		}
		// Display result
		System.out.println(" Unset bits from (1 to " + n 
                           + ") : " + result);
	}
	public static void main(String[] args)
	{
		BitCount task = new BitCount();
		// Test A
		// number(1-7)  Un-setbit
		// ----------------
		// 1  = 1         0
		// 2  = 10        1
		// 3  = 11        0   
		// 4  = 100       2
		// 5  = 101       1
		// 6  = 110       1 
		// 7  = 111       0
		// --------------------
		//                5
		task.countUnsetBit(7);
		// Test B
		// number(1-10)  Setbit
		// ----------------
		// 1  = 1         0
		// 2  = 10        1
		// 3  = 11        0   
		// 4  = 100       2
		// 5  = 101       1
		// 6  = 110       1 
		// 7  = 111       0
		// 8  = 1000      3
		// 9  = 1001      2 
		// 10  = 1010     2 
		// --------------------
		//                12
		task.countUnsetBit(10);
	}
}

Output

 Unset bits from (1 to 7) : 5
 Unset bits from (1 to 10) : 12

This Java program is designed to count the number of valid unset bits in all numbers from 1 to n, where n is a positive integer provided by the user.

The program contains two methods: countSetBit and countUnsetBit.

The countSetBit method takes an integer as input and returns the number of set bits (bits with a value of 1) in the binary representation of that number. It uses a bit manipulation technique to count the set bits.

The countUnsetBit method takes an integer n as input and loops from 1 to n to count the number of valid unset bits in all the numbers from 1 to n. For each number i, it first calculates the total number of bits in its binary representation using the formula log2(i) + 1, and then subtracts the number of set bits in i, which is obtained by calling the countSetBit method. The final result is the sum of all such differences.

The program also includes two test cases, test A and test B, where the expected results are manually calculated for the given input ranges.

Overall, the program is a correct implementation to count the number of valid unset bits in all numbers from 1 to n. However, it can be improved in terms of performance, especially for large values of n, by using more efficient algorithms to count the set bits and to calculate the logarithm.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment