what's the most efficient way in c++ to break a bool array into an int array

Question

I have a function where the input and output are bool arrays (longer than the simple example). Internally the function works on fixed length integers (i.e. integers that are exactly 12 bits or 7 bits, ...). So the first step is to convert the input bool array into an equivalent int array. Here's an example :

 bool bits[10*12];
 unsigned int ints[10];

 for(int k=0;k<10;k++)
  {
   x=1;
   t=0;
   for(int b=0;b<12;b++)
   {
    t+=x*bits[k*12+b];
    x*=2;
   }
   ints[k]=t;
 }

which converts an input array of 120 bits to an int array with 10 entries, each being 12 bits. This works fine but I'd like to see if there are more efficient ways of doing this.

The speed of light is a fundamental limit of our shared universe. It cannot be exceeded without violating the laws of physics. Similarly, if one has an array of 120 values that must be checked, nothing can be done other than checking each one of those 120 values, without violating the same laws of physics. Even if some micro-optimizations are possible here, modern multi-Ghz CPUs will make the result of any micro-optimization mostly academic. — Sam Varshavchik
– Sam Varshavchik, Commented Jun 1, 2022 at 21:56
10 ints, even on 16 bit platforms, have 160 bits, plenty of room for 120 bools, @DrewDormann — Sam Varshavchik
– Sam Varshavchik, Commented Jun 1, 2022 at 21:58
you can definitely replace multiplication by shifts, also move calculation of k*12 out of the loop — Iłya Bursov
– Iłya Bursov, Commented Jun 1, 2022 at 22:01
When you profile your (supposedly) more efficient way, make sure you enable the optimizer to compare the performance of the given implementation against the performance of the (supposedly) better implementation. In compilers these days, the optimizer is surprisingly good. — Eljay
– Eljay, Commented Jun 1, 2022 at 22:05
You also might want to consider using std::bitset instead of rolling your own. It's hard to be completely sure if it's what you need given that we don't know the reason why you're doing this. en.cppreference.com/w/cpp/utility/bitset — Donnie
– Donnie, Commented Jun 1, 2022 at 22:14

Goswin von Brederlow · Accepted Answer · 2022-06-01 22:05:46Z

1

You have to look at every single bit at least once. There is no way around it. So the most efficient way is O(n) where n is the number of bits.

Your algorithm is O(n). Congratulations.

The only way to be more efficient is to not need a conversion at all. Why don't all your code work with 12bit ints?

Or did you maybe want more performant code instead of more efficient?

answered Jun 1, 2022 at 22:05

Goswin von Brederlow

12.4k2 gold badges27 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

unknown Over a year ago

The internal code uses the 12 bit integers to access look up tables...so skipping the conversion is probably not an option.

Barmar Over a year ago

What distinction are you implying between "performant" and "efficient"? IMHO they're equivalent. Efficiency is more than just Big-O complexity, coefficients matters for real-world solutions.

Goswin von Brederlow Over a year ago

Efficiency is about the theoretical resource usage (e.g. memory or time) of an algorithm for an input n, especially how it changes as n changes. So it's very much about Big-O notation. On the other hand performance is about the practical side. When you benchmark something you measure the performance. How long does it actually take for a specific input? Coefficients matter for the performance, not the efficiency. en.wikipedia.org/wiki/Algorithmic_efficiency

unknown Over a year ago

@GoswinvonBrederlow I should have been more explicit...I want the code to run as fast as possible

Goswin von Brederlow Over a year ago

Have you profiled your code? is the conversion even a problem? Why do you need an array of bool instead of e.g. vector<bool> or bitset? 120 bit fit in 2 uint64_t and your conversion can just be a view into those. The most speedup you can get is by not doing things.

Collectives™ on Stack Overflow

what's the most efficient way in c++ to break a bool array into an int array

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related