Bit Hacking (with Go code) | Hacker News Reader

Bit Hacking (with Go code)

lemire.me

111 pointsgus_leonel13 comments

The intro sentence, "At a fundamental level, a programmer needs to manipulate bits," gave me a strange moment of mental dissonance.

It just highlights to me how the job of "programmer" can be many things, depending on your domain. One could argue that a goal of programming is to build higher abstractions so you don't need to manipulate bits in order to express yourself.

But that aside, I enjoy this stuff, so here are some links for others interested:

* A neat SO post about implementing "popcount" using SWAR trickery: https://stackoverflow.com/questions/109023/count-the-number-...

* Good collections of bit hacks:

** https://graphics.stanford.edu/~seander/bithacks.html (also mentioned in the article's comments)

** http://aggregate.org/MAGIC/

> It just highlights to me how the job of "programmer" can be many things, depending on your domain.

Agreed, though I'd argue different languages entreat different kinds of knowledge. That's why there's value in having experience in many.

> One could argue that a goal of programming is to build higher abstractions so you don't need to manipulate bits in order to express yourself.

Could be; though I'd argue just because those abstractions are there, it's still good to know how and why they work. That reveals some things about the language which I think influences the subtle choices you make every day.

I think it depends on how you interpret "fundamental level." It sounds like you're more interpreting it in the sense of "what are the basic important things that a programmer needs to build on." But then I think there's an interpretation that also makes perfect sense: bits are the fundamental building blocks of which the programmer can manipulate.

Yes, I suppose it's a hardware/software divide, largely. Bits are how things are implemented in hardware typically, and programs need to run on hardware, so bits are relevant. But from a pure software POV, it shouldn't matter if it's bits or ternary[1] or something else; the software's purpose is to accomplish some higher-level task.

[1]https://en.wikipedia.org/wiki/Ternary_computer

Go doesn't differ a ton from other programming languages but there are definitely a couple of things. I think when it comes to bit manipulation, my favorite detail about Go is the built-in AND NOT operator, which also has a corresponding compound assignment operator. It's mentioned in here, but I think it's worth calling out: not all languages have it, but it's a good addition.

Another interesting little go difference (along with other newer languages like rust, but not c/c++/c#/java/javascript) is making equality lower precedence than bitwise operators, so that var & 1 == 0 tests the lowest bit of var, which makes it more convenient for bit hacking.

This feels natural now, but other languages inherited a decision dating back to B, when logical operators like && and|| didn't exist, and the bitwise forms were used in their stead.

I do generally appreciate the changes Go made to operator precedence: Go's operator precedence is the simplest to understand I've seen yet, and has the fewest surprises I've seen so far.

With that having been said, it has exactly one downside in my opinion: when porting C code, you really have to be careful sometimes. C has 15 or so levels of operator precedence, splitting similar operators into their own precedence, whereas Go has only 5 and they're always left-associative. Particularly tricky C code may actually make use of this to reduce redundant parentheses in ways that may not be entirely obvious... (especially when combined with implicit casting.)

Whenever I do quick expression language parsers for any reason, I always follow Go's operator design. It's very easy to implement and other than not matching C behavior, has less footguns.

Old guy here: funny how manipulating bits is worth a HN post nowadays :-D

The only part of it that screams "this decade" is Go, unless you're programs-on-a-punch-card old.

Interesting! Only yesterday I had to get back into the bits (actually treating integera as bits, using shift operations and masks and bitwise-and), for the purpose of implementing base64 encoding. Good to know how to do this kind of stuff.

This is a fun post. Simplifying a problem to a series go bitwise operations always feels strangely satisfying to me.

Bit tweaking is always fun. I have the need to implement a long bit array spanning multiple words recently and it gets surprisingly non-trivial quickly, especially dealing with subranges or searching for the next 0 or 1 bit from a starting position. But it's still loads of fun.

Implementing a bitset[0] in Go is a fun exercise if this article interested you.

[0] https://en.wikipedia.org/wiki/Bit_array

Reply on news.ycombinator.com