找出已添加的数字以得出总和

Question

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

我在网站上有一个提出问题的表格.答案是复选框形式.每个答案都以"得分"保存到我的数据库中,值如下所示:

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

如您所见,分数是前两个值的两倍.当用户填写表单时,答案将作为一个值保存在数据库中 - 所有答案一起添加.

例如,用户选择了值:过敏,一般医学,血液学,产科.在数据库中,此问题的答案保存为2689.

有没有办法通过只回答问题来找出选择了哪些答案？

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

编辑:我希望用PHP反向设计答案.

Answer 1

是的,这是一种称为位屏蔽的常见模式.使用您的语言的二元AND运算符对应于给定答案的值和从表单提交的值,以查看给定答案是否是所选择的选项之一.例如,如果提交和保存的答案与2689您的示例相同,则可以通过查看是否2689 & 4为非零来检查"胸部疾病"是否是所选择的选项之一.(&应该用二进制AND运算符替换为您选择的语言.)

请注意,只有与个别选项对应的所有值都是2的幂时,这才有效.通常,在标题中提出的问题是关于找出给定集合中的哪些数字已经添加以得出给定的总和,是一个称为背包问题的实例,只有通过检查每个可能的组合才能解决,这是非常低效的.(NP-complete,具体而言)

Answer 2

您可以通过ANDing以2的幂来查找值.

2 ⁰ = 1
2 ¹ = 2
2 ² = 4
2 ³ = 8
...
2 ²³ = 8388608

您可以使用二进制移位找出2 ⁿ的值,如下所示: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友好