Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1513
Question Name: Number Of One In Binary
Question Description: Give an integer, check how many 1(s) are there in its binary form.
Input: may contains multiple test cases. The first line indicates how many test cases are there in the following input. Each of the next lines contains one integer as a test case.
Output: the number of 1(s) for each test case.
1 2 3 4 5 6 7 8 9 | Input: 3 4 5 -1 Output: 1 2 32 |
The challenge should appear in the Elements of Programming Interviews: The Insiders’ Guide. The book is on the way to me. So I cannot make sure.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | /** * Filename : NumberOf1InBinary.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-02 * JDK used : 1.7 * Change log: None */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class NumberOf1InBinary { /** * @param num: to check how many 1s are there in binary form of num. * @return int: the number of 1s. */ public int numberOf1InBinary(int num) { int count = 0; while(num != 0) { ++count; // num & (num-1) will change the last bit, whose value is 1, to 0. num = num & (num-1); } return count; } public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); NumberOf1InBinary oneCounter = new NumberOf1InBinary(); // Get the first integer, which says how many integers are there in the // following input. st.nextToken(); int totalTests = (int) st.nval; while (totalTests > 0 && st.nextToken() != StreamTokenizer.TT_EOF) { System.out.println(oneCounter.numberOf1InBinary((int)st.nval)); --totalTests; } } } |