计算整数中置位的数量

1. Overview

In this tutorial, we’ll discuss the problem of counting the number of set bits in an integer. First, we’ll define the problem. Then, we’ll give an example to explain it.

Finally, we’ll present three different approaches to solving it.

2. Defining the Problem

Suppose we have an integer and we need to count the number of bits that are equal to one in the binary representation of .

Let’s take a look at the following example for a better understanding. Given an integer X = 9 , let’s count the number of set bits in it.

If we look at the binary representation of it looks like this 1001 . There are two bits that are equal to one. Thus, the answer to the given example is .

3. Naive Approach

The main idea in this approach is to iterate over each bit in the binary representation of the given number and see if it’s activated, we increase the answer by one. Otherwise, we skip it.

As long as the given number is greater than zero, we get the first bit of by taking the bitwise and operation between and . If the first bit is on, we increase the answer by one. After that, we get rid of the first bit by dividing by two.

When the number becomes equal to zero, the answer will have the number of set bits in the given integer .

3.1. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm NaiveApproach(X):
    // INPUT
    //    X = an integer
    // OUTPUT
    //    The number of set bits in X

    answer <- 0

    while X > 0:
        first_bit <- X & 1
        if first_bit = 1:
            answer <- answer + 1
        X <- X / 2
    
    return answer

Initially, we declare the countSetBits function that will return the number of set bits in an integer. The function will have one parameter , which will represent the given number to count its set bits.

First, we declare the answer to store the number of set bits. Second, while the given number is greater than zero which means there’re set bits we didn’t count yet, so we get the first bit by taking the bitwise-and operation between and .

Third, if the first bit we got is equal to , it means the first bit is turned on. So, we increase the answer by one. Then, we divide by in order to shift the binary representation of to the right by one to get rid of the first bit we’ve checked.

Finally, we return the answer which stores the number of set bits in the given number .

3.2. Complexity

The time complexity of this algorithm is $\mathbf{O(Log_2(X))}$ , where is the given number. The reason behind this complexity is that we iterate over each bit of , and there are bits.

4. Jumping on Ones Approach

The main idea in this approach is to get the last set bit in the given number, increase the number of set bits by one and then turn off that bit. We keep repeating that operation while the number is greater than zero.

While the given number is greater than zero, we get the last set bit of by taking the bitwise-and operation between and .

(Recall we can get $\textbf{-X}$ by flipping the state of all bits in $\textbf{X}$ then adding one to the result). The result of this operation will turn off all the bits and keep the last set bit on. After that, we delete that last set bit from and increase our answer by one.

When the number becomes equal to zero, the answer will have the number of set bits in the given integer .

4.1. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm JumpingOnOnesApproach(X):
    // INPUT
    //    X = the integer to count set bits in
    // OUTPUT
    //    The number of set bits in the integer X

    answer <- 0

    while X > 0:
        last_bit <- X and -X
        X <- X - last_bit
        answer <- answer + 1

    return answer

Initially, we declare the same countSetBits function as the previous approach, which will return the number of set bits in the given number .

Then, we declare the answer to store the number of set bits. Next, while the given number is greater than zero which means there’re set bits we didn’t count yet, we get the last set bit by taking the bitwise-and operation between and .

After that, we subtract that bit from in order to remove it and then we increase the answer by one.

Finally, the countSetBits(X) will return the number of set bits in the given number .

4.2. Complexity

The time complexity of this algorithm is $\mathbf{O(N)}$ , where is the number of ones in the binary representation of the given number which could be O(1) in the best-case scenario and O(Log_2(X)) in the worst-case scenario.

The reason for this complexity is that we just get the last set bit in the number and remove it as long as the number has turned on bits in his binary representation.

5. Hamming Weight Approach

The main idea here is to cut the binary representation of the given number into blocks, which store the sum of the set bits of the corresponding block. Next, we isolate the odd blocks from the even blocks then align them above each other, and add them up to get new blocks that have sizes twice the old blocks and store the sum of the set bits in the adjacent corresponding old blocks.

First, we’ll start with blocks of size one. We get the odd bits and the even bits. Then, we align them above each other and add them up to get blocks of size two which store the sum of corresponding adjacent bits.

Next, we’ll do the same process on blocks of size two. We separate the odd blocks from the even blocks, align them above each other, and add them up to get blocks of size four. Each block stores the sum of the four corresponding bits. We do the same with blocks of size four to get blocks of size eight, eight to sixteen and sixteen to thirty-two.

Finally, when we reach a block of size that means we get the sum of all bits of the given integer, which means we have the sum of all set bits in the given number.

5.1. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm HammingWeightApproach(X):
    // INPUT
    //    X = an integer
    // OUTPUT
    //    the number of set bits in the integer X

    X <- (X & 0x55555555) + ((X >> 1) & 0x55555555)
    X <- (X & 0x33333333) + ((X >> 2) & 0x33333333)
    X <- (X & 0x0F0F0F0F) + ((X >> 4) & 0x0F0F0F0F)
    X <- (X & 0x00FF00FF) + ((X >> 8) & 0x00FF00FF)
    X <- (X & 0x0000FFFF) + ((X >> 16) & 0x0000FFFF)
    
    return X

Initially, we have the countSetBits function, which will get us the number of set bits of the given integer number.

Next, we’ll do the following steps:

We get the odd bits by taking the operation between and $0 \times 55555555$ which has a binary representation equal to , now in order to get the even bits and align the result with the odd bits, we’ll shift the binary representation of to right by one then we’ll take the operation with $0 \times 55555555$ . The sum of both operations will return a new number that has blocks of size two each of them stores the sum of the corresponding adjection bits.
We get blocks of size two by doing the same operations in the previous step, but instead, we’ll take the with the number $0 \times 33333333$ whose binary representation is equal to and shift the binary representation to the right by two to get the even blocks.
We get blocks of size four by doing the same operations, but instead, we’ll take the with the number $0{\times}0F0F0F0F$ which his binary representation is equal to , and shifting the binary representation to the right by four to get the even blocks.
We get blocks of size eight by doing the same operations, but instead, we’ll take the with the number $0{\times}00FF00FF$ which his binary representation is equal to , and shifting the binary representation to the right by eight to get the even blocks.
We get blocks of size sixteen by doing the same operations, but instead, we’ll take the with the number $0{\times}0000FFFF$ which his binary representation is equal to , and shifting the binary representation to the right by sixteen to get the even blocks.

Finally, the number will be equal to the sum of all bits in a block of size which is the sum of whole bits of the given number.

5.2. Complexity

The time complexity of this algorithm is $\mathbf{O(1)}$ . The reason for this complexity is that we do a constant number of arithmetic operations.

6. Conclusion

In this article, we presented the problem of finding the number of set bits in an integer.

First, we provided an example to explain the problem. Then, we explored three different approaches to solving it.

Finally, we walked through their implementations, with each approach having a better time complexity than the previous one.

Persistence

REST

Security

1. Overview

2. Defining the Problem

3. Naive Approach

3.1. Algorithm

3.2. Complexity

4. Jumping on Ones Approach

4.1. Algorithm

4.2. Complexity

5. Hamming Weight Approach

5.1. Algorithm

5.2. Complexity

6. Conclusion