Showing posts with label Hammingweight. Show all posts
How to find hamming weight in java
May 08, 2024
Hammingweight
Table of Content
How to find hamming weight in Java
hamming weight for a number is the count of bits that are non zero. For instance for 1001 hamming weight is 2. For 100001111 hamming weight is 5. In this article we will see how to find hamming weight efficiently.
Using Simple divide and reminder
Here we are divide the number by 2 and until it becomes 0 and each step we check if the intermediate gives reminder 1 while dividing by 2.
public static int hammingWeight(int n) {
int count = 0;
while (n != 0) {
if (n % 2 == 1) {
count++;
}
n = n / 2;
}
return count;
}Using Bit marking
In this example we are using Bit masking. Since the input is an Integer and it contains 32 bits. We do a & (bit wise and) operation for each of its digits.
public static int hammingWeightII(int n) {
int count = 0;
int mask = 1;
for (int i = 0; i <= 31; i++) {
count += (n & mask) == 0 ? 0 : 1;
//expand the mask
mask = mask << 1;
}
return count;
}Full Example
package ic.binary;
public class NumberOf1s {
public static void main(String[] args) {
int n = 5;
System.out.println("Number of 1 bits for :" + n + " -> " + NumberOf1s.hammingWeight(n));
System.out.println("Number of 1 bits for :" + n + " -> " + NumberOf1s.hammingWeight(n));
n = 8;
System.out.println("Number of 1 bits for :" + n + " -> " + NumberOf1s.hammingWeight(n));
System.out.println("Number of 1 bits for :" + n + " -> " + NumberOf1s.hammingWeight(n));
}
public static int hammingWeight(int n) {
int count = 0;
while (n != 0) {
if (n % 2 == 1) {
count++;
}
n = n / 2;
}
return count;
}
public static int hammingWeightII(int n) {
int count = 0;
int mask = 1;
for (int i = 0; i <= 31; i++) {
count += (n & mask) == 0 ? 0 : 1;
mask = mask << 1;
}
return count;
}
}
Output of above program
Number of 1 bits for :5 -> 2 Number of 1 bits for :5 -> 2 Number of 1 bits for :8 -> 1 Number of 1 bits for :8 -> 1</
