Count valid unset bits in numbers from 1 to n in php
Php program for Count valid unset bits in numbers from 1 to n. Here mentioned other language solution.
<?php
/*
Php program for
Count valid unset bits in all numbers from 1 to n
*/
class BitCount
{
// Returns number of set bits of given number
public function countSetBit($num)
{
$x = $num;
$x = $x - (($x >> 1) & 1431655765);
$x = ($x & 858993459) + (($x >> 2) & 858993459);
$x = ($x + ($x >> 4)) & 252645135;
$x = $x + ($x >> 8);
$x = $x + ($x >> 16);
$x = $x & 63;
// Number of set bit
return $x;
}
// Handles the request of count the all
// unset bits from (1 to n)
public function countUnsetBit($n)
{
$result = 0;
// Execute loop from 1 to n
for ($i = 1; $i <= $n; ++$i)
{
// Total bits - Active bits
$result += ((int)(log($i) / log(2.0) + 1.0)) -
$this->countSetBit($i);
}
// Display result
echo " Unset bits from (1 to ".($n).
") : ".($result), "\n";
}
public static function main()
{
$task = new BitCount();
// Test A
// number(1-7) Un-setbit
// ----------------
// 1 = 1 0
// 2 = 10 1
// 3 = 11 0
// 4 = 100 2
// 5 = 101 1
// 6 = 110 1
// 7 = 111 0
// --------------------
// 5
$task->countUnsetBit(7);
// Test B
// number(1-10) Setbit
// ----------------
// 1 = 1 0
// 2 = 10 1
// 3 = 11 0
// 4 = 100 2
// 5 = 101 1
// 6 = 110 1
// 7 = 111 0
// 8 = 1000 3
// 9 = 1001 2
// 10 = 1010 2
// --------------------
// 12
$task->countUnsetBit(10);
}
}
BitCount::main();
Output
Unset bits from (1 to 7) : 5
Unset bits from (1 to 10) : 12
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment