0

I'm working on a component where I put in data and I get different data as a result. The input is always the same (3 Objects). From these 3 Objects up to 9 other Objects can be calculated. One calculation for each output Object is performed. Before the output data is calculated I want to set which of the 9 Objects shall be calculated.

  1. Set input data
  2. Set which output data shall be calculated
  3. Get Output data

I'm working in Visual C++ (C99). At the moment I'm facing a bit of a design problem here. After I set the input data, I am using a bit mask to configure which output data is supposed to be calculated.

const int  foo1 = 1;   //000000001
const int  foo2 = 2;   //000000010
const int  foo3 = 4;   //000000100
const int  foo4 = 8;   //000001000
const int  foo5 = 16;  //000010000
const int  foo6 = 32;  //000100000
const int  foo7 = 64;  //001000000
const int  foo8 = 128; //010000000
const int  foo9 = 256; //100000000

SetOutput(foo2 | foo4 | foo5 );

The data is held in an array ARRAY[9] . For those that have been set (foo2, foo4 and foo5) the elements contain valid data after the calculation (ARRAY[2], ARRAY[4], ARRAY[5])

I then want to get the the resulting data.

GetData(foo2);
GetData(foo4);
GetData(foo5);

My problem is how do I get the element index from the mask values foo2 = 2, foo4 = 8 or for example foo5 = 16?
The only possibility would be taking log2(n) and get 2, 3 and 4, which would be the correct element indexes of ARRAY.

Is there a simpler way than this? I thought about using a map instead, with the mask value (1,2,4,8...256) as key field and the calculated data in the value field. But would prefer to keep the static array. Thanks in advance!

  • 1
    @RobertHarvey with the map it is possible in O(1) isn't it? 1 -> 0, 2 -> 1, 4 -> 2, 8 -> 3 etc etc – gnat Jul 11 '16 at 19:48
  • 1
    Why do you need to go from bitmask bits to indices? Can you write the critical parts directly in terms of the indices, and apply a MASKIFY() operator to obtain individual bitmask bits when you need them? (Note: MASKIFY(n) is just (1 << (n)).) – John R. Strohm Jul 11 '16 at 19:54
  • 1
    @gnat: How is a math calculation not O(1)? – Robert Harvey Jul 11 '16 at 19:55
  • 1
    @gnat: I think we're saying the same thing. The difference is that log2(n) doesn't require another data structure at all. Think of it as a perfect hash calculation with no possible collisions. – Robert Harvey Jul 11 '16 at 20:04
  • 1
    Understand that O(1) is not necessarily equal to O(1). O(1) means time K1 * 1, while O(n) means time K2 * n. If K1 = 1,000,000 and K2 = 42, then O(1) is NOT preferable to O(n) for n < 25000. A traditional log2(x) requires quite a few floating-point operations, which tend to be expensive. – John R. Strohm Jul 11 '16 at 20:23
1

An array with 257 entries will be fast, portable, and again fast. Many compilers provide a very fast built-in function to count leading or trailing zero bits in a number, for example __builtin_clz in gcc and Clang, which is likely about hundred times faster than a call to the log2 function.

  • Good answer about using the array (+1), Would the anonymous downvoter care to state their case? – user949300 Jul 12 '16 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.