Finding out what numbers have been added to come up with a sum

Finding out what numbers have been added to come up with a sum

Sorry for the title. I wasn't sure how to ask this question.

I have a form on a website that asks a question. The answers are in check box form. Each answer is saved into my database with a 'score', the values look like this:

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  

As you can see, the score is the previous value times two. When a user fills out the form, the answer is saved in the database as one value - all the answers added together.

For example, a user selected the values: Allergy, General Medicine, Hematology, Obstetrics. In the database, the answer for this question is saved as 2689.

Is there a way to figure out what answers have been selected by only having the answer to the question?

For example, I would query my database and pull the 2689 value, and I need to determine what answers were checked.

edit: I was hoping to reverse engineer the answer in PHP.

Answer by Mikeb for Finding out what numbers have been added to come up with a sum

Remember that integers are stored in binary - so each of these flags (Allergy = 1) etc. will correspond to a single bit being true or false in the binary representation of the sum.

For example, 2689 in binary is 0000 1010 1000 0001 which, if you think of it as an array of bits, where the least significant bit (right most in that array) is the least significant flag (allergy) then we can easily see that the first (allergy), eighth (gen. medicine), tenth (hematology) and twelfth (obs) slots of the array are marked with a 1 for true.

The largest value in your array of flags is 24th bit in a 32 bit integer. You could define up to 8 more flags in this system before having to use a larger integer.

Answer by Fred Foo for Finding out what numbers have been added to come up with a sum

Yes, there is. Note that each k'th "score" is of the form 2^(k - 1), which corresponds to a bitstring with only the k'th bit set. If you know which bits are set, you can reconstruct the sum.

Taking 2689 as an example, we first need to write it out in binary:

2689 = 101010000001b  

Counting from the right, we see that the first, eighth, tenth and twelfth bits are set, so (as you can verify)

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

The actual implementation of this can be done efficiently using bitwise operations. By taking the AND of the value and each of the "scores" in turn, then checking whether that gives a non-zero value, we can check which scores went into the sum.

Answer by David Z for Finding out what numbers have been added to come up with a sum

Yes, this is a common pattern called bit masking. Use your language's binary AND operator on the value corresponding to a given answer and the value submitted from the form to see if the given answer was one of the selected choices. For example, if the answer submitted and saved is 2689 as in your example, you can check whether "chest disease" was one of the selected choices by seeing if 2689 & 4 is nonzero. (& should be substituted with whatever the binary AND operator is in your language of choice.)

Note that this only works as long as all the values corresponding to individual choices are powers of 2. In general, the question posed in your title, about finding out what numbers from a given set have been added to come up with a given sum, is an instance of something called the knapsack problem and is only known to be solvable by checking every possible combination, which is very inefficient. (NP-complete, specifically)

Answer by atk for Finding out what numbers have been added to come up with a sum

Since all your numbers seem to be powers of two, you just need to store the input value in a long enough integer to hold it, then bit mask.

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  

Answer by SpacedMonkey for Finding out what numbers have been added to come up with a sum

You can find the values by ANDing with powers of 2.

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

You can find out the value of 2ⁿ using binary shifting like this: 1 << n

php like code:

$item[] = {"Allergy", "Cardiology", ..., "Diagnostic Tests (outside)"};  $answer = 2689;    for ( $power = 0; $power < count($item); $power++ ) {       if ( 1 << $power & $answer ) {         echo $item[$power] . "\n";     }  }  

Edit: made it more php friendly

Answer by User_allowed for Finding out what numbers have been added to come up with a sum

this will do exactly what you wanted :

Happy coding

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72