Number of 1 Bits

🏠 ⬅️ ➡️

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Constraints:

  • The input must be a binary string of length 32.

Follow up: If this function is called many times, how would you optimize it?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    call test_hamming_weight()

contains

    subroutine test_hamming_weight()
        implicit none

        integer :: i
        character(len=32) :: bin_str
        integer :: num_ones

        ! Example 1
        bin_str = "00000000000000000000000000001011"
        num_ones = hamming_weight(bin_str)
        write (*,*) "Example 1:"
        write (*,'(*(g0))') "Input: ", trim(bin_str)
        write (*,'(*(g0))') "Output:", num_ones

        ! Example 2
        bin_str = "00000000000000000000000010000000"
        num_ones = hamming_weight(bin_str)
        write (*,*) "Example 2:"
        write (*,'(*(g0))') "Input: ", trim(bin_str)
        write (*,'(*(g0))') "Output:", num_ones

        ! Example 3
        bin_str = "11111111111111111111111111111101"
        num_ones = hamming_weight(bin_str)
        write (*,*) "Example 3:"
        write (*,'(*(g0))') "Input: ", trim(bin_str)
        write (*,'(*(g0))') "Output:", num_ones

    end subroutine test_hamming_weight

end program main

function hamming_weight(n) result(num_ones)
    implicit none
    character(len=*), intent(in) :: n
    integer :: num_ones

    integer :: i
    logical :: is_one

    num_ones = 0
    do i = 1, len(n)
        is_one = n(i:i) == '1'
        if (is_one) then
            num_ones = num_ones + 1
        end if
    end do

end function hamming_weight
❌ Compiled
❌ Executed
❌ Correct 
! This function takes a binary representation of an unsigned integer and returns the number of '1' bits it has.

integer function hammingWeight(n)
    implicit none
    character(len=32), intent(in) :: n
    integer :: i, count

    count = 0
    do i = 1, 32
        if (n(i:i) == '1') then
            count = count + 1
        end if
    end do

    hammingWeight = count
end function

! Test the function with some examples
program main
    implicit none
    integer :: n, result
    character(len=32) :: binary

    ! Example 1
    binary = "00000000000000000000000000001011"
    n = binaryToInt(binary)
    result = hammingWeight(n)
    write (*,*) "Example 1:", result

    ! Example 2
    binary = "00000000000000000000000001000000"
    n = binaryToInt(binary)
    result = hammingWeight(n)
    write (*,*) "Example 2:", result

    ! Example 3
    binary = "11111111111111111111111111111101"
    n = binaryToInt(binary)
    result = hammingWeight(n)
    write (*,*) "Example 3:", result
end program

! Convert a binary string to an unsigned integer
integer function binaryToInt(binary)
    implicit none
    character(len=32), intent(in) :: binary
    integer :: i, n

    n = 0
    do i = 1, 32
        if (binary(i:i) == '1') then
            n = n + 2**(31-i)
        end if
    end do

    binaryToInt = n
end function
🌐 Data from online sources 
def hamming_weight(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

The algorithm for this problem is straightforward. We use a bitwise AND operation with 1 to check the rightmost bit of the input integer n. If the result is 1, then the rightmost bit is a '1', and we increment the count. We continue to check the rest of the bits by shifting n to the right (>> in C++/Python or >>> in Java/JavaScript, since Java/JavaScript use signed right shift) to remove the rightmost bit. The loop continues until n becomes 0, which means there are no more '1' bits. Finally, we return the count of 1 bits.

Note that the '>>>=' unary operator in Java and JavaScript is used to avoid sign extension when shifting right. This ensures that the shift is done in an unsigned manner.

🌐 Data from online sources 
int hammingWeight(uint32_t n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

The algorithm for this problem is straightforward. We use a bitwise AND operation with 1 to check the rightmost bit of the input integer n. If the result is 1, then the rightmost bit is a '1', and we increment the count. We continue to check the rest of the bits by shifting n to the right (>> in C++/Python or >>> in Java/JavaScript, since Java/JavaScript use signed right shift) to remove the rightmost bit. The loop continues until n becomes 0, which means there are no more '1' bits. Finally, we return the count of 1 bits.

Note that the '>>>=' unary operator in Java and JavaScript is used to avoid sign extension when shifting right. This ensures that the shift is done in an unsigned manner.