資訊專欄INFORMATION COLUMN
摘要：使用位運算數(shù)組只出現(xiàn)一次數(shù)字的數(shù)組得到最低的有效位，即兩個數(shù)不同的那一位看完上面的解法，我腦海中只有問號的存在，啥意思啊下面就讓我們簡單了解一下位運算并解析一下這三道題目。另，負(fù)數(shù)按補碼形式參加按位與運算。
你可做過這幾道題？
在面試的準(zhǔn)備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目：
# 136. 只出現(xiàn)一次的數(shù)字
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。
說明：
你的算法應(yīng)該具有線性時間復(fù)雜度。 你可以不使用額外空間來實現(xiàn)嗎？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
我不禁眉頭一皺，心說，這還不簡單，三下五除二寫下如下代碼：
/**
* HashMap
*
* @param nums 數(shù)組
* @return 結(jié)果
*/
public int solution(int[] nums) {
Map map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.remove(num);
} else {
map.put(num, 1);
}
}
return map.entrySet().iterator().next().getKey();
}
接著，我看到了另外一道題目：
# 137. 只出現(xiàn)一次的數(shù)字 II
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)了三次。找出那個只出現(xiàn)了一次的元素。
說明：
你的算法應(yīng)該具有線性時間復(fù)雜度。 你可以不使用額外空間來實現(xiàn)嗎？
示例 1:
輸入: [2,2,3,2]
輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
我不禁眉頭又一皺，心說，好像是同樣的套路，便寫下了如下代碼：
/**
* 使用Map，存儲key以及出現(xiàn)次數(shù)
*
* @param nums 數(shù)組
* @return 出現(xiàn)一次的數(shù)字
*/
public int singleNumber(int[] nums) {
Map map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
for (Integer key : map.keySet()) {
if (map.get(key) == 1) {
return key;
}
}
return 0;
}
然后，就出現(xiàn)了終極題目：
# 260. 只出現(xiàn)一次的數(shù)字 III
給定一個整數(shù)數(shù)組 nums，其中恰好有兩個元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。 找出只出現(xiàn)一次的那兩個元素。
示例 :
輸入: [1,2,1,3,2,5]
輸出: [3,5]
注意：
1. 結(jié)果輸出的順序并不重要，對于上面的例子， [5, 3] 也是正確答案。
2. 你的算法應(yīng)該具有線性時間復(fù)雜度。你能否僅使用常數(shù)空間復(fù)雜度來實現(xiàn)？
我不禁又皺了一下眉頭，心說，嗯……接著便寫下如下代碼：
/**
* 使用Map，存儲key以及出現(xiàn)次數(shù)
*
* @param nums 數(shù)組
* @return 出現(xiàn)一次的數(shù)字的數(shù)組
*/
public int[] singleNumber(int[] nums) {
int[] result = new int[2];
Map map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
int i = 0;
for (Integer key : map.keySet()) {
if (map.get(key) == 1) {
result[i] = key;
i++;
}
}
return result;
}
用幾乎同一種思路做了三道題，不得不夸一下自己：
做完這三道題目，提交了答案之后，執(zhí)行用時和內(nèi)存消耗都只超過了 10% 的解題者。不由得眉頭緊鎖（終于知道自己為啥抬頭紋這么深了），發(fā)現(xiàn)事情并沒有這么簡單……
之后我又找了一下其他解法，如下：
/**
* #136 根據(jù)題目描述，由于加上了時間復(fù)雜度必須是 O(n) ，并且空間復(fù)雜度為 O(1) 的條件，因此不能用排序方法，也不能使用 map 數(shù)據(jù)結(jié)構(gòu)。答案是使用 位操作Bit Operation 來解此題。
* 將所有元素做異或運算，即a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n]，所得的結(jié)果就是那個只出現(xiàn)一次的數(shù)字，時間復(fù)雜度為O(n)。
* 根據(jù)異或的性質(zhì) 任何一個數(shù)字異或它自己都等于 0
*
* @param nums 數(shù)組
* @return 結(jié)果
*/
private int solution(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
/**
* #137 嗯……這個我們下面再做詳解
* 這里使用了異或、與、取反這些運算
*
* @param nums 數(shù)組
* @return 出現(xiàn)一次的數(shù)字
*/
public int singleNumber2(int[] nums) {
int a = 0, b = 0;
int mask;
for (int num : nums) {
b ^= a & num;
a ^= num;
mask = ~(a & b);
a &= mask;
b &= mask;
}
return a;
}
/**
* #260 在這里把所有元素都異或，那么得到的結(jié)果就是那兩個只出現(xiàn)一次的元素異或的結(jié)果。
* 然后，因為這兩個只出現(xiàn)一次的元素一定是不相同的，所以這兩個元素的二進制形式肯定至少有某一位是不同的，即一個為 0 ，另一個為 1 ，現(xiàn)在需要找到這一位。
* 根據(jù)異或的性質(zhì) 任何一個數(shù)字異或它自己都等于 0 ，得到這個數(shù)字二進制形式中任意一個為 1 的位都是我們要找的那一位。
* 再然后，以這一位是 1 還是 0 為標(biāo)準(zhǔn)，將數(shù)組的 n 個元素分成兩部分。
* 1. 將這一位為 0 的所有元素做異或，得出的數(shù)就是只出現(xiàn)一次的數(shù)中的一個
* 2. 將這一位為 1 的所有元素做異或，得出的數(shù)就是只出現(xiàn)一次的數(shù)中的另一個。
* 這樣就解出題目。忽略尋找不同位的過程，總共遍歷數(shù)組兩次，時間復(fù)雜度為O(n)。
*
* 使用位運算
*
* @param nums 數(shù)組
* @return 只出現(xiàn)一次數(shù)字的數(shù)組
*/
public int[] singleNumber2(int[] nums) {
int diff = 0;
for (int num : nums) {
diff ^= num;
}
// 得到最低的有效位，即兩個數(shù)不同的那一位
diff &= -diff;
int[] result = new int[2];
for (int num : nums) {
if ((num & diff) == 0) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
return result;
}
看完上面的解法，我腦海中只有問號的存在，啥意思啊？！
下面就讓我們簡單了解一下位運算并解析一下這三道題目。
簡單介紹一下位運算
異或邏輯的關(guān)系是：當(dāng)AB不同時，輸出P=1；當(dāng)AB相同時，輸出P=0?！皑挕笔钱惢驍?shù)學(xué)運算符號，異或邏輯也是與或非邏輯的組合，其邏輯表達式為：P=A⊕B。在計算機語言中，異或的符號為“ ^ ”。
異或運算 A ⊕ B 的真值表如下：
| A | B | ⊕ |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
所以我們從 #136 題解中了解，通過異或運算，兩個相同的元素結(jié)果為 0，而 任何數(shù) 與 0 進行異或操作，結(jié)果都為其本身。
“與”運算是計算機中一種基本的邏輯運算方式，符號表示為 “&”，參加運算的兩個數(shù)據(jù)，按二進制位進行“與”運算。運算規(guī)則：0&0=0；0&1=0；1&0=0；1&1=1；即：兩位同時為“1”，結(jié)果才為“1”，否則為0。另，負(fù)數(shù)按補碼形式參加按位與運算。
與運算 A & B 的真值表如下：
| A | B | & |
|---|---|---|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
“與運算”的特殊用途：
清零。如果想將一個單元清零，即使其全部二進制位為0，只要與一個各位都為零的數(shù)值相與，結(jié)果為零。
取一個數(shù)的指定位
方法：找一個數(shù)，對應(yīng)X要取的位，該數(shù)的對應(yīng)位為1，其余位為零，此數(shù)與X進行“與運算”可以得到X中的指定位。例：設(shè) X=10101110，取X的低4位，用 X & 0000 1111 = 0000 1110 即可得到；還可用來取 X 的2、4、6位。
參加運算的兩個對象，按二進制位進行“或”運算。運算規(guī)則：0|0=0； 0|1=1； 1|0=1； 1|1=1；即 ：參加運算的兩個對象只要有一個為1，其值為1。另，負(fù)數(shù)按補碼形式參加按位或運算。
或運算 A | B 的真值表如下：
| A | B | | |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
或運算”特殊作用：
常用來對一個數(shù)據(jù)的某些位置1。
方法：找到一個數(shù)，對應(yīng)X要置1的位，該數(shù)的對應(yīng)位為1，其余位為零。此數(shù)與X相或可使X中的某些位置1。
例：將 X=10100000 的低4位 置為1 ，用 X | 0000 1111 = 1010 1111 即可得到。
參加運算的一個數(shù)據(jù)，按二進制位進行“取反”運算。運算規(guī)則：~1=0； ~0=1；即：對一個二進制數(shù)按位取反，即將0變1，1變0。
使一個數(shù)的最低位為零，可以表示為：a&~1。~1 的值為 1111111111111110，再按“與”運算，最低位一定為0。因為“~”運算符的優(yōu)先級比算術(shù)運算符、關(guān)系運算符、邏輯運算符和其他運算符都高。
OK，截止到這兒，三道題目中使用的位運算介紹完畢，那么這里我們插入一下 #137 的詳細(xì)題解。
public int singleNumber2(int[] nums) {
// 這里我們改一下變量名
// 用 one 記錄到當(dāng)前處理的元素為止，二進制1出現(xiàn)“1次”（mod 3 之后的 1）的有哪些二進制位；
// 用 two 記錄到當(dāng)前計算的變量為止，二進制1出現(xiàn)“2次”（mod 3 之后的 2）的有哪些二進制位。
int one = 0, two = 0;
int mask;
for (int num : nums) {
// 由于 two 要考慮，one 的已有狀態(tài)，和當(dāng)前是否繼續(xù)出現(xiàn)。所以要先算
two ^= one & num;
// one 就是一個0,1的二值位，在兩個狀態(tài)間轉(zhuǎn)換
one ^= num;
// 當(dāng) one 和 two 中的某一位同時為1時表示該二進制位上1出現(xiàn)了3次，此時需要清零。
mask = ~(one & two);
// 清零操作
one &= mask;
two &= mask;
}
// 即用 二進制 模擬 三進制 運算。最終 one 記錄的是最終結(jié)果。
return one;
}
首先考慮一個相對簡單的問題，加入輸入數(shù)組里面只有 0 和 1，我們要統(tǒng)計 1 出現(xiàn)的次數(shù)，當(dāng)遇到 1 就次數(shù)加 1，遇到 0 就不變，當(dāng)次數(shù)達到 k 時，統(tǒng)計次數(shù)又回歸到 0。我們可以用 m 位來做這個計數(shù)工作，即 xm, xm?1, …, x1，只需要確保 2m? > k 即可，接下來我們要考慮的問題就是，在每一次check元素的時候，做什么操作可以滿足上述的條件。在開始計數(shù)之前，每一個計數(shù)位都初始化位0，然后遍歷nums，直到遇到第一個1，此時 x1 會變成1，繼續(xù)遍歷，直到遇到第二個1，此時 x1=0, x2=1，直到這里應(yīng)該可以看出規(guī)律了。每遇到一個1，對于 xm, xm?1, …, x1，只有之前的所有位都為1的時候才需要改變自己的值，如果本來是1，就變成0，本來是0，就變成1 ，如果遇到的是0，就保持不變。搞清楚了這個邏輯，寫出表達式就不難了。這里以 m = 3 為例給出 java 代碼：
for(int num: nums) {
x3 ^= x2 & x1 & i;
x2 ^= x1 & i;
x1 ^= i;
// other operations
}
但是到這里還沒有解決當(dāng) 1 的次數(shù)到 k 時，計數(shù)值要重新返回到 0，也就是所有計數(shù)位都變成 0 這個問題。解決辦法也是比較巧妙。
假設(shè)我們有一個標(biāo)志變量，只有當(dāng)計數(shù)值到 k 的時候這個標(biāo)志變量才為 0，其余情況下都是 1，然后每一次check元素的時候都對每個計數(shù)位和標(biāo)志變量做與操作，那么如果標(biāo)志變量為 0，也就是計數(shù)值為 k 的時候，所有位都會變成 0， 反之，所有位都會保持不變，那么我們的目的也就達到了。
好，最后一個問題是怎么計算標(biāo)志變量的值。將 k 轉(zhuǎn)變?yōu)槎M制，只有計數(shù)值達到 k，所有計數(shù)位才會和 k 的二進制一樣，所以只需要將 k 的二進制位做 與操作 ，如果某個位為 0，就與該位 取反 之后的值做與操作。
以 k=3, m=2 為例，簡要的 java 代碼如下：
// where yj = xj if kj = 1,
// and yj = ~xj if kj = 0,
// k1, k2是 k 的二進制表示(j = 1 to 2).
mask = ~(y1 & y2);
x2 &= mask;
x1 &= mask;
將這兩部分合起來就是解決這個問題的完整算法了。
將一個運算對象的各二進制位全部左移若干位（左邊的二進制位丟棄，右邊補0）。
例：a = a<< 2將a的二進制位左移2位，右補0，左移1位后a = a *2;
若左移時舍棄的高位不包含1，則每左移一位，相當(dāng)于該數(shù)乘以2。
代碼示例，本代碼中的整數(shù)為32位整數(shù)，所以為負(fù)數(shù)的話，二進制表示其長度為32：
/**
* << 表示左移，如果該數(shù)為正，則低位補0，若為負(fù)數(shù)，則低位補1。如：5<<2的意思為5的二進制位往左挪兩位，右邊補0，5的二進制位是0000 0101 ， 就是把有效值101往左挪兩位就是0001 0100
*/
@Test
public void leftShiftTest() {
int number1 = 5;
System.out.println("左移前的十進制數(shù)為：" + number1);
System.out.println("左移前的二進制數(shù)為：" + Integer.toBinaryString(number1));
int number2 = number1 << 2;
System.out.println("左移后的十進制數(shù)為：" + number2);
System.out.println("左移后的二進制數(shù)為：" + Integer.toBinaryString(number2));
System.out.println();
int number3 = -5;
System.out.println("左移前的十進制數(shù)為：" + number3);
System.out.println("左移前的二進制數(shù)為：" + Integer.toBinaryString(number3));
int number4 = number3 << 2;
System.out.println("左移后的十進制數(shù)為：" + number4);
System.out.println("左移后的二進制數(shù)為：" + Integer.toBinaryString(number4));
}
結(jié)果如下：
左移前的十進制數(shù)為：5
左移前的二進制數(shù)為：101
左移后的十進制數(shù)為：20
左移后的二進制數(shù)為：10100
左移前的十進制數(shù)為：-5
左移前的二進制數(shù)為：11111111111111111111111111111011
左移后的十進制數(shù)為：-20
左移后的二進制數(shù)為：11111111111111111111111111101100
>> 表示右移，表示將一個數(shù)的各二進制位全部右移若干位，正數(shù)左補0，負(fù)數(shù)左補1，右邊丟棄。操作數(shù)每右移一位，相當(dāng)于該數(shù)除以2。
>>> 表示無符號右移，也叫邏輯右移，即若該數(shù)為正，則高位補0，而若該數(shù)為負(fù)數(shù)，則右移后高位同樣補0。
例如：a = a >> 2 將a的二進制位右移2位，左補0 or 補1得看被移數(shù)是正還是負(fù)。
代碼示例，本代碼中的整數(shù)為32位整數(shù)，所以為負(fù)數(shù)的話，二進制表示其長度為32：
@Test
public void rightShift() {
int number1 = 10;
System.out.println("右移前的十進制數(shù)為：" + number1);
System.out.println("右移前的二進制數(shù)為：" + Integer.toBinaryString(number1));
int number2 = number1 >> 2;
System.out.println("右移后的十進制數(shù)為：" + number2);
System.out.println("右移后的二進制數(shù)為：" + Integer.toBinaryString(number2));
System.out.println();
int number3 = -10;
System.out.println("右移前的十進制數(shù)為：" + number3);
System.out.println("右移前的二進制數(shù)為：" + Integer.toBinaryString(number3));
int number4 = number3 >> 2;
System.out.println("右移后的十進制數(shù)為：" + number4);
System.out.println("右移后的二進制數(shù)為：" + Integer.toBinaryString(number4));
System.out.println("***********************邏輯右移**********************");
int a = 15;
System.out.println("邏輯右移前的十進制數(shù)為：" + a);
System.out.println("邏輯右移前的二進制數(shù)為：" + Integer.toBinaryString(a));
int b = a >>> 2;
System.out.println("邏輯右移后的十進制數(shù)為：" + b);
System.out.println("邏輯右移后的二進制數(shù)為：" + Integer.toBinaryString(b));
System.out.println();
int c = -15;
System.out.println("邏輯右移前的十進制數(shù)為：" + c);
System.out.println("邏輯右移前的二進制數(shù)為：" + Integer.toBinaryString(c));
int d = c >>> 2;
System.out.println("邏輯右移后的十進制數(shù)為：" + d);
System.out.println("邏輯右移后的二進制數(shù)為：" + Integer.toBinaryString(d));
}
結(jié)果如下：
右移前的十進制數(shù)為：10
右移前的二進制數(shù)為：1010
右移后的十進制數(shù)為：2
右移后的二進制數(shù)為：10
右移前的十進制數(shù)為：-10
右移前的二進制數(shù)為：11111111111111111111111111110110
右移后的十進制數(shù)為：-3
右移后的二進制數(shù)為：11111111111111111111111111111101
***********************邏輯右移**********************
邏輯右移前的十進制數(shù)為：15
邏輯右移前的二進制數(shù)為：1111
邏輯右移后的十進制數(shù)為：3
邏輯右移后的二進制數(shù)為：11
邏輯右移前的十進制數(shù)為：-15
邏輯右移前的二進制數(shù)為：11111111111111111111111111110001
邏輯右移后的十進制數(shù)為：1073741820
邏輯右移后的二進制數(shù)為：111111111111111111111111111100
總結(jié)
以上就是我們常見的幾種位運算了，其中左移、右移等操作，在 HashMap的源碼中也會經(jīng)?？吹剑斫饬诉@些位操作，對于理解源碼也是有一定幫助的，當(dāng)然也會幫助我們寫出執(zhí)行效率更高的代碼。
從上面的部分示例中可以看出，位運算通常用來降低包含排列，計數(shù)等復(fù)雜度比較高的操作，當(dāng)然也可以用來代替乘 2 除 2，判斷素數(shù)，偶數(shù)，倍數(shù)等基本操作，但是我認(rèn)為其意義在于前者，即用計數(shù)器來降低設(shè)計到排列或者計數(shù)的問題的復(fù)雜度。
最后一點，三道算法題中，#136 、#260 理解起來倒還好，#137 Single Number II 的題解可能需要費一點功夫，至少我還沒有完全理解，但不能輕易放棄對不對，繼續(xù)啃啊！
以上便是我個人的簡單總結(jié)，如果有紕漏或者錯誤，歡迎進行指出及糾正。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/6636.html
摘要：簡單介紹一下位運算異或運算異或邏輯的關(guān)系是當(dāng)不同時，輸出當(dāng)相同時，輸出。另，負(fù)數(shù)按補碼形式參加按位與運算。使一個數(shù)的最低位為零，可以表示為。，截止到這兒，三道題目中使用的位運算介紹完畢，那么這里我們插入一下的詳細(xì)題解。你可做過這幾道題？ 在面試的準(zhǔn)備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字 給定一個非空整數(shù)數(shù)組，除了某個元素只...
摘要：題目二答案會報錯未定義這段代碼中混合了函數(shù)聲明和函數(shù)表達式的形式，而函數(shù)實際上是綁定到了上而不是。除此之外函數(shù)聲明與函數(shù)表達式的語法其實是等價的。因此，在外層函數(shù)函數(shù)體內(nèi)的兩個函數(shù)聲明，都會提升到之前執(zhí)行。 這是我在Javascript微信公眾號上看到的一篇文章，覺得挺有意思的，所以轉(zhuǎn)載過來跟大家分享一下，同時，對這些題目也加上了一些我個人的理解，如果有不對的地方，請大家指正。 題目...
摘要：如果不存在公共前綴，返回空字符串。示例輸入輸出示例輸入輸出解釋輸入不存在公共前綴。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個人主頁：應(yīng)無所住...
摘要：先實現(xiàn)棧操作遍歷鏈表，把每個節(jié)點都進中然后再遍歷鏈表，同時節(jié)點依次出棧，二者進行比較。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個人主頁：應(yīng)無...
閱讀 1102·2021-10-14 09:43
閱讀 1145·2021-10-11 11:07
閱讀 3112·2021-08-18 10:23
閱讀 1484·2019-08-29 16:18
閱讀 999·2019-08-28 18:21
閱讀 1474·2019-08-26 12:12
閱讀 3760·2019-08-26 10:11
閱讀 2501·2019-08-23 18:04
