управление битами — получение значений массива на основе битовой маски в переполнении стека

У меня есть 32-разрядное целое число, используемое для битовой маски и массив с 32 значениями. Как получить из массива только те значения, индексы которых соответствуют позициям ненулевых битов в битовой маске?

Например, допустим, что битовая маска 49152, а в двоичном — 1100000000000000. Поэтому я должен взять значения элементов с индексами 14 и 15 из массива.

9

Решение

Вот некоторый код PHP для вас, но, пожалуйста, обратите внимание, что он довольно неэффективен. Я использовал этот алгоритм, потому что:

  1. Это явно и использует слова, а не математические трюки, чтобы сделать работу, и
  2. Работает в ситуациях, когда вы не можете принять основную реализацию дополнения 2s, но все же хотите «думать» таким образом. (попробуйте «хранить» битовые маски в PHP и думать, что они будут работать в JavaScript)

Пожалуйста, прочтите комментарии и внедрите решение @Paebbels. Разница в производительности почти в 7 раз, поэтому используйте ее только в том случае, если она не будет использоваться очень часто.

Он использует base_convert чтобы преобразовать целое число 10 в число 2, разбивает строку на массив символов, переворачивает массив, а затем перебирает его в поисках 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] => Семь
)

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
6

Я реализовал функцию, которая соответствует вашим потребностям, и дополнительно:

  • может обрабатывать меньший или больший тип данных

  • сохранение значений, а не только индексов


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>
0