Table of Contents
What is Binary code?
Example
PHP Program to Count set Bits in an Integer
Output
Method 2: Recursive Approach
Conclusion
Home Backend Development PHP Tutorial PHP Program to Count set Bits in an Integer

PHP Program to Count set Bits in an Integer

Aug 28, 2024 pm 12:07 PM
php

What is Binary code?

Binary code is a system of representing information or data using a base-2 numeral system. It uses only two digits, typically 0 and 1, to represent all values. Each digit in a 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 code, the rightmost bit represents 2^0 (1), the next bit represents 2^1 (2), the next represents 2^2 (4), and so on.

Example

Let's take the decimal number 42 and represent it in binary code. To convert 42 to binary, we divide it successively by 2 and keep track of the remainders 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 start from the bottom (last remainder) and read the remainders from bottom to top.

The resulting 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 digit (bit) that is set to the value of 1. On the other hand, a clear bit refers to a binary digit that is set to the value of 0.

Example

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

PHP Program to Count set Bits in an Integer

PHP Program to Count set Bits in an Integer

Method 1: Loop through all bits in an 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);
?>

Copy after login

Output

Number of setbits in 12: 2
Copy after login

Method 2: Recursive Approach

<?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);
?>
Copy after login

Output

Number of setbits in 123 are: 6
Copy after login

Conclusion

In conclusion, we can count the set bits (1s) in an integer using both a recursive approach and a loop through all bits in PHP. The loop approach involves iterating through each bit of the integer using a while loop. We initialize a counter variable and iterate until the number becomes 0. Inside the loop, we use bitwise AND with 1 to check the least significant bit. If it equals 1, we increment the counter. Then, we right-shift the number by 1 bit. This process continues until all bits have been checked, and the final count is returned.

For the recursive approach, we can define a recursive function that takes an integer as input. Inside the function, we check the least significant bit using bitwise AND operator with 1. If it equals 1, we increment a counter. Then, we right-shift the number by 1 bit and recursively call the function with the updated number. The base case is when the number becomes 0, at which point we return the counter. This approach recursively counts the set bits until the number becomes 0. Both approaches provide a way to count the set bits in an integer, allowing for different implementation choices based on the specific needs and preferences of the programmer.

The above is the detailed content of PHP Program to Count set Bits in an Integer. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 Installation and Upgrade guide for Ubuntu and Debian

CakePHP Date and Time CakePHP Date and Time Sep 10, 2024 pm 05:27 PM

CakePHP Date and Time

CakePHP Project Configuration CakePHP Project Configuration Sep 10, 2024 pm 05:25 PM

CakePHP Project Configuration

CakePHP File upload CakePHP File upload Sep 10, 2024 pm 05:27 PM

CakePHP File upload

CakePHP Routing CakePHP Routing Sep 10, 2024 pm 05:25 PM

CakePHP Routing

Discuss CakePHP Discuss CakePHP Sep 10, 2024 pm 05:28 PM

Discuss CakePHP

CakePHP Quick Guide CakePHP Quick Guide Sep 10, 2024 pm 05:27 PM

CakePHP Quick Guide

How To Set Up Visual Studio Code (VS Code) for PHP Development How To Set Up Visual Studio Code (VS Code) for PHP Development Dec 20, 2024 am 11:31 AM

How To Set Up Visual Studio Code (VS Code) for PHP Development

See all articles