1

对不起标题。我不知道怎么问这个问题。

我在一个网站上有一个表格问一个问题。答案是复选框的形式。每个答案都使用“分数”保存到我的数据库中，值如下所示：

Allergy 1
Cardiology  2
Chest Disease   4
Dermatology 8
Emergency Room  16
Ambulance Trips 32
Gastroenterology    64
General Medicine    128
Gynecology  256
Hematology  512
Neurology   1024
Obstetrics  2048
Opthamology 4096
Orthopedics 8192
Physical Therapy    16384
Plastic Surgery 32768
Podiatry    65536
Proctology  131072
Psychiatry  262144
Surgery Performed   524288
Thoracic Surgery    1048576
Urology 2097152
Outside X-Rays  4194304
Diagnostic Tests (outside)  8388608

如您所见，分数是前一个值乘以 2。当用户填写表格时，答案将作为一个值保存在数据库中 - 所有答案加在一起。

例如，用户选择了以下值：过敏、普通医学、血液学、产科。在数据库中，此问题的答案保存为2689.

有没有办法通过仅获得问题的答案来确定选择了哪些答案？

例如，我会查询我的数据库并提取2689值，我需要确定检查了哪些答案。

编辑：我希望在 PHP 中对答案进行逆向工程。

4

6 回答 6

6

是的，这是一种称为位掩码的常见模式。对与给定答案对应的值和从表单提交的值使用您的语言的二元 AND 运算符，以查看给定答案是否是选定选项之一。例如，如果提交并保存的答案与2689您的示例一样，您可以通过查看是否2689 & 4为非零来检查“胸部疾病”是否是所选选项之一。（&应该用您选择的语言中的二进制 AND 运算符替换。）

请注意，这仅适用于与个人选择相对应的所有值都是 2 的幂的情况。通常，您的标题中提出的问题是，要找出给定集合中的哪些数字已被添加以得出给定的总和，是所谓的背包问题的一个例子，只有通过检查每个可能的组合才能解决，这是非常低效的。（特别是NP完全）

于 2013-04-17T13:19:40.183 回答
5

您可以通过与 2 的幂进行与运算来找到值。

2 0 = 1
2 1 = 2
2 2 = 4
2 3 = 8
...
2 23 = 8388608

您可以像这样使用二进制移位找出 2 n的值： 1 << n

php 之类的代码：

$item[] = {"Allergy", "Cardiology", ..., "Diagnostic Tests (outside)"};
$answer = 2689;

for ( $power = 0; $power < count($item); $power++ ) {

   if ( 1 << $power & $answer ) {
       echo $item[$power] . "\n";
   }
}

编辑：使它对 php 更友好

于 2013-04-17T13:27:27.527 回答
2

就在这里。请注意，每个第k个“分数”的形式为 2^( k - 1)，它对应于仅设置了第k个位的位串。如果您知道设置了哪些位，则可以重建总和。

以 2689 为例，我们首先需要将其写成二进制：

2689 = 101010000001b

从右边数，我们看到第一个、第八个、第十个和第十二位被设置，所以（你可以验证）

2689 = 2^0 + 2^7 + 2^9 + 2^11
     = 1 + 128 + 512 + 2048

可以使用按位运算有效地完成此操作的实际实现。通过AND依次获取值和每个“分数”，然后检查它是否给出非零值，我们可以检查哪些分数进入了总和。

于 2013-04-17T13:19:21.060 回答
1

这将完全符合您的要求：

<?php
Print bindecValues("2689");

function bindecValues($decimal, $reverse=false, $inverse=false) {

$bin = decbin($decimal);
if ($inverse) {
    $bin = str_replace("0", "x", $bin);
    $bin = str_replace("1", "0", $bin);
    $bin = str_replace("x", "1", $bin);
}
$total = strlen($bin);

$stock = array();

for ($i = 0; $i < $total; $i++) {
    if ($bin{$i} != 0) {
        $bin_2 = str_pad($bin{$i}, $total - $i, 0);
        array_push($stock, bindec($bin_2));
    }
}

$reverse ? rsort($stock):sort($stock);
return implode(", ", $stock);
}
?>

快乐编码

于 2014-04-03T11:37:05.117 回答
0

请记住，整数以二进制形式存储 - 因此这些标志中的每一个（过敏 = 1）等都将对应于和的二进制表示中的单个位是真还是假。

例如，二进制中的 2689 是0000 1010 1000 0001哪个，如果您将其视为一个位数组，其中最低有效位（该数组中的最右边）是最低有效标志（过敏），那么我们可以很容易地看到第一个（过敏)、第八个（gen.medicine）、第十个（血液学）和第十二个（obs）阵列的插槽用 1 标记为真。

标志数组中的最大值是 32 位整数中的第 24 位。在必须使用更大的整数之前，您可以在此系统中定义多达 8 个标志。

于 2013-04-17T13:18:44.117 回答
0

由于您所有的数字似乎都是 2 的幂，您只需将输入值存储在一个足够长的整数中以保存它，然后是位掩码。

if( value & 1 ) then 1 was part of the selection
if( value & 2 ) then 2 was part of the selection
if( value & 3 ) then 3 was part of the selection
and so on
于 2013-04-17T13:20:08.540 回答