Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I like the fact that the C language lets you use binary arithmetic in an explicit way in your code, sometimes the use of the binary arithmetic can also give you a little edge in terms of performance; but since I started studying C++ i can't really tell how much i have seen the explicit use of something like that in a C++ code, something like a pointer to pointer structure or an instruction for jumping to a specific index value through the binary arithmetic.

Is the binary arithmetic still important and relevant in the C++ world? How i can optimize my arithmetic and/or an access to a specific index? What about the C++ and the way in which the bits are arranged according to the standard?

... or i have taken a look at the wrong coding conventions ... ?

share|improve this question
8  
going to binary arithmetic is a micro optimization and (often) needlessly complicates code, go for readable code and let the compiler optimize it as it sees fit –  ratchet freak Jun 25 '12 at 12:25
6  
..and before you consider micro-optimizing, can you prove that this is the slowest part of your code? –  JBRWilkinson Jun 25 '12 at 14:00
1  
Use binary arithmetic for what, exactly? Can you be more specific? C++ includes all the same arithmetic operators that C has, and it's fine to use them. However, C++ gives you a lot of tools that let you work at a higher level than C. So, please provide some examples of the kinds of things you're talking about. –  William Shakespeare Jun 25 '12 at 16:14
8  
Today, C compilers are smart enough to optimize a*2 into a<<1 where appropriate. There's no need to refer to that as "the C style" - that is really more "the low-level assembly coder from the 1980s writing C" style. (Also, these days, mul is generally just as fast as shl, and in some cases could be faster. Don't try to out-optimize the compiler based on possibly-antiquated knowledge.) –  fluffy Jun 25 '12 at 18:55
3  
@user827992: Using the shift operators to multiply/divide by 2 is not quicker in either language. micro optimization like this are already done by the compiler and it does a much better job at it than you can. The only thing you can do is screw up the ability of the compiler to see an optimization so concentrate on writting clean code and doing things the compiler can't do (design good code). –  Loki Astari Jun 25 '12 at 19:01

9 Answers 9

up vote 22 down vote accepted

In short: No, it is not any good to use "binary arithmetic"(in sense the question asks it) or "C style" in C++.

What makes you believe bitwise arithmetic would be any faster really? You can throw your bitwise operations all over the code, but what would make it any faster?

The thing is, almost whatever trivial thing you're trying to solve, can be solved easier by the standard high-level features(including the standard library, STL and STL algorithms). In some specific cases you might indeed want to switch the individual bits, for example when working with bitmasks. Or storing very compact data, for example when writing a compression algorithm, a dense file format or working for example with embedded systems.

If you are concerned with performance, always write a simple and trivial algorithm first. Just make it work. Then, measure the time your algorithm takes with typical input. Now, if you at this point feel that it is too slow, only then you can try optimizing it by hand with these "bitwise arithmetic" tricks. And after done, measure if your code is any faster. The chances are that it is not, unless you really know what you are doing in that specific situation/case.

Frankly, the best way to understand about this kind of low-level constructs which deal with performance is to study assembly language. It really makes you realize that no, writing some bit-manipulating wizzcode is not any faster than using that sort(begin(v),end(v)). Just because you operate at low level doesn't mean you operate fast. In general, Algorithms are more important than implementation details!

Basically whatever the "C style" means, please, stay away from it when writing C++. They are two completely different languages. Don't mix them.

Bjarne Stroustrup gave a great talk about C++ style in Microsoft's GoingNative 2012 conference this February, please take a look: http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style

Especially the parts between around 10 and 15 minutes are great, when he talks about old C-style code compared to modern C++ style.

share|improve this answer
2  
"Algorithms > implementation details" - rubbish! Equally important. Watch this: youtube.com/watch?v=aMnn0Jq0J-E –  James Jun 25 '12 at 15:14
1  
Yes, (mostly) rubbish. Some algorithms and data structures (radix sort, tries, etc.) are efficient because they exploit binary representation. –  zvrba Jun 25 '12 at 15:17
3  
@James Of course, you can twist the statemet to not hold true in specific cases, for example for given input size N optimized merge sort can be faster than non-optimized quicksort and if you always keep your input under/at most N, it's no use to use that unoptimal implementation ofquicksort because your fast merge sort outperforms it in your typical usage scenarios. The trick is to pick the most optimal algorithm + implementation available for the certain input size. This process begins with picking the most efficiet algorithm first, then the most efficient implementation. –  zxcdw Jun 25 '12 at 16:48
1  
@zvrba I am definitely not suggesting that low-level bitwise trickery doesn't matter or that it shouldn't be exploited where it can. What I am saying is that I believe that in most cases there is actually no need to go "low-level". The same can be achieved by staying high, and using what the language gives you. For example, don't write your ultra-optimized inline-asm Quicksort, because the STL algorithm sort() is, with high probability, way faster. The bottom line is to first rely on what's available(e.g. standard library) and only then rely on tailored special-purpose low-level stuff. –  zxcdw Jun 25 '12 at 16:53
2  
@zxcdw: While algorithms can be efficient on paper the physical characteristics of what executes that algorithm can make a lot of difference. –  James Jun 25 '12 at 17:36

I make use binary arithmetic is virtually ALL computer languages I've programmed with. For example, take the addition operator +:

int sum = x + y; // compiler probably implements this as binary arithmetic!

I would find it hard to program in a language that did not support arithmetic, and I would find it hard to believe that arithmetic operations were not implemented by your compiler/interpreter using binary arithmetic (such as using base-10 arithmetic).

http://en.wikipedia.org/wiki/Arithmetic#Arithmetic_operations

http://www.binarymath.info/

http://www.swarthmore.edu/NatSci/echeeve1/Ref/BinaryMath/BinaryMath.html

TL;DR: Use the right terminology (bitwise ≠ binary), else you get pendatic answers like this.

share|improve this answer

Sometimes several flags are crammed into a single byte to save space. Sometimes it's premature, other times critical.

Microsoft SQL Server will store multiple columns of data type "bit" in the same byte. In this case it's not a premature optimization. You save 2 to 8 times the disk space, for 2 to 8 bit columns (this is a big deal). You get faster searches as well (very big deal). It's also more likely you will be able to cache a set of data in memory. This is perfect. Since there is no benefit in indexing binary data, you might as well pack the bits together. And the bitwise nature is not exposed to client programmers so everyone is happy.

The windows API crams several options per byte. You manipulate the display options with bitwise operations. I would say this one was premature. It also made many people give up on windows programming. But the programmers who wrote the API came from the old days when space was severely limited. At the time it may have been a good idea to design an API around bitwise manipulation.

Client/server video games love to pack multiple flags in a byte. For example, on the server the game calculates your damage. It will send back the display data to the client, with several flags like if it was a critical hit, if it killed the enemy, etc. The display would then process with bitwise operations. This is debatable whether it's premature or not. But I would lean towards saying less is more when pushing data over a network.

share|improve this answer

Follow these steps:

  1. Write the code as simple and clear as possible.
  2. Turn on all compiler optimizations.
  3. Consider whether you have sufficient knowledge about the specific target CPU and its instruction set (assembler). If not, then you will probably have a hard time to do any manual optimizations and should probably not attempt it, as you will likely just end up obfuscating the code for no gain. Also note that manual optimization is only necessary if your compiler has poor support for the specific target platform. As an alternative, you could try another compiler.

  4. Identify performance bottlenecks. How to find them depends on the target system. In "high-level" programs such as desktop programming, you benchmark your code through specific tools designed for that purpose, or through OS API functions. On "low-level" programs such as embedded systems, you typically use an oscilloscope to measure realtime performance. On any program, you can disassemble the code and see what the compiler actually came up with.

  5. If there are no bottlenecks that affects your program's performance, you don't need to do a thing and you can stop reading here.
  6. If there are bottlenecks that have impact on your program, you may need to perform manual optimization.
  7. How do manual optimizations depends on the target CPU, there is no universal trick. Common things to look for are: floating point arithmetic, alignment, integer sizes, division, branch prediction & instruction cache handling, use of needlessly complex library functions... and so on.
share|improve this answer
    
And don't forget to mention that this approach is valid for C or C++ or any other compiled language. –  Doc Brown Jun 26 '12 at 14:34

As many have mentioned already, be aware — do not to prematurely optimize things. But when you find CPU-bound code that is a bottle neck, one of the best ways to understand which of your alternate implementations would be better, using Clang C/C++ -> LLVM IR is a great idea. If you're more comfortable in a web browser, try http://llvm.org/demo/.

The IR (Intermediate Representation) generated by Clang and LLVM are virtual machine instructions. You can for instance write the same algorithm/arithmetic function in "C style" and "C++ style" (I'm guessing "STL-style"?) and compare the IR generated by the compiler. Even if your end-product compiler isn't based on LLVM, the IR code will be representative of what code is actually generated and compiled. Beyond IR there is only hardware optimizations (like how landing pads from conditional branches are implemented). LLVM can produce target machine assembly, if you think it would make you wiser (but I wouldn't recommend going beyond IR).

share|improve this answer

for example the shift operator << or >>, which is a quick way to calculate "something times 2" or "something divided by 2"

Whether you're working in C or C++, write what you mean. Write foo = foo * 2; or foo *= 2; if that's what you mean, not foo = foo << 1;. Let the compiler take care of finding the fastest instruction to use and don't confuse the people who have to read your code with unnecessary hand optimization.

share|improve this answer
2  
This is great advice. One example would be taking a modulo power-of-two of value V. e.g. V%32. The compiler will optimize it by using the AND -1-trick, doing V&31(only works for modulo power-of-two!). Also often times compiler can do lots of (perhaps non-obvious) tricks even during the compilation. For example multiplying a compile-time constant by another, the compiler can just compute the immediate value and replace the expression with that. This is called constant folding. The bottom line is that compiler often knows how to micro-optimize. ;) –  zxcdw Jun 26 '12 at 9:27
    
@zxcdw: If one wants a proper modulus, and V might be negative, I would consider V & 31 superior to any equivalent using %. If C had a proper mod operator, I might regard V mod 32 as being better yet, but no such feature exists. –  supercat Mar 26 at 20:04

It depends on what sort of C++ code you're writing. The lower you are the more relevant it becomes. The problem with these types of questions is that everyone can only rely on their own experience and so if someone has never had to do this sort of thing they can't see why someone else might need to do it.

Here's Joel's 'Five Worlds' article

share|improve this answer

No, there is no use of binary arithmetic in C++, except one "tiny" detail: the C++ standard defines the language semantics in terms of a binary abstract virtual machine that must use either 1st complement, 2nd complement or sign-magnitude integer representation.

share|improve this answer

Binary arithmetic is bound to the implementation. You must be careful about implementation details such as endianness. Therefore, using binary operators isn't automatically faster than using elementary operators. Often, the compiler will perform more relevant optimizations, and a natural code can be better for performance as well as easier to read for both the compiler and the programmer.

Of course, there are some cases (such as Base64 encoding), where you must use those operators. But optimizing code with binary operators should be the last optimization, coming after perfecting your algorithms. For personal programming, some pretty tricks (like this) may be faster, but with serious programming, readability should come first.

And, like zxcdw said, C and C++ are both very different languages. C++ has more high-level libraries, so binary tricks are less famous.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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