劍指offer15.二進制中1的個數
題目鏈接
題目：編寫一個函數，輸入是一個無符號整數（以二進制串的形式），返回其二進制表達式中數字位數為 ‘1’ 的個數（也被稱為 漢明重量).）。
思路一：最樸素的想法，每次判斷最低位是否為1，然后進行統計，判斷完右移一位。
通過代碼：
class Solution {
public:int hammingWeight(uint32_t n) {int res = 0;while(n > 0){if(n & 1)res++;n >>= 1;}return res;}
};
思路二：還可以更快。觀察這個運算：n & (n?1)，其預算結果恰為把n的二進制位中的最低位的1變為0之后的結果。
通過代碼：
class Solution {
public:int hammingWeight(uint32_t n) {int res = 0;while(n > 0){n &= n - 1;res++;}return res;}
};
劍指offer16.數值的整數次方
題目鏈接
題目：實現pow(x, n) ，即計算 x 的 n 次冪函數（即，$ x^n $）。
思路：快速冪。不過需要注意負數的處理。由此引出另一個問題，-2^31轉換為正數后是超過int的范圍的，需要用long long。
通過代碼：
class Solution {
public:double quickPow(double x, long long n) {double res = 1.0;while(n > 0){if(n & 1){res *= x;n--;}x = x * x;n >>= 1;}return res;}double myPow(double x, int n) {if(n < 0)return 1.0 / quickPow(x, -1 * (long long) n);return quickPow(x, n);}
};
劍指offer56-I.數組中數字出現的次數
題目鏈接
題目：整數數組sockets記錄了一個襪子禮盒的顏色分布情況，其中sockets[i]表示該襪子的顏色編號。禮盒中除了一款撞色搭配的襪子，每種顏色的襪子均有兩只。請設計一個程序，在時間復雜度O(n)，空間復雜度O(1)內找到這雙撞色搭配襪子的兩個顏色編號。
思路：分組異或。如果除了一個數字以外，其他數字都出現了兩次，對這個數組進行全員異或就能快速找到這個數字。由此，針對這道題，將那兩個不同的數字拆分到兩個數組中，并且每個數組中，其他數字都出現了兩次就得到了本題解法。
- 先對所有數字進行一次異或，得到兩個出現一次的數字的異或值。
- 在異或結果中找到任意為 1 的位。
- 根據這一位對所有的數字進行分組。
- 在每個組內進行異或操作，得到兩個數字。
通過代碼：
class Solution {
public:vector<int> sockCollocation(vector<int>& sockets) {int ret = 0;for(int n : sockets)ret ^= n;int div = 1;while((ret & div) == 0)div <<= 1;int a = 0, b = 0;for(int n : sockets){if(n & div)a ^= n;elseb ^= n;}return vector<int> {a, b};}
};
劍指offer56-II.數組中數字出現的次數
題目鏈接
題目：教學過程中，教練示范一次，學員跟做三次。該過程被混亂剪輯后，記錄于數組actions，其中actions[i]表示做出該動作的人員編號。請返回教練的編號。
思路：欣賞一下即可。考慮數字的二進制形式，對于出現三次的數字，各二進制位 出現的次數都是 3 的倍數。因此，統計所有數字的各二進制位中 1 的出現次數，并對 3 求余，結果則為只出現一次的數字。
通過代碼：
class Solution {
public:int trainingPlan(vector<int>& actions) {int ones = 0, twos = 0;for(int action : actions){ones = ones ^ action & ~twos;twos = twos ^ action & ~ones;}return ones;}
};
劍指offer65.不用加減乘除做加法
題目鏈接
題目：計算機安全專家正在開發一款高度安全的加密通信軟件，需要在進行數據傳輸時對數據進行加密和解密操作。假定dataA和dataB分別為隨機抽樣的兩次通信的數據量：
- 正數為發送量
- 負數為接受量
- 0 為數據遺失
請不使用四則運算符的情況下實現一個函數計算兩次通信的數據量之和（三種情況均需被統計），以確保在數據傳輸過程中的高安全性和保密性。
思路：數字邏輯中的半加器。本位和c相當于異或運算，進位相當于與運算之后再左移一位。
通過代碼：
class Solution {
public:int encryptionCalculate(int dataA, int dataB) {while(dataB){int c = (dataA & dataB) << 1;dataA ^= dataB;dataB = c;}return dataA;}
};
