[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;
}
};