Получение значений массива на основе битовой маски в PHP

Question

Получение значений массива на основе битовой маски в PHP

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

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

7

php array-map bit-manipulation

Author: Nikola Obreshkov, 2014-12-18

Source

2 answers

Вам нужно будет выполнить цикл из 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

Author: Paebbels, 2014-12-17 22:11:54

score 1 · Accepted Answer

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

Он явен и использует слова, а не математические трюки, чтобы выполнить работу, и
Работает в ситуациях, когда вы не можете предположить базовую реализацию дополнения 2s, но все же хотите "думать" таким образом. _{^{( попробуйте "хранить" битовые маски в PHP и думать, что они будут работать в JavaScript)}}

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

Он использует base_convert для преобразования целого числа с основанием 10 в основание 2, разбивает строку на массив символов, переворачивает массив и затем перебирает его в поисках единиц.

$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] => Семь )