Pop Count

The pop count or hamming weight of a number is the number of set bits (1s) in its binary representation. For example, the pop count of 6 (0110 in binary) is 2, since it has two 1 bits.

Pop count is used in several algorithms:

• Estimating set cardinality
• Identifying sparse vs dense bitmaps
• Measuring distance between binary strings
• Finding variation between sets

It can be calculated efficiently using bit tricks.

Example in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int popCount(int x) {
  int count = 0;
  while (x != 0) {
    count++;
    x &= (x - 1); //unset rightmost 1-bit
  }
  return count;
}

int n = 6; //0110
int popCount = popCount(n); //2

Example in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int popCount(int x) {
  int count = 0;
  while (x) {
    count += x & 1;
    x >>= 1;
  }
  return count; 
}

int n = 11; //1011 
int cnt = popCount(n); //3

Example in Python:

1
2
3
4
5
6
7
8
9

def pop_count(n):
  count = 0
  while n:
    count += n & 1
    n >>= 1
  return count

num = 14 #1110  
pop_cnt = pop_count(num) #3

In summary, the pop count of a number counts the set bits in its binary representation. It has applications in set operations, bitmaps, and binary strings.

Pop Count, also known as “Hamming Weight,” refers to the number of set bits (bits that are 1) in the binary representation of a given integer. Counting the number of set bits is a common operation in computer science and can be used in various applications like cryptography, data compression, and error detection.

Java

In Java, you can use bitwise operations to calculate the pop count.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public class Main {
  public static int popCount(int n) {
    int count = 0;
    while (n != 0) {
      count += n & 1;
      n >>>= 1;
    }
    return count;
  }

  public static void main(String[] args) {
    int num = 19;  // Binary: 10011
    int result = popCount(num);
    System.out.println("Pop Count: " + result);  // Output: Pop Count: 3
  }
}

• n & 1: Checks the least significant bit. If it’s 1, it adds to the count.
• n >>>= 1: Right-shifts the bits of n, effectively dividing it by 2.

C++

In C++, the code structure is similar to Java.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>
using namespace std;

int popCount(int n) {
  int count = 0;
  while (n) {
    count += n & 1;
    n >>= 1;
  }
  return count;
}

int main() {
  int num = 19;  // Binary: 10011
  int result = popCount(num);
  cout << "Pop Count: " << result << endl;  // Output: Pop Count: 3
}

• n & 1: Checks the least significant bit.
• n >>= 1: Right-shifts the bits.

Python

In Python, you can achieve the same using a while loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def pop_count(n):
  count = 0
  while n:
    count += n & 1
    n >>= 1
  return count

num = 19  # Binary: 10011
result = pop_count(num)
print(f"Pop Count: {result}")  # Output: Pop Count: 3

• n & 1: Checks the least significant bit.
• n >>= 1: Right-shifts the bits.

Key Takeaways

• Pop Count calculates the number of set bits in an integer.
• Bitwise operations are a fast and efficient way to calculate the pop count.
• The logic remains consistent across different programming languages like Java, C++, and Python.