[dead]
Demystifying bitwise operations, a gentle C tutorial
61–70 of 95 posts
Re: Demystifying bitwise operations, a gentle C tutorial
#62I suppose the online list of hacks at the 1st reference in the OP [1] makes more sense, but I've got a fondness for the book "Hacker's Delight", which I've owned and browsed for many years now [2]. And checking on that, I see there was a 2nd edition issued 10 years ago. Hmm, might need to pick that up. [1] https://graphics.stanford.edu/~seander/bithacks.html [2] https://en.wikipedia.org/wiki/Hacker's_Delight
There are quite a lot of bit hacks on the web, but Hackers Delight is where it took off for me.It was a massive eye-opener, what was possible and even better doing it the old-fashioned way. The second book is very, very heavy on division and as such it's not really as much 'fun' as the original, however I'd still recommend it! I shared the original Hackers delight with a work colleague, who had a mathematical bent an…
The second book is very, very heavy on division and as such it's not really as much 'fun' as the original, however I'd still recommend it!
What do you mean by this? Did they merely add a ton of information on division? Or did they take out the 'fun' bits from the original and replace them with division stuff?
Re: Demystifying bitwise operations, a gentle C tutorial
#63I don’t understand why bit masking and manipulation is so popular when it makes the code impossible to read. I like using Ruby, string, and pack and unpack.
Do Ruby's pack and unpack routines let you access a field smaller than a byte? What about a field that is split across a byte boundary?
I agree that bit masking and manipulation is hard to read and can be misused by ego-driven programmers. But the "popularity" because because bit masking and manipulation are both fundamental to computer science and an absolute necessity in certain situations.
Re: Demystifying bitwise operations, a gentle C tutorial
#64The graphics are impressive. Specifically, I've never seen someone fold a "bit surface" in half like that. I've also never seen a ladder view. Assuming Andrei Ciobanu himself posted this, how did you come up with those views? Bored on a Friday night?
Re: Demystifying bitwise operations, a gentle C tutorial
#65Funnily enough just spent a day tracking down a weird problem in an embedded system - some event timestamps were getting corrupted in a weird way. The pattern wasn't obvious until in desperation I dumped them in hex and found the second MSB was toggling between 0 and 1 (whereas it should have been been part of a count sequence). That told me exactly where to look - where the count was re-assembled from four bytes and…
This is one case where lining up values (and surrounding operators with spaces) can be good practice: tx_data[43] = utime >> 24; tx_data[44] = utime >> 16; tx_data[45] = utime >> 8; tx_data[46] = utime >> 0; Or even: tx_data[43] = utime >> (3 * 8); tx_data[44] = utime >> (2 * 8); tx_data[45] = utime >> (1 * 8); tx_data[46] = utime >> (0 * 8);
Yep. Bugs like this just pop out at you this way.
Having spent a lot of time digging into C code and doing microcontroller programming professionally, I have learned a certain disdain for the practice of using minimal whitespace in expressions, and the related practice of minimising LOC using C's very dense expressions syntax(unary dec/inc operators, the fact that assignment is itself an expression, etc).
The dense expressions syntax is pretty much a holdover from the time C was invented by Dennis Ritchie for the purpose of porting Unix; when it had to be typed on a painfully slow electromechanical teletype. This is also why most Unix commands are 2-4 characters long.
But it serves very little meaningful purpose today. It's important to remember that you might be able to turn 3 lines of code into 1, but it'll still be the same amount of machine code. And it will probably be harder to read, harder to change, and harder to reason about. And it can be a lot easier to miss some edgecase or even a typo like in this case. I have seen such a silly amount of off-by-one errors in C code due to some subtle misuse of unary increment/decrement that I stopped using those operators altogether. They don't improve your software in any meaningful way.
Re: Demystifying bitwise operations, a gentle C tutorial
#66Earlier quoted context omitted.
Nope, code was clean with -Wall on arm-9 compiler (i.e. gcc). Interesting thought now you say that (no warning) - only found it because of seeing the pattern (apropos the article) and from that having a good idea what was causing it (knowing the int was assembled a byte at a time). If I had a criticism of modern compilers, it's the blizzard of uninteresting warnings ("strncmp takes const char star, did you really mea…
All warnings are uninteresting until they're not. > ("strncmp takes const char star, did you really mean to pass it unsigned char star") This warning (with a different function) actually saved my bacon once, pointing me to a very obscure bug in the code. My practice is to use -Wall and make sure that the code compiles without any warnings at all. Then I don't have a deluge of warnings to wade through.
Remember -Wall isn't all. -Wall -Wextra is the new -Wall.
I recommend asan too, where possible.
Re: Demystifying bitwise operations, a gentle C tutorial
#67Earlier quoted context omitted.
All warnings are uninteresting until they're not. > ("strncmp takes const char star, did you really mean to pass it unsigned char star") This warning (with a different function) actually saved my bacon once, pointing me to a very obscure bug in the code. My practice is to use -Wall and make sure that the code compiles without any warnings at all. Then I don't have a deluge of warnings to wade through.
Remember -Wall isn't all. -Wall -Wextra is the new -Wall. I recommend asan too, where possible.
Oh, you're right. I need to update my build system.
Re: Demystifying bitwise operations, a gentle C tutorial
#68Earlier quoted context omitted.
I think if you work with UUIDs, it's worth learning about bitwise stuff. So backend developers in general. It's not a day-to-day skill, but it is one I've used at just about every job in the last decade to elegantly and efficiently solve hard problems regarding idempotency and randomness.
When would you want to perform bitwise operations on a UUID?
A UUID is a bunch of bit fields packed together: the version/variant, and depending on the version, fields for the datetime, MAC address, node ID, etc. You'd use bit ops to both construct and extract the fields.
Re: Demystifying bitwise operations, a gentle C tutorial
#69I’ve found significant code in c/c++ where bitwise operations are done for things like division etc by shifting a certain way. I Can imagine in the past, this was “faster”, yet clang/gcc can emit the same by just writing a basic A/B function. Seems the win goes to readability by reducing some of these old school hacks. What say you, greybeards ?
If x is signed and happens to be negative, x/16 will round one way, and x>>4 another. x/16 can still be implemented more performantly than a general division with unknown (or even known but non power of two) denominator, but it will be marginally slower than a plain shift. It depends on which semantics you desire.
Re: Demystifying bitwise operations, a gentle C tutorial
#70Funnily enough just spent a day tracking down a weird problem in an embedded system - some event timestamps were getting corrupted in a weird way. The pattern wasn't obvious until in desperation I dumped them in hex and found the second MSB was toggling between 0 and 1 (whereas it should have been been part of a count sequence). That told me exactly where to look - where the count was re-assembled from four bytes and…
This is one case where lining up values (and surrounding operators with spaces) can be good practice: tx_data[43] = utime >> 24; tx_data[44] = utime >> 16; tx_data[45] = utime >> 8; tx_data[46] = utime >> 0; Or even: tx_data[43] = utime >> (3 * 8); tx_data[44] = utime >> (2 * 8); tx_data[45] = utime >> (1 * 8); tx_data[46] = utime >> (0 * 8);
I've done the >> 0 thing to make it very clear what's going on, but I hadn't considered the * 8 construction. That's actually easier to comprehend at a glance because the numbers become less "magic". (8 and 16 are obvious to me, but 24 always has me second-guessing myself somewhere in the back of my mind)