0

I've a sum build of 0 up to 3 specific decimal numbers that can build 8 different sums:

  100      ---      100      ---      100      ---      100      ---
  200      200      ---      ---      200      200      ---      ---
+ 400    + 400    + 400    + 400    + ---    + ---    + ---    + ---
-----    -----    -----    -----    -----    -----    -----    -----
  700      600      500      600      300      200      100        0

The decimal numbers are scaled by doubling the next smaller number starting at a specific offset. They might be for example in the following sets instead:

  • { 300, 600, 1200, ..}
  • { 7, 14, 28, ..}

It is possible to figure out if a specific number is added by simply dividing by the offset and then running a bitmask check:

(sum / offset) & 1 == true if the first decimal number is added.
(sum / offset) & 2 == true if the second decimal number is added.
(sum / offset) & 4 == true if the third decimal number is added.

Is there any faster algorithm than that?

BTW: Since this is not exactly bitmasking how is it called instead? Decimal masking? Decimal sum multiplexing? Bitmasking with offset? Sum masking? WTF bit masking?

Sebastian Barth
  • 4,079
  • 7
  • 40
  • 59
  • Why is it "not exactly bitmasking"? Once you divide by 100, you've got a 3-bit value, and you're using the bitwise-AND operator after all. – Pointy Jul 09 '16 at 13:45
  • It's called "counting 0 bits". Have a look at [Fast computing of log2 for 64-bit integers](http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers) – Bergi Jul 09 '16 at 14:38

0 Answers0