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

}
};
``````

#### 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;
stream << '1';
} else {
stream << '0';
}
car = 1;
}
// increment the index
i++;
}

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

### 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 ->  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) {
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]);
}
}
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 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;

}
};
``````