CODEWITHSUNDEEP
phpalgorithmmath
quickshiftin
quickshiftin

Reputation: 69621

Is there a clever way to do this with pure math

I've got this spot of code that seems it could be done cleaner with pure math (perhaps a logarigthms?). Can you help me out?

The code finds the first power of 2 greater than a given input. For example, if you give it 500, it returns 9, because 2^9 = 512 > 500. 2^8 = 256, would be too small because it's less than 500.

function getFactor($iMaxElementsPerDir)
{
    $aFactors = range(128, 1);
    foreach($aFactors as $i => $iFactor)
        if($iMaxElementsPerDir > pow(2, $iFactor) - 1)
            break;
    if($i == 0)
        return false;
    return $aFactors[$i - 1];
}

The following holds true

getFactor(500)  = 9
getFactor(1000) = 10
getFactor(2500) = 12
getFactor(5000) = 13

Upvotes: 2

Views: 157

Answers (4)

Ja͢ck
Ja͢ck

Reputation: 173582

If you're looking for a "math only" solution (that is a single expression or formula), you can use log() and then take the ceiling value of its result:

$factors = ceil(log(500) / log(2)); // 9
$factors = ceil(log(5000) / log(2)); // 13

I seem to have not noticed that this function accepts a second argument (since PHP 4.3) with which you can specify the base; though internally the same operation is performed, it does indeed make the code shorter:

$factors = ceil(log(500, 2)); // 9

To factor in some inaccuracies, you may need some tweaking:

$factors = floor(log($nr - 1, 2)) + 1;

Upvotes: 2

tmyklebu
tmyklebu

Reputation: 14205

There are a few ways to do this.

  1. Zero all but the most significant bit of the number, maybe like this:

    while (x & x-1) x &= x-1;

    and look the answer up in a table. Use a table of length 67 and mod your power of two by 67.

  2. Binary search for the high bit.

  3. If you're working with a floating-point number, inspect the exponent field. This field contains 1023 plus your answer, except in the case where the number is a perfect power of two. You can detect the perfect power case by checking whether the significand field is exactly zero.

  4. If you aren't working with a floating-point number, convert it to floating-point and look at the exponent like in 3. Check for a power of two by testing (x & x-1) == 0 instead of looking at the significand; this is true exactly when x is a power of two.

Note that log(2^100) is the same double as log(nextafter(2^100, 1.0/0.0)), so any solution based on floating-point natural logarithms will fail.

Here's (nonconformant C++, not PHP) code for 4:

int ceillog2(unsigned long long x) {
  if (x < 2) return x-1;
  double d = x-1;
  int ans = (long long &)d >> 52;
  return ans - 1022;
}

Upvotes: 1

bitWorking
bitWorking

Reputation: 12665

The same as jack but shorter. Log with base 2 is the reverse function of 2^x.

echo ceil(log(500, 2));

Upvotes: 2

Beed
Beed

Reputation: 460

You can get the same effect by shifting the bits in the input to the right and checking against 0. Something like this.

i = 1
while((input >> i) != 0)
    i++

return i

Upvotes: 4

Related Questions