4 ms·

I'm one of those new programmers. I'll sometimes do low level dev, but I don't use bitwise operations much. I guess I just don't recognise where they're useful.

by _1rth 3y ago

I'm one of those new programmers. I'll sometimes do low level dev, but I don't use bitwise operations much. I guess I just don't recognise where they're useful. I'm always a bit awed when people chain a few for massive speedups. How can I learn?

gumby 3y ago
Read a lot of code and work with someone who does that kind of thing. Also you might want to brush up on math and algos: a lot of this "skill" is really just thinking about what the actual computation is. And that just comes from experience.
- JohnFen 3y ago
  Heh, that is probably more useful advice than the freaking essay I wrote in response.
  - dmvdoug 3y ago
    False. Your freaking essay was a great read for me. But I’m not a developer/programmer, just a very interested outsider.
JohnFen 3y ago
I've been doing this from well before the internet was a thing, so I'm not actually familiar with good online resources to help. But I can give very general search suggestions. I tend to think of there being two classes of problems that are addressed at the bitwise level. The first is optimization and the second is hardware control. The techniques the two use are rather different. Optimization is a tricky topic, because you can't always get great gains there though bitwise operations, but when you can, the gains can be huge. This is because (for compiled languages) modern compilers tend to be very good at this sort of optimization and will do things in very efficient way to begin with. You taking the bits into your own hands aren't likely to improve on them. Also, there are processors where certain optimizations don't apply. For example, shifting a value one bit to the left is the same as multiplying by 2, and to the right is the same as dividing by 2. In many processors, the bit shift is much faster than the multiplication operation, so there's a win to be had there. In others, however, there is not such a huge speed difference. It all depends. In terms of hardware control, what you want to know is more obvious: what is the most efficient way to work with single or small groups of bits? What's the fastest way to count bits? That sort of thing. As an aside -- where I currently work, one of the interview problems is to have the applicant write code that counts how many bits are set in a word. Even high-level programmers will generally know how to do this -- but the method they use tells you a lot about the focus of their training and skillset. Bonus points if you can say why this is a useful thing to do, and what the Big O for your method is. In any case, I would suggest reading up on Boolean algebra to start to get a handle on this stuff. If you want to really wow people (at least ones who aren't graybeards), then a fun trick is to learn to model things (system states, whatever) as boolean networks (linking together AND, OR, XOR, etc. "gates" that result in a desired truth table), then use Karnaugh maps to reduce the network to the smallest possible number of components. I learned this as a way of reducing component counts in digital logic circuits, but I still find use for them to this day in purely software applications and often get called a wizard for being able to produce complex decision-making code that is very fast. The price you pay, of course, is that such code is not easy to follow for the poor souls who have to work with it later.
- AlotOfReading 3y ago
  I'm curious how often you get people who know what POPCNT is with that question.
  - JohnFen 3y ago
    I don't actually know, but recently an applicant did this and it caused a bit of stir (in a good way). It changed the role the applicant was being considered for. The language to be used for the exercise is intentionally not specified (even pseudocode is fine), so more often with younger applicants you see them using Python and doing it using high-level methods. Not the best approach for that kind of problem, but it also tells us something -- that applicant is probably better suited for our AI teams than our embedded systems teams.
- deleted 3y ago
  [deleted]
schoen 3y ago
You could consider doing a form of NAND to Tetris: https://www.nand2tetris.org/ https://www.nand2tetris.org/ https://www.nandgame.com/ https://www.nandgame.com/ (The NAND Game is having you build the same stuff as NAND to Tetris, but you do it visually as circuit block diagrams, rather than writing a textual description of how the circuits would connect up. It also doesn't include the elaborate details of why you're building each thing, although since it's the same content and sequence as NAND to Tetris, you could read the book or listen to lectures while doing the NAND game to get more context.) Alternatively, read Code: The Hidden Language of Computer Hardware and Software by Charles Petzold. A very bit-oriented book! These suggestions might be controversial because they start bottom-up rather than top-down -- they're not really asking "how does the stuff that you already use work at a lower level?" but more like "suppose that we had logic circuits and math; what could we do with those that would eventually allow us to have computer systems?". Some people might advocate trying to find a way to experiment with things that are more closely connected to what you already do with computer programming. Alternatively, you could do some kind of cryptography class or tutorial, as those extensively use bitwise operations (although the only one that is likely to be explained is XOR, because XOR mixes two bit sequences in a reversible way, which makes it natural for use in encryption and decryption).
- deleted 3y ago
  [deleted]

by _1rth 3y ago

gumby 3y ago

Read a lot of code and work with someone who does that kind of thing. Also you might want to brush up on math and algos: a lot of this "skill" is really just thinking about what the actual computation is. And that just comes from experience.

JohnFen 3y ago
Heh, that is probably more useful advice than the freaking essay I wrote in response.
- dmvdoug 3y ago
  False. Your freaking essay was a great read for me. But I’m not a developer/programmer, just a very interested outsider.

JohnFen 3y ago

I've been doing this from well before the internet was a thing, so I'm not actually familiar with good online resources to help. But I can give very general search suggestions. I tend to think of there being two classes of problems that are addressed at the bitwise level. The first is optimization and the second is hardware control. The techniques the two use are rather different. Optimization is a tricky topic, because you can't always get great gains there though bitwise operations, but when you can, the gains can be huge. This is because (for compiled languages) modern compilers tend to be very good at this sort of optimization and will do things in very efficient way to begin with. You taking the bits into your own hands aren't likely to improve on them. Also, there are processors where certain optimizations don't apply. For example, shifting a value one bit to the left is the same as multiplying by 2, and to the right is the same as dividing by 2. In many processors, the bit shift is much faster than the multiplication operation, so there's a win to be had there. In others, however, there is not such a huge speed difference. It all depends. In terms of hardware control, what you want to know is more obvious: what is the most efficient way to work with single or small groups of bits? What's the fastest way to count bits? That sort of thing. As an aside -- where I currently work, one of the interview problems is to have the applicant write code that counts how many bits are set in a word. Even high-level programmers will generally know how to do this -- but the method they use tells you a lot about the focus of their training and skillset. Bonus points if you can say why this is a useful thing to do, and what the Big O for your method is. In any case, I would suggest reading up on Boolean algebra to start to get a handle on this stuff. If you want to really wow people (at least ones who aren't graybeards), then a fun trick is to learn to model things (system states, whatever) as boolean networks (linking together AND, OR, XOR, etc. "gates" that result in a desired truth table), then use Karnaugh maps to reduce the network to the smallest possible number of components. I learned this as a way of reducing component counts in digital logic circuits, but I still find use for them to this day in purely software applications and often get called a wizard for being able to produce complex decision-making code that is very fast. The price you pay, of course, is that such code is not easy to follow for the poor souls who have to work with it later.

AlotOfReading 3y ago
I'm curious how often you get people who know what POPCNT is with that question.
- JohnFen 3y ago
  I don't actually know, but recently an applicant did this and it caused a bit of stir (in a good way). It changed the role the applicant was being considered for. The language to be used for the exercise is intentionally not specified (even pseudocode is fine), so more often with younger applicants you see them using Python and doing it using high-level methods. Not the best approach for that kind of problem, but it also tells us something -- that applicant is probably better suited for our AI teams than our embedded systems teams.
deleted 3y ago
[deleted]

schoen 3y ago

You could consider doing a form of NAND to Tetris: https://www.nand2tetris.org/ https://www.nand2tetris.org/ https://www.nandgame.com/ https://www.nandgame.com/ (The NAND Game is having you build the same stuff as NAND to Tetris, but you do it visually as circuit block diagrams, rather than writing a textual description of how the circuits would connect up. It also doesn't include the elaborate details of why you're building each thing, although since it's the same content and sequence as NAND to Tetris, you could read the book or listen to lectures while doing the NAND game to get more context.) Alternatively, read Code: The Hidden Language of Computer Hardware and Software by Charles Petzold. A very bit-oriented book! These suggestions might be controversial because they start bottom-up rather than top-down -- they're not really asking "how does the stuff that you already use work at a lower level?" but more like "suppose that we had logic circuits and math; what could we do with those that would eventually allow us to have computer systems?". Some people might advocate trying to find a way to experiment with things that are more closely connected to what you already do with computer programming. Alternatively, you could do some kind of cryptography class or tutorial, as those extensively use bitwise operations (although the only one that is likely to be explained is XOR, because XOR mixes two bit sequences in a reversible way, which makes it natural for use in encryption and decryption).

deleted 3y ago
[deleted]