PHP program to count the number of set bits in an integer

What is binary code?

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

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

Example

Let's convert the decimal number 42 to binary code. To convert 42 to binary, we continuously divide it by 2 and keep track of the remainder until the quotient becomes zero

The following is the step-by-step process:

first step

42 ÷ 2 = 21, the remainder is 0

Second step

21 ÷ 2 = 10, the remainder is 1

Step 3

10 ÷ 2 = 5, remainder is 0

the fourth step

5 ÷ 2 = 2, the remainder is 1

the fifth step

2 ÷ 2 = 1, remainder is 0

Step Six

1 ÷ 2 = 0, remainder is 1

To get the binary representation, we start from the bottom (the last remainder) and read the remainders from the bottom upwards

The binary code for 42 is: 101010

So, the decimal number 42 is represented as 101010 in binary code.

What is Setbit?

In the context of binary code, a set bit refers to a binary number (bit) that is set to 1. Clear bits, on the other hand, refer to binary digits (bits) that are set to 0

Example

For example, in binary code 101010, there are three set bits (corresponding to positions with a value of 1) and three clear bits (corresponding to positions with a value of 0).

PHP Program: Count the number of set bits in an integer

Method 1: Loop through all the bits in the integer

Example

<?php
// Function to get no of set
// bits in binary representation
// of 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 method

<?php
// PHP implementation of recursive
// approach to find the number of
// set bits in binary representation
// of positive integer n

// recursive function
// to count set bits
function countSetBits($n)
{
	// base case
	if ($n == 0)
		return 0;

	else

		// if last bit set
		// add 1 else add 0
		return ($n & 1) +
				countSetBits($n >> 1);
}

// Driver code

// get value from user
$n = 123;

// function calling
echo "Number of setbits in $n are: ".countSetBits($n);
?>

Output

Number of setbits in 123 are: 6

Conclusion

In summary, we can count the number of set bits (1) in an integer using recursive methods and looping through all bits. 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 reaches 0. Inside the loop, we do a bitwise AND with 1 using the bitwise AND operator to check the least significant bit. If it's equal to 1, we increment the counter. Then we move the number 1 place to the right. This process continues until all bits have been checked and the final count is returned

For recursive methods, we can define a recursive function that takes an integer as input. Inside the function we use bitwise AND operator and 1 to check the least significant bit. If it's equal to 1, we increment a counter. We then shift the number right by 1 place and call the function recursively with the updated number. The basic case is that when the number reaches 0, we return the value of the counter. This method recursively calculates the set bits until the number becomes 0. Both methods provide a way to count set bits in an integer, with different implementation options depending on the programmer's specific needs and preferences.

The above is the detailed content of PHP program to count the number of set bits in an integer. For more information, please follow other related articles on the PHP Chinese website!