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!

tzippy
  • 147
  • 1
  • 4
  • `log2(n)` is about as simple as it gets. – Robert Harvey Jul 11 '16 at 19:42
  • 1
    @RobertHarvey with the map it is [possible in O(1)](http://programmers.stackexchange.com/a/250785/31260) isn't it? 1 -> 0, 2 -> 1, 4 -> 2, 8 -> 3 etc etc – gnat Jul 11 '16 at 19:48
  • @RobertHarvey Thanks! wanted to avoid the expensive double to int hassle tho... – tzippy Jul 11 '16 at 19:49
  • 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
  • @tzippy: That expense is almost certainly inconsequential, unless you're doing some sort of high-speed real-time lookup on equipment requiring nanosecond precision. Measure it and see. – Robert Harvey Jul 11 '16 at 19:56
  • @RobertHarvey there's no math, only map lookup: `map.get(fooN)` will give index corresponding to fooN, ie log(fooN) – gnat Jul 11 '16 at 19:58
  • @gnat: But `log2(n)` is math, and so is a hash calculation. – Robert Harvey Jul 11 '16 at 19:59
  • @RobertHarvey log2 is precalculated and is within map already. Lookup is O(1) [as explained here](http://programmers.stackexchange.com/a/250785/31260) isn't it – gnat Jul 11 '16 at 20:01
  • 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
  • @JohnR.Strohm I wanted to use bit masks so that I would only need one call `SetOutput` with one parameter. This parameter being the ORed bit masks. – tzippy Jul 11 '16 at 20:05
  • 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
  • [Fast function to compute log2 for 64 bit integers](http://stackoverflow.com/a/11398748/102937) – Robert Harvey Jul 12 '16 at 02:34
  • The approach seems backwards. The constants should be set to the offsets into the array. The bitmask can be manipulated by left shifting 1 by the constant. edit: Now that I see the rest of the posts I see that John R. Strohm and I agree. – dbasnett Jul 13 '16 at 13:17

1 Answers1

2

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.

gnasher729
  • 42,090
  • 4
  • 59
  • 119