Number of 1’s in bit representation of a number

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

Exam­ple:

Number: 6
Output: 2 ( 1 1 0)

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

 Approach:
Method 1:

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

Method 2:

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

Method 3: Brian Kernighan’s Algorithm

  1. While number > 0
  2. Increment the count.
  3. 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 & number1;
}
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);
}
}

Output:

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

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.