**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:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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); | |

} | |

} |

**Output**:

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