Home C++ Page 4 - Bitwise Operators in Action

# Bitwise Operators in Action

Whether we like it or not, our society is money-oriented. Earning money takes time, and time has its limits; none of us has more of it. So if you want to maximize what you're earning, you must improve your speed. Bitwise operators may not always be the best choice for this, but in some cases relying on them will pay off quite handsomely.

Author Info:
By: Gabor Bernat
Rating:  / 2
March 03, 2009

SEARCH DEVARTICLES

Bitwise Operators in Action - In Algorithms
(Page 4 of 4 )

Because bitwise operators speed up an algorithm, they can be used for obtaining better run times for complex but otherwise slow algorithms. Of course, if we are smart enough we may also benefit much more. A good example is the problem of the minimum number of queens required on a chess board to cover every square.

At first the only solution we can come up with is the backtrack technique (if you aren’t familiar with it please find the articles written by Barzan "Tony" Antal because he authored an excellent one on this topic; you should find it here on Dev Articles). However, this is agonizingly slow, which is typical of a backtrack algorithm.

The problem with the “backtrack” method is that we need to find, first, the solution that covers it with n pieces (n x n board) then n-1 and so on. This leaves us with too many options to think about, and many of them are in vain. The key to an optimal algorithm is using bitwise operators. First we need to observe that if we put a queen on the chess board, that will cover the square on the horizontal, vertical, main diagonal, and the secondary diagonal also.

Also if we put another queen on the board, that will cover its own squares in the same manner, and the sum of the two will be what they cover. So for a square on the board we only need to know if that square is covered or not. That is a single 0 or 1 (bool —true or false). And why should we bother with first finding a way to cover n and so on? Wouldn’t be much faster if we start from the other direction, namely with first one piece, then with two, and so on until the n-th piece?

Despite the fact that this approach wasn’t possible with pure backtracking, this will change once we apply bitwise operators. Let’s store in an integer (or a couple of them) which squares cover a single queen, then start to combine them until we find a good solution. Combining the territory of two queens on the board is a piece of cake with the bitwise “or” operator.

For example, on a 4x4 board, if we have a queen on the (0,2) places, the board will look like this:

And this can be translated into a binary number like this: 1100 1111 0100 0010. Generate this for all positions and start to combine them. First use only one piece, then two and so one. Once you get all of them you are ready. Bitwise or the pieces, and when all of the bits are 1 (or as is more commonly said the value will be -1) you are done.

Sadly enough, for the combination a “backtrack algorithm” must be used, but even this way, this approach this will be much faster than any other implementation. I have already written the code; it works well for a number less than 10. For something beyond that the combination generation is too slow. Feel free to look into it; the code is heavily commented so you can comprehend it fully.

Here is a link to the code; download it, make a project for it and compile it or just run the exe if you want to see how it works:

Speaking of the results, here they are for ten. As you can see, it needs more and more time to run the generation of combinations. Imagine if we were to start from the other end, how much slower it would then turn out to be!

The End

Throughout this two-part article series you have learned all that is to be known about bitwise operators, so you can decide if you want to use them or not. While I introduced you to the bitwise operators in the first part, the purpose of this segment was to present their usage.

Of course, there are many more algorithms where a bitwise operator can be used, for instance when you want to sort a really long list that has unique members (like the population of America – because the personal numeric number is unique for each person). Also you can resolve the modulo 2^n in a fast and efficient way, but I’ll let this be homework for you to consider.

Thank you for your interest and reading my article. You may also read other interesting articles throughout the entire Dev Shed Network or just place your questions and doubts here in the blog comments area, or make the effort to sign up with the friendly community on Dev Hardware forums and post your questions there. We’ll do our best.

Have a great day!

 DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.