Counting bits or Hamming Weight

by

Counting bits, also known as the “Hamming Weight” or the “population count”, refers to counting the number of 1 bits in the binary representation of a number. This is a common problem in computer science, often used in various applications such as cryptography, algorithms, and network address calculation.

In Kotlin, you can solve the counting bits problem using a straightforward approach that checks each bit of the number. Here’s how you can implement it along with a detailed explanation:

Kotlin
fun countBits(n: Int): Int {
    var count = 0 // Initialize count of bits
    var num = n   // Copy of n for manipulation

    while (num != 0) {
        count += num and 1 // Increment count if the least significant bit is 1
        num = num ushr 1 // Unsigned shift right by 1 to check the next bit
    }

    return count
}

fun main() {
    val n = 9 // Example number
    println("Number: $n")
    println("Bits count: ${countBits(n)}")
}

Explanation:

  1. Initialization: A variable count is initialized to 0. This variable will hold the total count of 1 bits. Another variable, num, is a copy of the input n, which will be manipulated in the process.
  2. Loop through each bit: The while loop runs as long as num is not zero. Inside the loop, two operations are performed:
    • count += num and 1: This line performs a bitwise AND between num and 1. If the least significant bit (LSB) of num is 1, the expression evaluates to 1, and count is incremented. If the LSB is 0, the expression evaluates to 0, and count remains unchanged.
    • num = num ushr 1: This line right-shifts num by one position without sign extension. The ushr stands for “unsigned shift right”. It ensures that the sign bit is filled with zeros, which is necessary for positive numbers in Kotlin to avoid infinite loops with negative numbers.
  3. Result: The loop continues until num becomes 0, meaning all bits have been checked. The final value of count is the total number of 1 bits in the binary representation of n.

This approach is efficient and straightforward, allowing you to count the number of 1 bits in an integer’s binary representation in Kotlin.

Leave a Comment