How to find hamming weight in java

May 08, 2024 | No comments

How to find Hamming Weight in Java

Hamming weight of a number is the count of bits that are set to 1. For instance:
  • 1001 → Hamming weight = 2
  • 100001111 → Hamming weight = 5
In this article we will see how to calculate Hamming weight efficiently.

Using Simple Division and Remainder

Here we divide the number by 2 repeatedly until it becomes 0. At each step, we check if the remainder is 1 (i.e., the least significant bit is set). 
public static int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        if (n % 2 == 1) {
            count++;
        }
        n = n / 2;
    }
    return count;
}

Using Bit Masking

In this example, we use bit masking. Since an int in Java has 32 bits, we shift a mask bit and check each position with a bitwise AND. 
public static int hammingWeightII(int n) {
    int count = 0;
    int mask = 1;

    for (int i = 0; i < 32; i++) {
        if ((n & mask) != 0) {
            count++;
        }
        mask = mask << 1; // shift the mask
    }
    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 + " -> " + hammingWeight(n));
    System.out.println("Number of 1 bits for " + n + " -> " + hammingWeightII(n));

    n = 8;
    System.out.println("Number of 1 bits for " + n + " -> " + hammingWeight(n));
    System.out.println("Number of 1 bits for " + n + " -> " + hammingWeightII(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 < 32; i++) {
      if ((n & mask) != 0) {
        count++;
      }
      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

No comments :

Post a Comment

Please leave your message queries or suggetions.

Note: Only a member of this blog may post a comment.