2 ms·
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 sea
by 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 agoI'm curious how often you get people who know what POPCNT is with that question.
- JohnFen 3y agoI 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]