Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Demystifying bitwise operations, a gentle C tutorial

andreinc.net

Post reply on HN
Print view View original

31–40 of 95 posts

Re: Demystifying bitwise operations, a gentle C tutorial

#31

Post by flohofwoe »

cactusplant7374 wrote: post #10

I 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.

C23 finally introduces binary literals, e.g. you can write now "0b11110000" instead of "0xf0" for situations where binaries are more readable (but with a bit of 'training', hexadecimal works just as well).

Also, bitwise operations are essentially "SIMD for bits" and important down on the machine code level, it makes a lot of sense to have that same functionality also in higher level languages (unfortunately not all common bitwise instructions - like rotations - made it into high level languages).

(edited)

Re: Demystifying bitwise operations, a gentle C tutorial

#32

Post by zh3 »

Funnily 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 I found this upstream (paraphrased):-

    uint8_t tx_data[64];

    ....
    tx_data[43] = utime>>24;
    tx_data[44] = utime>16;
    tx_data[45] = utime>>8;
    tx_data[46] = utime;

Re: Demystifying bitwise operations, a gentle C tutorial

#33

Post by _a_a_a_ »

philiplu wrote: post #6

I 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 and he contacted Henry Warren with a possible addition for the forthcoming second edition, Morton curves (https://en.wikipedia.org/wiki/Z-order_curve) which are extremely simple to calculate, much more so than the space filling curve given in Hackers Delight, but which despite the author's interested response to us, did not go into the second edition. My colleague was very disappointed. Me too. Morton curves are just interlace-the-bits so would have slotted in so well.

Sadly there won't be a third edition as the author died.I found out when I contacted him to let him know his website was down (again!). His family let me know he had gone.

Re: Demystifying bitwise operations, a gentle C tutorial

#34

Post by zh3 »

whb07 wrote: post #18

I’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 ?

Nowaways you just write 'divout = divin/8192' and assume the compiler is going to do the right thing (and very possibly do something deeper than "divin>>12" at the assembler level).

Makes me wonder who pays attention to this sort of thing these days :)

Re: Demystifying bitwise operations, a gentle C tutorial

#35

Post by whateveracct »

tester756 wrote: post #23
detrites wrote: post #3

While it's based on C, a large chunk of the content is simply a great introduction to number representations in other bases such as binary and hexadecimal etc. Fundamental knowledge and very well explained, and a few insights I've not seen before.

>Fundamental knowledge yes? no? hard to say The number of times I've needed this knowledge during all years of formal education and then years of work would be probably around 3. Then I started working with C and close to hardware and it became something that I need everyday. It's feels like bit proficiency is only useful in some very specific domains. Thought: is HTTP foundational knowledge nowadays? after all whole…

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.

Re: Demystifying bitwise operations, a gentle C tutorial

#36

Post by dahfizz »

tester756 wrote: post #23
detrites wrote: post #3

While it's based on C, a large chunk of the content is simply a great introduction to number representations in other bases such as binary and hexadecimal etc. Fundamental knowledge and very well explained, and a few insights I've not seen before.

>Fundamental knowledge yes? no? hard to say The number of times I've needed this knowledge during all years of formal education and then years of work would be probably around 3. Then I started working with C and close to hardware and it became something that I need everyday. It's feels like bit proficiency is only useful in some very specific domains. Thought: is HTTP foundational knowledge nowadays? after all whole…

If you're a web developer and your product relies on HTTP, then HTTP is absolutely fundamental knowledge.

Similarly, if you're a web developer and your language doesn't even have integers, then understanding twos compliment is probably not fundamental.

That said, the people who proudly know the very least amount possible to perform their day job usually are not top performers.

Re: Demystifying bitwise operations, a gentle C tutorial

#37

Post by radicalbyte »

_a_a_a_ wrote: post #33
philiplu wrote: post #6

I 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…

I have the second edition, back around 2010 I made a bit of a splurge on books. Super handy when you need it; which in my case has only been one time. Don't spend much time on low-level code nowadays.

Re: Demystifying bitwise operations, a gentle C tutorial

#38

Post by zoomablemind »

zh3 wrote: post #32

Funnily 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…

       tx_data[44] = utime>16;
Good catch!

I wonder if this would have been flagged with -Wall?

Re: Demystifying bitwise operations, a gentle C tutorial

#39

Post by wg0 »

I'm trying to find some good resources or some book that covers modern C.

For everything else from Python to Golangz Rust and everything in between - there are tons of quality books and even their own documentation in some cases is pretty decent. But not so with C.

If you read this and have something, please share. Just C (not much interested in C++)

Re: Demystifying bitwise operations, a gentle C tutorial

#40

Post by edflsafoiewq »

zoomablemind wrote: post #38
zh3 wrote: post #32

Funnily 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…

tx_data[44] = utime>16; Good catch! I wonder if this would have been flagged with -Wall?

Nope. There's no warning for bool->int conversion: https://stackoverflow.com/questions/28716391/gcc-forbid-impl...
Post reply on HN