Making the & and | bitwise operators work higher than 2^31

[Goldeneye]

Here is a simple script which uses bitwise operations to determine whether or not a checkbox has been set. The problem is that if you use the $alpha array, the script doesn't produce the results you should expect. For example, if you set the last checkbox while using the $alpha array, all the checkboxes become set.

 

I partially know why this happens as the PHP-Manual enlightened me:

From: http://www.php.net/manual/en/language.operators.bitwise.php

Don't right shift for more than 32 bits on 32 bits systems. Don't left shift in case it results to number longer than 32 bits.

 

I attempted to use the GMP_* functions but because those aren't part of the PHP-Standard-Library, I do not wish to rely on them. Is there any way to make these functions work for integers beyond 2^31?

 

Here is a standalone script I'm using to make these tests.

$alpha = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z');
$delta = range('a', 'z');

function generate($array){
	$n = count($array);
	$c = array();
	for($i = 0; $i < $n; ++$i){
		$c[bcpow(2, $i)] = $array[$i];
	}
	return $c;
}

function set($array, $post){
	$c = 0;
	foreach($array as $key => $val)
		if(isset($post['c'.$key])) $c |= $key;
	return $c;
}

function check($num, $category){
	if($num & $category) return 'CHECKED';
	return '';
}

function checkboxes($array, $numval=0){
	$i = 0;
	$form = '';
	foreach($array as $key => $val){
		$checked = check($numval, $key);
		$form .= '<input type="checkbox" '.$checked.' name="c'.$key.'" id="c'.$key.'">' . '<label for="c'.$key.'"> '.$val.'</label><br />';
		++$i;
	}
	return $form;
}

$array = generate($alpha);
$num = 0;
if(isset($_POST['action'])){
	$num = set($array, $_POST);
	echo $num;
}
echo '<form action="y.php" method="post" style="width: 400px; border: 1px solid black;">';
echo checkboxes($array, $num);
echo '<input type="submit" name="action" value="Set" />';
echo '</form>';

[btherl]

Not as far as I know.. I'm guessing that since you want portability, using 64 bit php isn't a solution.  I think the simplest solution is to use more than one integer.  Bits 33-64 can go in the second integer, 65-96 in the third, and so on.

 

Is there any reason you are storing the checkboxes this way?  An associative array would be much simpler to deal with.  And if memory use is very important, php is probably the wrong language

[Goldeneye]

I think the simplest solution is to use more than one integer.  Bits 33-64 can go in the second integer, 65-96 in the third, and so on.

How would I accomplish that?  :-\

 

Well, it's not that I'm explicitly storing checkboxes this way. This is what I implemented for my user-permission system and categorization system.

[btherl]

The only possible reason I can imagine for using that data structure is to save memory.  Is that your goal?  If it is, then I can describe a complicated but very efficient way to store bits.  But if you're not trying to save memory, just store the data like this:

 

$fields = array(
  '5' => true,
  '15' => true,
);

 

If you do want to save memory, the most efficient way to store data in php is to pack it into a string.  You can pack as many integers as you want into a string, just by putting them one after another.  Each integer can store 32 bits.  You can read and write these integers using http://php.net/manual/en/function.pack.php and http://php.net/manual/en/function.unpack.php

 

The integer where a bit should be stored is floor($bit_no / 32).  This will give you 0 for bits 0-31, 1 for bits 32-63, and so on.  If the bit numbers start with 1, then you can subtract 1 before doing the division.

 

Does that make sense?  Once you've fetched the integer you can use the normal bit manipulation operators.  Then you can store it back again. 

[Goldeneye]

The Math part makes sense to me. But accomplishing it, I can't get my head around.

 

You can pack as many integers as you want into a string, just by putting them one after another.

You mean by concatenation?

 

The only reason it doesn't make complete sense is because I am unfamiliar with the pack and unpack functions. Would this be considered as using a bitmask? Or is a bitmask something completely different?

[btherl]

Yep, by concatenation.  I wouldn't call it "using a bitmask", although the effect is what you would get if you used a bitmask and then shifted the result, if php was able to do bitwise operations on more than 32 bits.

 

I would probably go for the "l" option in pack(), "signed 32 bit integer, machine byte order".  As long as you don't transport packed strings between different machines, the byte order doesn't matter.

 

$str = pack("l*", 1,2,3);
print urlencode($str) . "\n";
$ints = unpack("l*", $str);
var_dump($ints);

 

Unfortunately php doesn't accept arrays as arguments to pack().  So you'll either need to have a fixed number of integers, or you can use a loop to generate the packed string, packing 1 integer at a time and concatenating the results.  You can still unpack them all in one call to unpack(), and you'll get an array as the result.