In this post we will solve the LeetCode 191 Number of 1 Bits problem using the Java programming language.
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). Note: Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3. Constraints: o The input must be a binary string of length 32.
The requirements call to develop a function that takes as an argument an unsigned integer and returns the number of bits set to 1. Note that the integers have 32-bits.
As mentioned, we will be solving the problem using the Java programming language and the VSCode IDE on a Windows computer. Java is quite portable and the solution should work on most (never generalize) platforms.
Please check the current description of the problem at the LeetCode site. Some requirements may change with time.
public int hammingWeight(int n) {
}
The signature of the function of interest expects as a single argument an integer `n` and should return the number of bits set to 1.
00000000000000000000000000001011 main <<< s ==>00000000000000000000000000001011<== main <<< n: 11 main <<< output: 3 00000000000000000000000010000000 main <<< s ==>00000000000000000000000010000000<== main <<< n: 128 main <<< output: 1 11111111111111111111111111111101 main <<< s ==>11111111111111111111111111111101<== main <<< n: -3 main <<< output: 31
We have the same set of test cases provided by LeetCode.
The first line in each test case is the input line expressed as a series of 0s and 1s. This is not what we find in the input argument. I guess the arguments are in a binary representation, but the actual value passed to the function of interest is the integer representation.
Since I developed the solution on my Windows computer, I had to implement a test scaffold which would read the input line, convert it to an integer in the `n` variable, call the function of interest, and display the output. Please note that the test code IS NOT PART OF THE SOLUTION!
/**
* Test scaffold
*
* !!! NOT PART OF THE SOLUTION !!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the input line ****
String s = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
// **** convert to integer ****
int n = Integer.parseUnsignedInt(s, 2);
// ???? ????
System.out.println("main <<< n: " + n);
// **** call the function of interest and display output ****
System.out.println("main <<< output: " + hammingWeight(n));
}
Our test code reads the input string of 0s and 1s. It parses the line and populates the `n` int variable which will be used to pass as an argument to the function of interest.
The function of interest is then called and the returned value is displayed as the output.
/**
* Given an unsigned integer return the number of '1' bits it has.
*
* 601 / 601 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 36.1 MB
*/
static public int hammingWeight(int n) {
// **** initialization ****
int cnt = 0;
// **** traverse the binary representation of n - O(32) ****
for (int i = 0; i < 32; i++) {
// **** increment counter (if needed) ****
if ((n & 1) == 1) cnt++;
// **** shift n right ****
n >>= 1;
}
// **** return count of 1s ****
return cnt;
}
The function of interest initializes a counter. A loop is called which will move to the least significant position the bit in the ith location in `n`. If the bit is set to 1 the counter is incremented. The variable `n` is then shifted right once.
When the loop completes, the count of 1s is returned.
We could also have kept `n` and declare the flag variable initialized to 1 and then shift it left per loop.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named NumberOf1Bits.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John