# Bit Manipulation

###### tags: `LeetCode筆記`

## :memo: 一、The basics of bit manipulation

### Meaning of Base


### Commonly used bases

decimal has 10 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Binary has two digits: 0, and 1.
Octal has eight digits: 0, 1, 2, 3, 4, 5, 6, and 7.
Hexadecimal has sixteen digits: in addition to 0 to 9, there are A, B, C, D, E, and F, corresponding to 10, 11, 12, 13, 14, 15 in decimal, respectively.

### Conversion between bases

* Decimal to non-decimal:


* Conversion between other bases

a binary number:
101110010(2)
in groups of three as 101|110|010, to 562(8) in octal
in groups of four as 1|0111|0010, to 172(16) in hexadecimal

## :memo: 二、Representing integers in computer

### Binary in computer

* 1-byte number, i.e., 8 digits binary number with 2^8 possible values
* 2-byte number, i.e., 16 digits binary number with 2^16 possible values
* 4-byte number, i.e., 32 digits binary number with 2^32 possible values
* 8-byte number, i.e., 64 digits binary number with 2^64 possible values

### Signed and unsigned integers

* The value range of signed integers includes negative integers, zero and positive integers, while the value range of unsigned integers only includes zero and positive integers, without negative integers;
* Using the same number of bits, the maximum value that a signed integer can represent is half smaller than that of an unsigned integer;
* For k-bit integers, the range of signed integers is -2^(k-1) to 2^(k-1) - 1.
* The value range of an unsigned integer is 0 to 2^k - 1.

### The original code, inverse code, and complement code

***Original code***
The original code is the sign bit of the machine number plus the absolute value of the truth value of the machine number.
The highest bit is the sign bit, and the remaining bits represent the value.

***Inverse code***
The inverse code of non-negative numbers is the same as the original code.
The inverse of negative numbers is to flip every bit of the original code **except the sign bit.** Flip means changing 0 to 1 or changing 1 to 0.
* The original code of +10 is 00001010, and the inverse code is 00001010.
* The original code of −10 is 10001010, and the inverse code is 11110101.

***Complement code***
The complement code is obtained from the inverse code.
The complement code of non-negative numbers is the same as the original code and the inverse code.
The complement of negative numbers is obtained by adding 1 to the inverse code.
The original code of +10 is 00001010, the inverse code is 00001010, and the complement code is 00001010;
The original code of −10 is 10001010, the inverse code is 11110101, and the complement code is 11110110.

### Representation in computer

The complement code solves both the subtraction error and dual representation of 0 problem.
Moreover, one more minimum value can be represented. In complement code, there is no −0.

## :memo: *三、Concepts and properties of bitwise operators

### Overview of Bit Operations
There are six types of bit operations, namely: AND, OR, XOR, negation, left shift, and right shift.

### AND, OR, XOR, and Negation
AND:
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
OR:
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
XOR:
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0
Negation:
∼ 0 = 1
∼ 1 = 0



### Properties of bitwise operations

Bit operations have many properties. Here, we will list common properties of AND, OR, XOR, and negation in bit operations. We assume that the variables below are all signed integers.

* Idempotent law: a & a = a, a | a = a (note that XOR does not satisfy the idempotent law);
* Commutative law: a & b = b & a, a | b = b | a, a ⊕ b = b ⊕ a;
* Associativity: (a & b) & c = a & (b & c), (a | b) | c = a | (b | c), (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c);
* Distributive Law: (a & b) | c = (a | c) & (b | c), (a | b) & c = (a & c) | (b & c), (a ⊕ b) & c = (a & c) ⊕ (b & c);
* De Morgan's Law: ∼ (a & b) = (∼a) | (∼b), ∼ (a | b) = (∼a) & (∼b);
* Negative operation properties: -1 = ∼0, -a = ∼(a−1);
* AND operation properties: a & 0 = 0, a & (-1) = a, a & ( ∼a) = 0;
* OR operation properties: a | 0 = a, a | (∼a) = −1;
* XOR operation properties: a ⊕ 0 = a，a ⊕ a = 0;
* Other properties: The result of a & (a−1) is to change the last 1 in the binary representation of a to 0; The result of a & (-a) (equivalent to a & (∼(a−1))) is to keep only the last 1 of the binary representation of a, and set the remaining 1s to 0. Using these properties, many bit operation problems can be solved strategically.

## :memo: Base 7 (Easy)
Given an integer num, return a string of its base 7 representation.


### 作法
檢查是否num==0，再分正數負數去解

class Solution {
public:
    string convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        string ans = "";
        if (num >= 0) {
            while (num > 0) {
                ans += to_string(num % 7);
                num = num / 7;
            }
            reverse(ans.begin(), ans.end());
        }
        else {
            int num_abs = abs(num);
            string temp = "";
            while (num_abs > 0) {
                temp += to_string(num_abs % 7);
                num_abs = num_abs / 7;
            }
            reverse(temp.begin(), temp.end());
            ans += '-';
            ans += temp;
        }
        
        return ans;
    }
};

## :memo: Convert a Number to Hexadecimal (Easy)
Given an integer num, return a string representing its hexadecimal representation. For negative integers, two’s complement method is used.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

Note: You are not allowed to use any built-in library method to directly solve this problem.



### 作法
直接用一個unsigned int n去把num轉成沒有符號的int，接著做法和轉binary一樣

class Solution {
public:
    string toHex(int num) {
        string str = "";
        unsigned int n = num;   //converting -ve no. to +ve no.

        if (num == 0) {  //edge_case
            return "0";
        }        
            
        while (n != 0) {
            int rem = 0;
            char ch;

            rem = n % 16;
            if (rem < 10) {
                ch = rem + 48;  //ASCII(0)==48
            }                
            else {
                ch = rem + 97 - 10; //ASCII(a) == 97
            }             
            str += ch;
            n /= 16;
        }
        
        int i = 0, j = str.size() - 1;
        while (i < j) {
            swap(str[i], str[j]);
            i++;
            j--;
        }

        return str;
    }
};

## :memo: Number of 1 Bits (Easy)
Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).


### 作法
直接用**uint32_t**去算有幾個1，n = n >> 1往左移1個位數

**uint32_t**要記起來->存32位元的數

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int times = 0;
        int ans = 0;

        while (times < 32) {
            if (n % 2 == 1) {
                ans++;
            }
            n = n >> 1;
            times++;
        }
        
        return ans;
    }
};

## :memo: Reverse Bits (Easy)
Reverse bits of a given 32 bits unsigned integer.
**Input:**
n = 00000010100101000001111010011100
**Output:**
964176192 (00111001011110000010100101000000)
**Explanation:**
The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

### 作法

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        int times = 0;
        
        while (times < 32) {
            ans = ans * 2 + n % 2;
            n = n >> 1;
            times++;
        }
        
        return ans;
    }
};

## :memo: *Sum of Two Integers (Medium)
Given two integers a and b, return the sum of the two integers without using the operators + and -.

### 作法
背誦

class Solution {
public:   
    int getSum(int a, int b) {
        long mask = 0xFFFFFFFF;
        
        while (b != 0) {
            int answer = (a ^ b) & mask;
            int carry = ((a & b) & mask) << 1;
            a = answer;
            b = carry;
        }
        
        return a < INT_MAX ? a : ~(a ^ mask);
    }
};

## :memo: *Gray Code (Medium)
Given an integer n, return any valid n-bit gray code sequence.


### 作法 Iteration with a single loop
**Algorithm**
1. Initialize sequenceLength variable to 2^n. sequenceLength denotes the total number of elements present in the Gray code sequence.
2. Run a for loop for i = 0 to 2^n.
* At each iteration calculate the next number to be added in the sequence using the formula G(i) = i ⊕ (i>>1) and assign it to num.
* Add num to the result.
3. Return result list.

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        // there are 2 ^ n numbers in the Gray code sequence.
        int sequenceLength = 1 << n;
        
        for (int i = 0; i < sequenceLength; i++) {
            int num = i ^ i >> 1;       // shift先運算
            result.push_back(num);
        }
        
        return result;
    }
};

## :memo: Bitwise AND of Numbers Range (Medium)
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.


### 作法 Bit Shift

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        
        // find the common 1-bits
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        
        return left << shift;
    }
};

### 作法 Brian Kernighan's Algorithm


class Solution {
  public int rangeBitwiseAnd(int m, int n) {
    while (m < n) {
      // turn off rightmost 1-bit
      n = n & (n - 1);
    }
    return m & n;
  }
}

## :memo: Counting Bits (Easy)
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.


### 作法 慢

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans;
        ans.push_back(0);
        
        for (int i = 1; i <= n; i++) {
            int count = 0;
            int num = i;
            while (num > 0) {
                if (num % 2 == 1) {
                    count++;
                }
                num /= 2;
            }
            ans.push_back(count);
        }
            
        return ans;    
    }
};

### 作法 快

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

        vector<int> v(n + 1);
        
        v[0] = 0;
        for (int i = 1; i <= n; i++) {
            int num = i, one = 0;
            if (num % 2 == 1) one = 1;
            v[i] = one + v[num / 2];            
        }
        
        return v;
    }
};

## :memo: Single Number 題型

## 1. Single Number (Easy)
Given a **non-empty** array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.


### 作法 Bitwise Operators: XOR

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        
        for (int n : nums) {
            ans ^= n;
        }
        
        return ans;
    }
};

## 2. Single Number II (Medium)
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.


### 作法 Bitwise Operators: NOT, AND and XOR

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int seenOnce = 0;
        int seenTwice = 0;
        
        for (int n : nums) {
            seenOnce = ~seenTwice & (seenOnce ^ n);
            seenTwice = ~ seenOnce & (seenTwice ^ n);
        }
        
        return seenOnce;
    }
};

## 3. Single Number III (Medium)
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.


### 作法 Two bitmasks





class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long bitmask = 0;
        for (auto num : nums) {
            bitmask ^= num;
        }
        
        long long diff = bitmask & (-bitmask);
        
        int x = 0;
        
        for (auto num : nums) {
            if ((num & diff) != 0) {
                x ^= num;
            }
        }
        
        return {x, static_cast<int>(bitmask ^ x)};
    }
};

## :memo: Maximum Students Taking Exam (Hard)


### 作法

class Solution {
    int f[1 << 8][8];  // the student distribution, row
    int n, m;
    vector<vector<char>> seats;
    
    // this bit is on
    bool on(int bit, int mask) {
        return (1 << bit) & mask;
    }
    
    bool checkRowValid(int row, int mask) {
        for (int i = 0; i < m; i++) {
            // if a student is put on a broken chair
            if (on(i, mask) && seats[row][i] == '#') return false;
            // if there is a student on the left of this student
            if (i > 0 && on(i - 1, mask) && on(i, mask)) return false;
            // if there is a student on the right of this student
            if (i < m - 1 && on(i + 1, mask) && on(i, mask)) return false;
        }
        return true;
    }
    
    bool checkTwoRowCollision(int mask, int nmask) {
        for (int i = 0; i < m; i++) {
            // if there is a student on the upper left
            if (i > 0 && on(i, nmask) && on(i - 1, mask)) return false;
            // if there is a student on the upper right
            if (i < m - 1 && on(i, nmask) && on(i + 1, mask)) return false;
        }
        return true;
    }
    
public:
    int maxStudents(vector<vector<char>>& seats) {
        n = seats.size();
        m = seats[0].size();
        memset(f, 0, sizeof(f));
        this->seats = seats;
        int ans = 0;
        
        // initialization
        for (int mask = 0; mask < (1 << m); mask++) {
            if (checkRowValid(0, mask)) {
                f[mask][0] = __builtin_popcount(mask);
                ans = max(ans, f[mask][0]);
            }
        }
        
        for (int row = 0; row < n - 1; row++) {
            for (int mask = 0; mask < (1 << m); mask++) {
                // the current row of students has to be valid
                if (!checkRowValid(row, mask)) continue;
                
                // generate each next row and check correctness
                for (int nmask = 0; nmask < (1 << m); nmask++) {
                    // first it has to be valid
                    if (!checkRowValid(row + 1, nmask))
                        continue;
                    // then it has to not collide with former row
                    if (!checkTwoRowCollision(mask, nmask))
                        continue;

                    f[nmask][row + 1] = max(f[nmask][row + 1], f[mask][row] + __builtin_popcount(nmask));
                    ans = max(ans, f[nmask][row + 1]);
                }
            }
        }
        
        return ans;
    }
};

## :memo: Missing Number (Easy)
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.


### 作法 Bit Manipulation
#### **Intuition**
We can harness the fact that XOR is its own inverse to find the missing
element in linear time.
#### **Algorithm**
Because we know that nums contains n numbers and that it is missing
exactly one number on the range [0..n-1], we know that n definitely
replaces the missing number in nums. Therefore, if we initialize an integer
to n and XOR it with every index and value, we will be left with the
missing number. Consider the following example (the values have been sorted
for intuitive convenience, but need not be):

#### **Explantion**
missing = 4\^(0\^0)\^(1\^1)\^(2\^3)\^(3\^4)
= (4\^4)\^(0\^0)\^(1\^1)\^(3\^3)\^2 **//** 交換律
= 0\^0\^0\^0\^2 **//** (a XOR a = 0)
= 2 **//** (0 XOR a = a)


class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int missing = nums.size();

        for (int i = 0; i < nums.size(); i++) {
            missing ^= i ^ nums[i];
        }

        return missing;
    }
};

### 作法 Gauss' Formula \[Accepted\]

算出1到n的總和以及nums的加總
消失的數字一定是1到n的總和減去nums的加總
1+2+3+4+5+6+7+8+9
1+2+3+4+5+6+9+7(-
\-\-\-\-\-\-\-\-\-\-\-\-
8

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int expectedSum = nums.size() * (nums.size() + 1) / 2;
        int actualSum = 0;

        for (int num : nums) {
            actualSum += num;
        }

        return expectedSum - actualSum;
    }
};