Current Location: Home> Latest Articles> How to Count the Number of Set Bits in an Integer Using PHP

How to Count the Number of Set Bits in an Integer Using PHP

M66 2025-06-20

What is Binary Code?

Binary code is a system used to represent information or data using the binary number system. It only uses two digits, usually 0 and 1, to represent all values. Each digit in binary code is called a bit (short for binary digit).

In binary code, each digit represents a power of 2. Starting from the rightmost digit, the powers of 2 increase from right to left. For example, in an 8-bit binary number, the rightmost bit represents 20 (1), the next bit represents 21 (2), and so on.

Binary Number Example

Let’s convert the decimal number 42 into binary code. To convert 42 to binary, we repeatedly divide it by 2 and track the remainder until the quotient becomes zero.

Here’s the step-by-step process:

Step 1: 42 ÷ 2 = 21, remainder 0

Step 2: 21 ÷ 2 = 10, remainder 1

Step 3: 10 ÷ 2 = 5, remainder 0

Step 4: 5 ÷ 2 = 2, remainder 1

Step 5: 2 ÷ 2 = 1, remainder 0

Step 6: 1 ÷ 2 = 0, remainder 1

To obtain the binary representation, we read the remainders from bottom to top. The binary code for 42 is 101010, so the decimal number 42 is represented as 101010 in binary.

What are Set Bits (Setbit)?

In the context of binary code, a set bit refers to a bit that is set to 1. On the other hand, a cleared bit refers to a bit that is set to 0.

Set Bit Example

For example, in the binary code 101010, there are three set bits (the positions where the value is 1) and three cleared bits (the positions where the value is 0).

PHP Program: Count the Number of Set Bits in an Integer

Method 1: Loop Through All the Bits of the Integer

Here’s an example of a PHP program using the loop method to count the number of set bits:

<?php
// Function to get the number of set bits in the binary representation of a positive integer n
function countSetBits($n)
{
    $count = 0;
    while ($n) {
        $count += $n & 1;
        $n >>= 1;
    }
    return $count;
}

// Driver Code
$number = 12;
echo "Number of setbits in $number: " . countSetBits($number);
?>

Output

Number of setbits in 12: 2

Method 2: Recursive Approach

Here’s an example of a PHP program using the recursive method to count the number of set bits:

<?php
// PHP implementation of recursive approach to find the number of set bits
function countSetBits($n)
{
    // base case
    if ($n == 0)
        return 0;
    else
        // if last bit is set, add 1 else add 0
        return ($n & 1) + countSetBits($n >> 1);
}

// Driver code
$n = 123;
echo "Number of setbits in $n are: " . countSetBits($n);
?>

Output

Number of setbits in 123 are: 6

Conclusion

In conclusion, we can use both the recursive and loop traversal methods to calculate the number of set bits (1s) in an integer. The loop method involves using a while loop to iterate through each bit of the integer. We initialize a counter variable and iterate until the number becomes 0. Inside the loop, we use the bitwise AND operator with 1 to check the least significant bit. If it’s 1, we increment the counter, then shift the number right by 1. This process continues until all bits are checked, and we return the final count.

For the recursive method, we define a recursive function that takes an integer as input. Inside the function, we use the bitwise AND operator with 1 to check the least significant bit. If it’s 1, we increment the counter. Then we shift the number right by 1 and recursively call the function with the updated number. The base case is when the number becomes 0, at which point we return the count. This method recursively counts the set bits until the number becomes 0.

Both methods provide ways to count set bits in an integer. Programmers can choose the implementation method based on their specific needs and preferences.

Related