Как получить набор числовых рядов из двух битов 16-битного int?
(Работа над алгоритмом поиска) Я хочу перебрать возможные совпадения с двумя битами, установленными в 16-битном слове. Кажется глупой проблемой с чрезмерно сложным в настоящее время решением.
Итерация должна возвращать (десятичное число) 3,5,6,9,10,12,17...
Какое подходящее слово для этой проблемы? Зацикливание на битовой маске? Есть какая-нибудь умная функция для этого?
Текущий код - теперь обновлен: (Как бы то ни было, я думаю, что нет более простого способа обойти это.)
<?php
function biterate($numBits=8, $setBits=2, $maxval=null) {
//init
if(is_null($maxval)) $maxval = (pow(2,$setBits)-1) * pow(2,$numBits - $setBits);
$err = 0;
header('content-type:text/plain');
echo '-- ' . $setBits . ' of ' . $numBits . " --\r\n";
$result = str_pad('', $numBits - $setBits, '0') . str_pad('', $setBits, '1');
do {
$err++;
if($err > 200) die('bad code');
//echo and calc next val.
echo $result . ' : ' . bindec($result) . "\r\n";
//count set bits and search for '01' to be replaced with '10'. From LSB.
$bitDivend = '';
$hit = false;
for($i=$numBits;$i>0;$i--) {
if(substr($result,$i-2,2) == '01') {
$hit = true;
//do the replacement and replace the lower part with bitDivend.
$result = substr($result, 0, $i-2) . '10';
$result .= str_pad('',$numBits - $i - strlen($bitDivend),'0');
$result .= $bitDivend;
//exit loop
$i = 0;
}
if($result[$i-1] == '1') $bitDivend .= '1';
}
} while($hit && bindec($result) <= $maxval);
}
biterate(8,2);
biterate(8,7);
biterate();
1 answers
Если вы просто хотите, чтобы все 16-битные входы были установлены с 2 битами, это должен сделать следующий код:
<?php
for($i=1;$i<16;$i++)
{
for($j=0;$j<$i;$j++)
{
echo (1<<$i)|(1<<$j) , "\r\n";
}
}
?>
Если вы посмотрите на битовые шаблоны чисел, вы увидите, как это работает:
11 3
101 5
110 6
1001 9
1010 10
1100 12
10001 17
10010 18
10100 20
11000 24
И т.д. Вы просто перемещаете наиболее значимый бит на одно место влево (другая степень 2) для каждой итерации внешнего цикла, а внутри внутреннего цикла вы повторяете от наименее значимого бита (1) до 1 места справа от наиболее значимого бита.
Если вы хотите обобщить это позволяет поддерживать произвольное количество битов и мест, вы можете расширить описанный выше алгоритм с помощью рекурсии:
<?php
function biterate_recursive($numBits=8, $setBits=2, $initialValue=0, $maxval=null) {
for($i=$setBits-1;$i<$numBits;$i++)
{
if(!is_null($maxval) && ($initialValue|(1<<$i)) > $maxval)
break;
if($setBits==1)
echo $initialValue|(1<<$i) , "\r\n";
else
biterate_recursive($i, $setBits-1, $initialValue|(1<<$i), $maxval);
}
}
biterate_recursive(16, 2);
?>
Вы также можете думать о проблеме как о простом выборе комбинаций, т.Е. C(16,2) выбирает 2 числа a, b из набора 0-15, а затем вычисляет (1<<a)|(1<<b). Однако вы должны быть осторожны с выбором алгоритма комбинации, если хотите расположить числа по порядку.