How to Answer: How many 1's can you find?
Advice and answer examples written specifically for a Java Intermediate Level Bit Manipulation job interview.
2. How many 1's can you find?
This interview question concentrates on using Java strings and manipulation.
You are given a 32-bit integer. Your task is to calculate how many 1’s are there in the binary representation of the given number.
/*Example*/
Given: 23
expected output: 4
explanation: binary representation of 23 is 10111, which has 4 bits which are 1.
Given: 9
expected output: 2
explanation: binary representation of 9 is 1001, which has 2 bits which are 1.Solution:
Approach I (using strings):
We will find the binary representation of the number in string form. This can easily be done using the Number.prototype.toString method. Number.prototype.toString takes one optional parameter- radix- an integer in the range 2 through 36 specifying the base to use for representing numeric values. n is a number here. So we will call the toString method on n passing 2 has argument because we want radix 2 (binary) representation.
Next, we will iterate over each character of the string and check if it is “1â€. If it is “1†we increase the count and then return the count after the loop.
public class Solution {
// you need to treat n as an unsigned value
public int count1Bits(int n) {
int count = 0;
String num = Integer.toBinaryString(n);
for (char character : num.toCharArray()) {
if (character == '1') count++;
}
return count;
}
}Time complexity- O(32) = O(1)
Space complexity- O(32) = O(1)
Approach II (using bit-manipulation):
We can make use of bitmasks to check if the binary representation has 1 at a particular position (0-indexed from right to left).
Let’s say we have a binary number as n = 101100.
â— We want to check position 2. To check, we will bitwise-and the number with 000100 (1 is only at position 2). We will bitwise-and it with the number n. The result will be 000100
101100
000100 (bitwise and)
000100
The result is non-zero. We will say the number n has bit 1 at position 2.
â— Now, we want to check position 4. To check, we will bitwise-and the number with 010000 (1 is only at position 4). We will bitwise-and it with the number n. The result will be 000000
101100
010000 (bitwise and)
000000
The result is zero. We will say the number n does not have bit 1 at position 2.
We will do bitwise and with all the positions one by one from 0 to 31. If the result is non-zero, we will increase the counter by 1.
NOTE- the numbers 000100 and 010000 to check the position if they are 1 or 0 are known as bitmasks.
To generate the mask for a specific position, we will use the left-shift operator. The left shift operator shifts all the bits to left by a specified number.
So if we want to shift 1, we will do 1 << i.
â— if i = 0 then 1 << 0 = 1 i.e. no shift at all
â— if i = 1 then 1 << 1 = 10 i.e. shift 1 times
â— if i = 2 then 1 << 2 = 100 i.e. shift 2 times
â— if i = 3 then 1 << 3 = 1000 i.e. shift 3 times
â— if i = 6 then 1 << 6 = 1000000 i.e. shift 6 times
public class Solution {
// you need to treat n as an unsigned value
public int count1Bits(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
int mask = 1 << i;
if ((n & mask) != 0) {
count++;
}
}
return count;
}
}Time complexity- O(32) = O(1)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021