How do people come up with solutions to bitwise problems?

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.

2 answers

  • answered 2019-09-15 20:44 Acorn

    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 ;)

  • answered 2019-09-15 20:48 harold

    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.