5 ms·

Bit Hacking (with Go code)

111 points by gus_leonel 3y ago

interroboink 3y ago
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-of-set-bits-in-a-32-bit-integer/109025#109025 https://stackoverflow.com/questions/109023/count-the-number-... * Good collections of bit hacks: ** https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html (also mentioned in the article's comments) ** http://aggregate.org/MAGIC/ http://aggregate.org/MAGIC/
- kodah 3y ago
  > 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.
- bitshiftfaced 3y ago
  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.
  - interroboink 3y ago
    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 https://en.wikipedia.org/wiki/Ternary_computer
zelphirkalt 3y ago
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.
ungerik 3y ago
Old guy here: funny how manipulating bits is worth a HN post nowadays :-D
- mike_hock 3y ago
  The only part of it that screams "this decade" is Go, unless you're programs-on-a-punch-card old.
bryancoxwell 3y ago
This is a fun post. Simplifying a problem to a series go bitwise operations always feels strangely satisfying to me.
shaftoe444 3y ago
Implementing a bitset[0] in Go is a fun exercise if this article interested you. [0] https://en.wikipedia.org/wiki/Bit_array https://en.wikipedia.org/wiki/Bit_array
jchw 3y ago
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.
- pfedak 3y ago
  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.
  - jchw 3y ago
    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.
ww520 3y ago
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.

111 points by gus_leonel 3y ago

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-of-set-bits-in-a-32-bit-integer/109025#109025 https://stackoverflow.com/questions/109023/count-the-number-... * Good collections of bit hacks: ** https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html (also mentioned in the article's comments) ** http://aggregate.org/MAGIC/ http://aggregate.org/MAGIC/

kodah 3y ago
> 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.
bitshiftfaced 3y ago
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.
- interroboink 3y ago
  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 https://en.wikipedia.org/wiki/Ternary_computer

zelphirkalt 3y ago

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.

ungerik 3y ago

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

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

bryancoxwell 3y ago

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

shaftoe444 3y ago

Implementing a bitset[0] in Go is a fun exercise if this article interested you. [0] https://en.wikipedia.org/wiki/Bit_array https://en.wikipedia.org/wiki/Bit_array

jchw 3y ago

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.

pfedak 3y ago
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.
- jchw 3y ago
  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.

ww520 3y ago

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.