[LC Walkthrough] 191. Number of 1 Bits

Hello world! This is the second article of LeetCode Walkthrough where I record my thinking process to the solution to LeetCode problems.

Today, I will be writing about 191. Number of 1 Bits. This is very first question of February LeetCoding Challenge 2021. A problem that challenges us to count number of 1 bits of a binary number on February 1st; interesting problem choice by LeetCode.

For this problem, we are asked to write a function that takes an unsigned integer and returns the number of ‘1’ bits it has. Since Java doesn’t have unsigned integer type, we are allowed to assume that input will be given as signed integer type.

If you are aware of

Integer.toBinaryString(int i) 

this problem becomes dead simple; just get the binary string using such method and count the number of 1s. This is the initial approach I took.

This solution did the trick.

I was thinking if there were any other ways to tackle the problem. Then I realized I could also solve this problem with bit operations. We can declare a variable to use as a bitmask and perform bitwise AND operation to see if a certain bit is 1 or not. After each iteration, we will shift the mask to the left to check higher bits.

Note that the for-loop only needs to run 32 times as Java’s int type can only hold up to 32-bit

Let us run a test case. Consider a case where n = 11:

The bit-operation approach also passed the solution check.

Since we are bound by the 32-bit limitation, the time complexity of both solution will be O(1). The for-loops used in both algorithm will at most iterate for 32 times at max.

The space complexity of both solution will be O(1) as well, since the string will have length of 32 at max (for binary string approach) and we only use variables of constant sizes (for bit-operation approach).

Thanks for reading!