在PHP中根据位掩码获取数组值

Question

我有一个用于位掩码的32位整数和一个包含32个值的数组。如何仅获取数组中索引对应于位掩码中非零位位置的值？

例如，假设位掩码为49152，即二进制中的1100000000000000。因此，我必须从数组中取出索引为14和15的元素的值。

- Nikola Obreshkov

Answer 1

你需要在32个步骤中循环你的掩码并测试它是否为“1”，如果这一位被设置，你可以将元素复制到结果数组中。

伪代码：

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

- Paebbels

---

当你所提供的只是未解决问题的伪代码时，你如何批评Jeff Lambert的真实PHP代码？ - David N. Jafferian

正如Jeff所指出的那样，我提出的算法（他已经实现了）快了7倍！ - Paebbels

这甚至不是PHP。#只是说一下 - e-sushi

Answer 2

我已经实现了一个符合您需求的函数，并且还有以下额外功能：

• 可以处理更小或更大的数据类型

• 保存值而不仅仅是索引

---

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);

举个例子，这里有一段JS代码：

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>

- Dorad

Answer 3

这是一段PHP代码，但请注意它相当低效。我使用了这个算法，因为：

1. 它明确地使用单词而不是数学技巧来完成工作，
2. 在无法假设2s补码的基础实现的情况下仍然可以以这种方式思考。 _{^{（尝试在PHP中“存储”位掩码并认为它们将在JavaScript中起作用）}}

请阅读注释并实施@Paebbels的解决方案。性能差异几乎是7倍，因此只有在很少使用时才使用它。

它利用base_convert将十进制整数转换为二进制，将字符串拆分为字符数组，反转数组，然后迭代查找1。

$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";
    }
}

输出：

14 是一个

15 是一个

作为一个函数：

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));

输出：

数组 ( [0] => 三 1 => 四 [2] => 七 )

- Jeff Lambert

---

抱歉，但是这个解决方案在处理简单的位移和位比较时消耗了大量的内存和 CPU 周期。 - Paebbels

我并不是说在所有情况下都应该减少内存和运行时间，但将int -> string -> double -> string转换比使用掩码整数和2个计数变量更昂贵。 - Paebbels

更新以更明确地说明这种方法的注意事项。希望@Nikola Obreshkov能够回来并重新考虑。 - Jeff Lambert

我已经实现了这个解决方案，并且它非常可靠。不得不承认，从算法的角度来看，第二个答案似乎更有效率。对于任何有兴趣的人，实际应用是在牙科影像中标记治疗过的牙齿。 - Nikola Obreshkov

你可以移除 foreach 循环，使用这行代码代替：return array_intersect_key($input, array_filter($bitArray)); 可以得到完全相同的数组：http://sandbox.onlinephpfunctions.com/code/b7d9a706c34797d1b0a5d5a74ccd2f969b227b0e - Erenor Paz