Hacker News Reader

Comment by erksa | Hacker News Reader

Does anyone have any reading material on introduction to where bit-wise programming becomes important knowledge? Is it mostly just used in game-dev?

They've always peaked my interest, but never personally had to work with it, and just don't know the use cases where these become important!

View on HN

The general use-case is "high-performance and/or embedded systems." Games, and especially console games, happen to check both of those boxes. Another high-perf case is financial systems (eg: high-frequency trading). Other embedded systems would include things like robotics, automotive software, audio synthesizers and processing, etc.

Packing data into bits is a space optimization. On modern processors, accessing memory is hideously slow compared to doing logical operations, so if you can pack more info into fewer bits, you get higher information density, and need to access main RAM less often. Thus, it speeds things up, sometimes dramatically.

Sorry, I don't have reading material per-se.

But just as an anecdotal example: I was using some of this trickery to implement a densely-packed Quadtree using Morton Codes. Morton Codes interleave the bits of the X and Y coordinates for a cell on a grid. So, in order to break a M-Code apart and combine them back together, you need to "select the even bits" or "select the odd bits", which can be done with some tricks like these.

(aside: it's "piqued" :)

Thank you for the thorough break down. All the replies have immediately framed my "understanding" much more.

I'm not exactly sure why, but I'm very intrigued nonetheless.

Aside: TIL, Thanks!

I don't know of any formal introductions to the topic but you can see them in action in these places too

* some of Daniel Lemire's work in high performance data structures

* the blog posts related to solving board games on https://nullprogram.com

* the articles about board representations on the chess programming wiki https://www.chessprogramming.org/Main_Page

* Any explanation of Quake III's fast inverse square root

Thanks for the resources, these are great! As an avid chess fan I've always played around with the idea of trying making a basic chess engine.. This might just be the push!!

Most obvious use case I can think of is embedded programming, e.g. when you're setting control registers.

In embedded programming it can be useful to control an animation on an LED matrix since a lot of LED drivers and multiplexers enable pins based on the bits passed through their respective drivers. Example of how you might animate 8 LED connected to 8 pins:

You could turn that into an array to animate an LED going from left-to-right or you could just write a simple function that bit-shifts your current state to the right.

It's also useful in scrolling text: Imagine that 8x8 above contains a character like O. You could animate the O moving to the left by shifting the bits in each row to the left by one over and over again (according to whatever speed you've defined).

Thanks man, this was a very clear explanation!

Anywhere that a byte/word/dword is used as a first class data structure, there is likely some operation on the data structure that can be accomplished with a bit trick. As others have said, this is most often the case where CPU cycles are tightly constrained.

Not an answer to your exact question, but there's:

https://graphics.stanford.edu/~seander/bithacks.html

And if you like that, there's an entire book full of them, which is delightful:

https://www.amazon.ca/Hackers-Delight-2nd-Henry-Warren/dp/03...

Interacting with hardware registers, such as in a device driver, is another common use case.

or implementing file formats / network protocols

Maybe what danbruc commented [0] may be of interest for you.

[0]: https://news.ycombinator.com/item?id=34055831

Thanks!

You end up needing this stuff to write fast parsers of text formats, but you need a bunch of other stuff too, and there isn't really any introductory material online.

If you're writing a standard library from scratch, they can be important in data structure or algorithms that are expected to be in hot loops.

When dealing with networking it's extremely common.

NETWORKS. All use cases apply.

Reply on news.ycombinator.com