C# Solution with explanation


  • 1
    L
    public int RangeBitwiseAnd(int mVal, int nVal) {
        uint m = (uint) mVal;
        uint n = (uint) nVal;
        
        // Base case when m == n
        if (m == n || n == 0) {
            return (int)n;
        }
        
        // First of all we need to find the first most significate bit
        // flipped on in the gratest number
        uint bitmask = 0x80000000;
        uint result = 0x0;
        while(bitmask != 0) {
            uint nValue = n & bitmask;
            if (nValue != 0x0) {
                // We found the bit
                break;
            }
            
            // Shift right
            bitmask = bitmask >> 1;
        }
        
        // No we need to look at both m and n and find the first position
        // where there is a mismatch
        while (bitmask != 0) {
            uint nValue = n & bitmask;
            uint mValue = m & bitmask;
            
            if (nValue != 0x0) {
                // The bit in n is 1
                if (mValue != 0x0) {
                    // The bit in m is also flipped
                    // It means it will stay the same when adding values to m to reach n, so it
                    // will be flipped in the result AND
                    result = result | bitmask;
                } else {
                    // The bit in m is not flipped
                    // It means that to reach m at some point this will be flipped and all the
                    // subsequent bits will be 0 during one of the additions (which clears out all
                    // the bits in the AND)
                    // To convince yourself, look at this:
                    // n:= hhhhzz1rrrrrrr
                    // m:= kkkkzz0qqqqqqq
                    // While adding to m to reach n, we will hit this combination at least
                    //     kkkkzz10000000
                    // Which clears out everything else.
                    return (int)result;
                }
            }
            
            // The bit in n is 0
            // We do not check if we have a match in m since that could not be possible
            // othermise m is greater than n
            // We just do nothing here except moving the bitmask
            bitmask = bitmask >> 1;
        }
        
        return (int)result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.