How do people come up with solutions to bitwise problems?

Question

I'm curious as to how people come up with solutions to bitwise problems. For reference, I'm a computer engineering major that graduates this semester. I have take discreet math, digital logic design, digit electronics, and other classes involving using boolean algebra / bitwise operations. However, I'm still not too sure how people come up with solutions to bitwise problems. Here is an example problem:

Reverse bits of a given 32 bits unsigned integer.

Input: 00000010100101000001111010011100

Output: 00111001011110000010100101000000

Here is a solution in C++:

class Solution {

    # define NUM_BITS 32
public:
    uint32_t reverseBits(uint32_t n) {

        uint32_t result = 0;

        for (int i = 0; i < NUM_BITS; i++) {
            if (n & (1 << i)) {
                result |= (1 << ((NUM_BITS - 1) - i));
            }
        }

        return result;
    }
};

This is actually a Leetcode question. In this problem, I know why a for loop iterating from 0 to 31 is a good idea, we're dealing with a 32 bit integer, but the conditional statement and the operation is what confuses me:

     if (n & (1 << i)) {
       result |= (1 << ((NUM_BITS - 1) - i));
     }

I understand what is going on here, but I don't know how this is derived. Using a truth table of some sort ? How can someone come up with this in an interview ? I can understand if someone got paper and pencil and took a few hours to find this out, but in general I'm curious as to how people come up with these solutions.

The process for me at least, in any problem (not just specifically to bitwise operations) is first to think of a solution in a practical way - how you would check that yourself, and than try to implement it with tools that I have such as bitwise operations for this instance. Bottom line is it takes some thinking and people's mind vary, so something that's easier for you is harder for someone else and the other way around. but practice will make you better always. — prophet-five, Sep 15 '19 at 20:47
Its iterating through bits and whenever 1 is found, setting 1 on the mirrored position. Just as a pseudo code is written. — huseyin tugrul buyukisik, Sep 15 '19 at 20:48
I usually start by doing the problem "as a human" before translating that to code. So if someone said to you to reverse the bits of input and write them down, then you'd probably read the bits one by one and write the output backwards by hand. And that becomes your for-loop in code. And then you need to work out how to test each bit of the input, which is where the horrible bit-shift code comes from. — Hitobat, Sep 15 '19 at 20:56
Persistence really. I remember discovering on my own how to test if a number is a power of two. It took me a whole page of writing bits and manually doing bitwise operations to finally figure it out. I stubbornly refused to look it up until I had done it and when I looked it up, there it was: already an [answer](https://stackoverflow.com/a/600306/2089675) on SO. You just have to look for patterns. I'm still interested in finding if primes have a pattern when looked at from other bases. That would be dope to see — smac89, Sep 15 '19 at 20:56
Why isn't this just a function? The class wrapper and saving the return value as state seems pointless. — doug, Sep 16 '19 at 02:24
I don't think this is on-topic, but this is **not** subjective. It however is a topic that makes more sense on CSE (Computer Science Educators). In short, this sort of questions work at interviews because it proves experience. However, it proves only experience with this sort of question, and that is generally not a real job skill. — MSalters, Sep 16 '19 at 11:04

Acorn · Answer 1 · 2019-09-15T20:49:55.680

The same way as with any other math/technical/skill-related problem: experience solving similar problems (mostly).

Ask yourself how you learnt to solve non-trivial integrals early in your degree. You will find you needed to do a lot of them to get intuition on how to approach the problem (rather than trying blindly).

_{By the way, if you manage to answer this question fully, you may have solved artificial general intelligence ;)}

score 1 · Answer 2 · answered Sep 15 '19 at 20:48

These sort of simple approaches can be found by looking at integers as simple arrays of booleans.

You can start with thinking about the algorithm as if you literally had an array of booleans, then change indexing into the array with the simple bitwise snippets for test-kth-bit, set-kth-bit, etc.

That approach doesn't lead to advanced solutions though.

How do people come up with solutions to bitwise problems?

2 Answers2