Number of 1’s in bit representation of a number

Objective: Write an algorithm to count the number of 1’s in the bit representation in given number.

Example:

Number: 6
Output: 2 ( 1 1 0)

Number: 11
Output: 3 ( 1 0 1 1)

Approach:
Method 1:

While number > 0
Keep doing the number & 1, increment count if result is 1
Do the right shift

Method 2:

While number > 0
Keep doing the number MOD 2, increment count if result is 1
Divide the number by 2.

Method 3: Brian Kernighan’s Algorithm

While number > 0
Increment the count.
Keep doing the number & number –1.

Example:

n = 6
count = 1
Bit representation: 1 1 0
n-1 = 5 => 1 0 1
n = n & n-1 => 1 1 0 & 1 0 1 => 1 0 0
Now n = 4
Count = 2
Bit representation: 1 0 0
n-1 = 3
n = n & n-1 => 1 0 0 & 0 1 1 => 0

Complete Code:

	public class CountOnesInNumber {

	//Method 1
	public static void count_method1(int number){
	int one = 1;
	int count = 0;
	int n = number;
	while(number>0){
	count = count + (number & 1);
	int x = number & 1;
	number >>= 1;
	}
	System.out.println("Number of 1's in the binary representation of " + n + " is: " + count);
	}

	//Method 2
	public static void count_method2(int number){
	int count = 0;
	int n = number;
	while(number>0){
	if(number%2==1)
	count++;
	number=number/2;
	}
	System.out.println("Number of 1's in the binary representation of " + n + " is: " + count);
	}

	//Method 3
	public static void count_method3(int number){
	//subtract 1 from the number
	//this will turn off the right most bit of the number, keep track of the count
	int count = 0;
	int n = number;
	while(number>0){
	count++;
	number = number & number–1;
	}
	System.out.println("Number of 1's in the binary representation of " + n + " is: " + count);
	}

	public static void main(String[] args) {
	int number = 6;
	count_method1(number);
	count_method2(number);
	count_method3(number);
	}
	}

view raw

CountOnesInNumber.java

hosted with ❤ by GitHub

Output:

Number of 1's in the binary representation of 6 is: 2

Number of 1’s in bit representation of a number

Related Posts:

Leave a Comment Cancel reply