Maths problem in PHP

[toastyman]

Greetings to all!

I'm currently working on a permissions system for a CMS i'm building, but have hit a slight problem... maths

Take the following list:
1
2
4
8
16
32
etc...

Yep, they're all just doubling the previous value. Easy enough!


Now what I want to do is supply a number, let's say 11. I then need to find all the numbers in that list which when added together, produce that number. So in the case of 11, this would return 1, 2 and 8 (1 + 2 + 8 = 11).

Via a bit of googling, i've got the following code:

$mask = 5;
$return = array();
while ($mask > 0) {
	for($i = 0, $n = 0; $i <= $mask; $i = 1 * pow(2, $n), $n++) {
		$end = $i;
		$return[] = $end;
	}        
	$mask = $mask - $end;
}
sort($return);

However, it doesn't work very well... it returns
[0] => 0
[1] => 0
[2] => 1
[3] => 1
[4] => 2
[5] => 4

when it should return
[0] => 1
[1] => 4

Does anyone have any ideas on how to go about solving this problem? Any ideas, attempts etc would be appreciated!

 

[Inquisitor]

Try this:

$mask = 5;
$permissions = array();
while ($mask > 0)
{
	$permissions[] = ($mask & 1) == 1;
	$mask >>= 1;
}

It'll produce an array of booleans, true representing a set bit and false representing an unset bit, so with 5, you'll get {true, false, true}, or with 11, {true, true, false, true}.

That isn't exactly what you're asking for, but it's how I'd do it

 

[toastyman]

Haha fantastic! I didn't realise it was so simple!

I adapted your code to give the array of numbers:

<?php
$mask = 11;
$permissions = array();
$perm = 1;
while ($mask > 0)
{
	if(($mask & 1) == 1)
		$permissions[] = $perm;
	$perm = $perm * 2;
	$mask >>= 1;
	
}
print_r($permissions);
?>

Thanks very much

 

[Inquisitor]

Haha fantastic! I didn't realise it was so simple!

I adapted your code to give the array of numbers:

<?php
$mask = 11;
$permissions = array();
$perm = 1;
while ($mask > 0)
{
	if(($mask & 1) == 1)
		$permissions[] = $perm;
	$perm = $perm * 2;
	$mask >>= 1;
	
}
print_r($permissions);
?>

Thanks very much

No problems!

You could actually write that slightly more concisely as:

for ($i = 1; $mask > 0; $i <<= 1, $mask >>= 1)
{
	if (($mask & 1) == 1)
	{
		$permissions[] = $i;
	}
}

The << and >> operators are the left and right binary shift operators respectively: they essentially take all the bits in the number (if you imagine it as binary) and move them one place to the left or right, which has the effect of multiplying or dividing by two (any remainder after the division is dropped).

So 3 << 4 is the same as 3 * pow(2, 4).

 

[toastyman]

Ah ha, very useful information! I did wonder what the << and the >> did, and was just looking them up when I noticed there was a reply on this thread.

Binary never was my strong point, but I see it and it's mathamatical techniques are definetely worth learning for situtations like this!

Again, thanks very much