[Leetcode]Bit Manipulation on Leetcode

Why Bit Manipulation

Recently I have finished cs144 TCP lab and found that I was not very confident about bit manipulation. My code prone to be buggy so I decided to do some leetcode exercise to refresh on my knowledge.

Bit Calculation

29. Divide Two Integers

Description

link: https://leetcode.com/problems/divide-two-integers/ Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Solution

Use substraction to simulate division, and this way we get truncating naturally. Be care about the overflow and negative results.

class Solution {
public:
    int divide(int dividend, int divisor) {
        bool is_negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);

        // Covnert to long to avoid overflow/underflow
        long a = dividend, b = divisor;

        // Convert to postive for simplification
        a = abs(a);
        b = abs(b);

        if(a < b) return 0;

        long res = 0, times = 1, cur_b = b;

        // Find the biggest multiples of b that is smaller than a
        while((cur_b << 1) <= a) {
            cur_b <<= 1;
            times <<= 1;
        }

        while(a >= b) {
            while(a < cur_b) {
                cur_b >>= 1;
                times >>= 1;
            }
            a -= cur_b;
            res += times;
        }

        if(is_negative) {
            res = -res;
        }

        if(res > INT_MAX) res = INT_MAX;
        if(res < INT_MIN) res = INT_MIN;

        return res;

    }
};

67. Add Binary

Description

Given two binary strings a and b, return their sum as a binary string.

Solution

Similar to add two numbers but in binary. Only need to take care of the carry digit.

class Solution {
public:
    string addBinary(string a, string b) {
        // reverse the string
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        ostringstream stream;

        // take the longer index
        int len = max(a.length(), b.length());
        int car = 0, i = 0;

        while(i < len || car != 0) {
            int dig_a = 0, dig_b = 0;
            if(i < a.length()) {
                dig_a = a[i] == '1' ? 1 : 0; 
            }
            if(i < b.length()) {
                dig_b = b[i] == '1' ? 1 : 0;
            }
            int added = car + dig_a + dig_b;

            // reset the carry digit
            car = 0;
            if(added == 1 || added == 3) {
                stream << '1';
            } else {
                stream << '0';
            }
            if(added >= 2) {
                car = 1;
            }
            // increment the index
            i++;
        }

        string res = stream.str();
        reverse(res.begin(), res.end());
        return res;
    }
};

Bitmask

78. Subsets

Description

https://leetcode.com/problems/subsets/ Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Solution

The number of subsets we have is 2^(size). We can view each number as a bitmask where 1 represents taking the element in the corresponding place. E.g.: input: [1,2,3] bitmask 101 -> [1,3] 001 -> [3] Then we can just iterate through 2^size to compute each subset.(Maybe easier to implement if we don't use bit manipulation...)

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        // Total number of subsets
        int subsets_num = (1 << nums.size()) - 1; 
        vector<vector<int>> res;
        // Compute each subset
        for(int i = 0; i <= subsets_num; ++i) {
            int bitmask = i;
            vector<int> cur;
            for(int i = 0; i < nums.size(); ++i) {
                bool is_taken = bitmask & 1 == 1;
                if(is_taken) {
                    cur.push_back(nums[i]);
                }
                bitmask >>= 1;
            }
            res.push_back(cur);
        }
        return res;
    }
};

89. Gray Code

https://leetcode.com/problems/gray-code/

Solution

Brute force(backtrack)

class Solution {
public:
    vector<int> grayCode(int n) {

        // range 0 ~ (1 << n) - 1
        // brute forcely flip one bit for the current number
        // try to build the vector using this pattern
        int limit = 1 << n;

        // Initialize the data structure we need
        unordered_set<int> set;
        for(int i = 1; i < limit; ++i) set.insert(i);
        vector<int> res;
        res.push_back(0);

        backtrack(set, res, n);
        return res;
    }

    bool backtrack(unordered_set<int>& set, vector<int>& res, int n) {
        if(set.empty()) return true;
        int last = res[res.size() - 1];
        for(int i = 0; i < n; ++i) {
            int bitmask = 1<<i;
            int cur = last ^ bitmask;
            if(set.count(cur)) {
                set.erase(cur);
                res.push_back(cur);
                if(backtrack(set, res, n)) {
                    return true;
                }
                set.insert(cur);
                res.pop_back();
            }
        }
        return false;
    }
};

Gray code is deterministic:https://en.wikipedia.org/wiki/Gray_code

class Solution {
public:
    vector<int> grayCode(int n) {

        vector<int> res;
        for(int i = 0; i < (1 << n); ++i) {
            res.push_back(i^(i>>1));
        }

        return res;

    }
};