20 bit operations programmers should know(pixelstech.cn)
pixelstech.cn
20 bit operations programmers should know
http://www.pixelstech.cn/article/1355943192_20_bit_operations_programmers_should_know
9 comments
I don't think these 'quick intro to bitwise operations' and/or 'cool bitwise operation tricks' articles ever go into enough detail to be safe.
Bitwise operations can be _extremely_ useful, but it's surprisingly difficult to use them in a correct and portable way. I have no idea where you can go to learn all the intricacies involved.
One killer that's always listed is "divide an int by 2: n >> 1" with no reference to how it behaves differently than the "/" operator (bitwise rounds towards negative infinity, / rounds towards zero). It's not incorrect, but that detail can be extremely important.
Bitwise operations can be _extremely_ useful, but it's surprisingly difficult to use them in a correct and portable way. I have no idea where you can go to learn all the intricacies involved.
One killer that's always listed is "divide an int by 2: n >> 1" with no reference to how it behaves differently than the "/" operator (bitwise rounds towards negative infinity, / rounds towards zero). It's not incorrect, but that detail can be extremely important.
Even the first one (Get maximum int value) is just plain wrong.
Although int has a 32 bit size on almost all systems it is only guaranteed to have a size of 16 bits.
The correct way of getting the size of int is including limits.h ( <climits> ) and looking at the value INT_MAX.
Although int has a 32 bit size on almost all systems it is only guaranteed to have a size of 16 bits.
The correct way of getting the size of int is including limits.h ( <climits> ) and looking at the value INT_MAX.
Do you (or anyone else) have a good source for someone who wants an introduction to bit operations?
http://graphics.stanford.edu/~seander/bithacks.html
Entertaining book: http://www.amazon.co.uk/Hackers-Delight-2nd-Edition-ebook/dp...
The reference: http://www.amazon.co.uk/The-Computer-Programming-Vol-Combina... Section 7.1.3 Bitwise Tricks and Techniques
Entertaining book: http://www.amazon.co.uk/Hackers-Delight-2nd-Edition-ebook/dp...
The reference: http://www.amazon.co.uk/The-Computer-Programming-Vol-Combina... Section 7.1.3 Bitwise Tricks and Techniques
Thanks!
It's unclear what language that is. Could that be (well-defined) Java?
Besides, it's also wrong because left shifting a signed integer "into the sign bit" is undefined.
Besides, it's also wrong because left shifting a signed integer "into the sign bit" is undefined.
Author is apparently trying to combine multiple languages.
Maybe well defined in java, definitely not in C.
In the original Chinese article, the languages were actually mentioned. And the one we're discussing is C++. (And so as you point out, wrong.)
It annoys me that this kind of vacuous article is posted. It reminds me of an old rant about Perl tutorials: http://blogs.perl.org/users/mithaldu/2011/10/perl-tutorials-...
It annoys me that this kind of vacuous article is posted. It reminds me of an old rant about Perl tutorials: http://blogs.perl.org/users/mithaldu/2011/10/perl-tutorials-...
#14 (calculating 2^n), is usually implemented as:
return 1 << n;
I, honestly, don't think these things are a good idea, bitwise operations make your code unreadable. Moreover there are simple, perfectly readable implementations of operations 1 to 17 that everyone recognizes in a second. With the operations 18 to 20 I agree since you may need them in an authorization system, but that's it. One more argument against these would be the fact that we're no longer in the 20th century and we cannot squeeze optimizations out of simple operations which are already optimized at the CPU level.
Bit operations are a great way to store multiple datas in one place (you still have to limit yourself to 32 true/false flags though).
My latest use has been to store (multiple) categories of an item in a database in a single spot and do a quick search through bit operations (instead of joining to another table to fetch relations between item and categories).
My latest use has been to store (multiple) categories of an item in a database in a single spot and do a quick search through bit operations (instead of joining to another table to fetch relations between item and categories).
While the techniques described here are academically interesting, don't expect your code to run magically faster if you use them in practice. I once benchmarked the performance of the "common version" of #9 implemented in C compared to swapping using a temporary variable like so:
int tmp = a; a = b; b = tmp;
It turned out that the bitwise swap was slower. In other words this sort of "clever" bit-level hack does not necessarily translate to higher performance.
And I would recommend the first chapter of "Matters Computational" written by Jörg Arndt, which includes many more advanced bitwise operations: http://www.jjj.de/fxt/#fxtbook. This book is more like a cookbook rather than an introductory book.
EDIT: debugged!
int tmp = a; a = b; b = tmp;
It turned out that the bitwise swap was slower. In other words this sort of "clever" bit-level hack does not necessarily translate to higher performance.
And I would recommend the first chapter of "Matters Computational" written by Jörg Arndt, which includes many more advanced bitwise operations: http://www.jjj.de/fxt/#fxtbook. This book is more like a cookbook rather than an introductory book.
EDIT: debugged!
bit ops are a really great way to obfuscate the intent of your code and most compilers strength reduce stuff anyway (and are probably smarter than you at it)
They also tend to have subtle differences in semantics compared to the "usual" way of doing things so beware.
They also tend to have subtle differences in semantics compared to the "usual" way of doing things so beware.
Looks pretty cool.
Except if I wasn't using bit operations on a day to day basis, I wouldn't understand any of this "magic".
Okay sure, "programmers should know", yadda, yadda,... What about some of us who just don't know because they didn't go through C and don't know what is an integer?
Sue me, but until three years ago when I began being taught C, back when I only used ActionScript, JavaScript and PHP, I had no idea a number was "a suit of bits" and not just "a number". Same goes for linked-lists, binary trees,...
Not trying to "dumb down" HN, but let's not assume everyone knows everything.
Except if I wasn't using bit operations on a day to day basis, I wouldn't understand any of this "magic".
Okay sure, "programmers should know", yadda, yadda,... What about some of us who just don't know because they didn't go through C and don't know what is an integer?
Sue me, but until three years ago when I began being taught C, back when I only used ActionScript, JavaScript and PHP, I had no idea a number was "a suit of bits" and not just "a number". Same goes for linked-lists, binary trees,...
Not trying to "dumb down" HN, but let's not assume everyone knows everything.
Some people are pointing out undefined behavior involving shifts. I agree it's pretty egregious. (Also, how can you hardcode 31 in a bunch of places, make a statement like "if you don't know how many bytes an int is" - and not mention sizeof!)
But there's a special place in hell reserved for this:
> (a) ^= (b) ^= (a) ^= (b);
This is undefined because ^= is not a sequence point.
I feel like the title of this should be "how to demonstrate lack of C knowledge".
But there's a special place in hell reserved for this:
> (a) ^= (b) ^= (a) ^= (b);
This is undefined because ^= is not a sequence point.
I feel like the title of this should be "how to demonstrate lack of C knowledge".
1.3, 2.2: wrong, shifting by negative number is undefined behavior
2.1: wrong, relies on some specific behavior for signed integer overflow
4, 5, 6, 7, 10, 11, 12, 17.1, 18: wrong, shifting negative numbers is implementation-defined behavior
Some examples will also suffer from integer overflow if the type 'int' is changed to something bigger (because then 1<<n could overflow, you'd need .e.g (uint64_t)1<<n).