Get array values based on bitmask in PHP

Question

I have a 32-bit integer used for bitmask and an array with 32 values. How to get only those values from the array which indexes correspond to the positions of the non-zero bits in the bitmask?

For example let say that the bitmask is 49152 which is 1100000000000000 in binary. Therefore I have to take the values of elements with indexes 14 and 15 from the array.

Grigg

Answer 1

Here's some PHP code for you, but please note it is pretty inefficient. I have used this algorithm because:

1. It is explicit and uses words rather than mathematical tricks to get the job done, and
2. Works in situations where you can't assume an underlying implementation of 2s complement, but still want to 'think' that way. _{^{(try 'storing' bitmasks in PHP and thinking they will work in JavaScript)}}

Please read the comments and implement @Paebbels solution. The difference in performance is almost 7x, so really only use this if it will not be used very often.

It utilizes base_convert to convert the base 10 integer to base 2, splits the string into a character array, reverses the array and then iterates over it looking for 1s.

$mask = 49152; // 0xC000

// Find which positions in the mask contain a '1'
$bitArray = array_reverse(str_split(base_convert($mask, 10, 2)));

foreach($bitArray as $k => $v) {
    if($v) {
        echo $k . " is a one\n";
    }
}

Output:

14 is a one

15 is a one

As a function:

function extractElements($mask, array $input) 
{
    $output = array();
    $bitArray = array_reverse(str_split(base_convert($mask, 10, 2)));

    foreach($bitArray as $k => $v) {
        if($v && isset($input[$k])) {
            $output[] = $input[$k];
        }
    }

    return $output;
}

$mask = 76; // 0x4C
$input = [
    'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight'
];

print_r(extractElements($mask, $input));

Output:

Array ( [0] => Three 1 => Four [2] => Seven )

Seminal

Sorry, but this solution is consuming masses of memory and CPU cycles for a job of simple bit shifts and bit-compares. – Viole

Masses of memory? Not too bad for a 32-bit integer mask. Unless you have real-time requirements (.. in PHP ..) or you are repeatedly calling this, then this solution is appropriate. Otherwise, I'm sure people will find your answer helpful. – Seminal

My solution: 3 words á 4 bytes = 12 bytes {m, j, i}, it has no call instructions. -- Your solution converts mask from int to string; uses a base conversion based on double values (string to double, base convert, to string conversion); after that a string operation (str_split) is used and finally a string reverse operation. These are just the initial coasts ... In every iteration you are accessing a hash list and calling a isset function for a simple bit compare. Your code uses 35 call instructions. Memory: each char of a intermediate string is stored in 2 bytes (UTF-16) => 64 bytes. – Viole

I'm not saying one should reduce memory and runtime at all coast, but converting int -> string -> double -> string is more expensive than using a mask integer and 2 count variables. – Viole

Updated to make the caveats to this approach more explicit. Hopefully @Nikola Obreshkov will return and rethink. – Seminal

I have implemented this solution and it works solid. I have to admit that the second answer seems more efficient from algorithmic point of view. For anyone interested the practical usage was to tag the treated teeth in a dental image. – Grigg

You could remove the foreach loop and instead use this line: return array_intersect_key($input, array_filter($bitArray)); to get exactly the same array: sandbox.onlinephpfunctions.com/code/… – Benzaldehyde

Answer 2

You will need to loop in 32 steps over your mask and test it for '1', if this bit is set, you can copy the element to your resulting array.

Pseudo code:

m = 0x00000001
j = 0
for i in 0 to 31 loop
  if ((mask & m) = m) then   // bit is set in mask
    result(j++) := input(i)
  end if
  m := m << 1     // shift left by 1 or multiply by 2
end loop

Viole

How can you criticize Jeff Lambert's real PHP code when all you offer is pseudocode which doesn't address the posted question ? – Margartmargate

As Jeff noted, my proposed algorithm (which he implemented) is 7x faster! – Viole

This isn't even PHP. #JustSaying – Upsydaisy

Answer 3

I have implemented a function that fits your needs, and in additional:

• can handle smaller or bigger data type

• saving the values and not only the indexes

---

function extractMask($mask, &$idxs, &$values) {
    for($i = 0, $valueToCompare = 1; $valueToCompare <= $mask; $i++, $valueToCompare <<= 1) {
        if ($mask & $valueToCompare){ 
            $idxs[] = $i;
            $values[] = $valueToCompare;
        }
    }
}

// usage:
extractMask(49152, $idxs, $values);

// results:
var_dump($idxs);
var_dump($values);

For impression, here is a JS snippet:

function extractMask(mask) {
  var result = {idxs: [], values: []};
  for(i = 0, valueToCompare = 1; valueToCompare <= mask; i++, valueToCompare <<= 1) {
    if (mask & valueToCompare){ 
      result.idxs.push(i);
      result.values.push(valueToCompare);
    }
  }
  return result;
}

//====================== UI ==========================
var anchor = document.getElementsByTagName("a")[0];
var input = document.getElementsByTagName("input")[0];
anchor.addEventListener("click", function(e) {
  var result = extractMask(input.value);
  console.log(result);
});
input.addEventListener("keyup", function (e) {
  if (e.keyCode == 13) {
    var result = extractMask(input.value);
    console.log(result);
  }
});
//====================================================

<input value="49152" />
<a href="#">calculate</a>

Decumbent