- Single Number落單的數(shù)
- 落單的數(shù) IISingle Number II
- Single Number III落單的數(shù) III
- Number of 1 Bits
- Counting Bits
- Reverse Bits
- Missing Number
- Sum of Two Integers
- Power of Two
- Power of Four
本文將根據(jù)題目總結(jié)常用的位操作常用的解決算法問題的技巧
如讀者對基本的位操作概念還不熟悉先紫，可以先參考筆者的文章淺談程序設(shè)計(jì)中的位操作http://www.reibang.com/p/294fc6605bb1
Single Number落單的數(shù)
給出2*n + 1 個的數(shù)字桅狠，除其中一個數(shù)字之外其他每個數(shù)字均出現(xiàn)兩次拧簸，找到這個數(shù)字。
思路：
一個數(shù)字和自己進(jìn)行異或操作會是0沟突，由于異或操作滿足交換定律，一個數(shù)和0進(jìn)行異或操作還是本身。所以這道題目的思路就來了，將所有出現(xiàn)兩次的數(shù)異或就都變成了0槽片，最后剩的那個數(shù)和0異或就還是本身何缓。直接將數(shù)組所有數(shù)異或，就可以找出那個落單的數(shù)
public class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i=0;i<nums.length;i++)
res ^= nums[i];
return res;
}
}
落單的數(shù) IISingle Number II
給出3*n + 1 個的數(shù)字还栓，除其中一個數(shù)字之外其他每個數(shù)字均出現(xiàn)三次碌廓，找到這個數(shù)字。
思路：
java中int是32位的剩盒，所以我們利用一個32的數(shù)組谷婆，分別記錄每一位1的情況，如果出現(xiàn)三次就清0辽聊，最后留下來的就是那個只出現(xiàn)1次的數(shù)字在那一位上的情況纪挎，然后進(jìn)行移位復(fù)原
public class Solution {
public int singleNumber(int[] A) {
int[] bits = new int[32];
int res = 0;
for(int i=0;i<32;i++) {
for(int j=0;j<A.length;j++) {
bits[i] += (A[j]>>i) & 1;
}
res = res | ((bits[i]%3) << i);
}
return res;
}
}
如果要找出現(xiàn)4次或者出現(xiàn)5次等的情況，只要%5就行了跟匆。
Single Number III落單的數(shù) III
給出2*n + 2個的數(shù)字异袄，除其中兩個數(shù)字之外其他每個數(shù)字均出現(xiàn)兩次，找到這兩個數(shù)字玛臂。
思路
如果能把這兩個不同的數(shù)字分開烤蜕，那么直接采取落單的數(shù)1的方法異或就可以了。
所以迹冤，我們先考慮將所有數(shù)異或讽营，最后得到的結(jié)果是兩個不同的數(shù)的異或結(jié)果，然后我們找到最后一位為1的位泡徙，為1代表這兩個數(shù)在這一位上是不同的橱鹏。然后用這個位與數(shù)組中每個數(shù)相與，就可以把數(shù)分成兩部分锋勺，一部分里有第一個不同的數(shù)蚀瘸，另一部分有第二個不同的數(shù)，所以這個時候我們只要直接異或就可以得到結(jié)果了庶橱。
public class Solution {
public int[] singleNumber(int[] A) {
int xor = 0;
for(int i=0;i<A.length;i++) {
xor ^= A[i];
}
// a&(a-1)將最后為1的一位變成0
int lastbit = xor - (xor & (xor -1)); //取出最后一個為1的位
int group0 = 0, group1 = 0;
for(int i=0;i<A.length;i++) {
if((lastbit & A[i]) == 0)
group0 ^= A[i];
else
group1 ^= A[i];
}
return new int[]{group0,group1};
}
}
Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011
, so the function should return 3.
思路：
依次拿每一位與1進(jìn)行比較贮勃，統(tǒng)計(jì)1的個數(shù)，然后邏輯右移苏章，不能用算數(shù)右移寂嘉，算數(shù)右移會在高位加一。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ones = 0;
while(n!=0) {
ones += (n & 1);
n = n >>> 1;
}
return ones;
}
}
還有一種方法枫绅，我們知道n&(n-1)會把n中最后為1的一位變成0泉孩。
所以我們調(diào)用n&(n-1),看看調(diào)幾次這個數(shù)會變成0，就說明有幾個1.
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int sum = 0;
while(n != 0) {
sum++;
n = n & (n-1);
}
return sum;
}
}
Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example:
For num = 5 you should return [0,1,1,2,1,2].
思路：
我們當(dāng)然可以利用上一題的方法并淋，直接每個數(shù)計(jì)算一次
但也發(fā)現(xiàn)是存在規(guī)律的
public class Solution {
public int[] countBits(int num) {
int[] res = new int[num+1];
for(int i=1;i<=num;i++)
res[i] = res[i>>1] + (i & 1);
return res;
}
}
Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
思路：
利用位操作寓搬，先交換相鄰的兩位，再交換的四位县耽，再交換相鄰的八位句喷。
舉個例子镣典；
我們交換12345678
可以先變成 21436587
再變成43218765
最后87654321，交換成功
對于32位也是如此的思路唾琼。
關(guān)鍵如何用位操作實(shí)現(xiàn)兄春，首先交換兩位的話，可以先分別取出前一位
x & （10101010101010101101010锡溯。赶舆。。祭饭。）
換成16進(jìn)制就是
x & (0xaaaaaaaa)取出前一位芜茵，因?yàn)橐c要有后一位交換，所以右移一位甜癞，因?yàn)橹皇菃渭兊慕粨Q夕晓，所以是邏輯右移
（x & 0xaaaaaaaa） >>> 1
然后對后一位也進(jìn)行相應(yīng)的操作，很容易得出
(x & 0x555555555) << 1
最后分別將前一位后一位合起來悠咱，使用或操作就可以了
所以蒸辆，第一次交換后
x = ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1);
然后進(jìn)行第二次交換：
取出前兩位
x & (1100110011001100......)也就是 x & 0xcccccccc.
后面的步驟都是一樣的思路
x = ((x & 0xcccccccc) >>> 2) | ((x & 0x33333333) << 2);
第三次交換
x = ((x & 0xf0f0f0f0) >>> 4) | ((x & 0x0f0f0f0f) << 4);
第四次交換
x = ((x & 0xff00ff00) >>> 8) | ((x & 0x00ff00ff) << 8);
第四次交換
x = ((x & 0xffff0000) >>> 16) | ((x & 0x0000ffff) << 16);
交換成功
代碼就是上面的交換的過程
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int x) {
x = ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >>> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >>> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >>> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >>> 16) | ((x & 0x0000ffff) << 16);
return x;
}
}
Missing Number
給出一個包含 0 .. N 中 N 個數(shù)的序列，找出0 .. N 中沒有出現(xiàn)在序列中的那個數(shù)析既。
public class Solution {
public int missingNumber(int[] nums) {
int xor = 0, i = 0;
for (i = 0; i < nums.length; i++) {
xor = xor ^ i ^ nums[i];
}
return xor ^ i;
}
}
Sum of Two Integers
位操作實(shí)現(xiàn)A+B的操作是常見的算法題躬贡。
lintcode上就有一道容易題是這樣。
class Solution {
/*
* param a: The first integer
* param b: The second integer
* return: The sum of a and b
*/
public int aplusb(int a, int b) {
// write your code here, try to do it without arithmetic operators.
if(a==0)return b;
if(b==0)return a;
int x1 = a^b;
int x2 = (a&b)<<1;
return aplusb(x1,x2);
}
};
上述代碼就實(shí)現(xiàn)了不用+操作符眼坏，利用位操作實(shí)現(xiàn)兩個數(shù)的相加操作拂玻。
現(xiàn)在我們來講解位操作實(shí)現(xiàn)兩個數(shù)相加的原理
首先，十進(jìn)制中宰译，我們知道檐蚜，7+8，不進(jìn)位和是5沿侈，進(jìn)位是1闯第，然后我們可以根據(jù)不進(jìn)位和和進(jìn)位5+1*10算出最后的結(jié)果15。
類似二進(jìn)制也可以采取這種方法
比如
a = 3缀拭，b = 6
a : 0011
b : 0110
不進(jìn)位和： 0101 也就是5
進(jìn)位：0010 也就是2
所以a+b變成5 + （2<<1）
5 0101
2<<1 0100
不進(jìn)位和 0001 = 1
進(jìn)位 0100 = 4
因此 a + b就變成了1 + 4 << 1
然后有
1 0001
4<<1 1000
不進(jìn)位和 1001 = 9
進(jìn)位 0000 = 0
當(dāng)時進(jìn)位為0時咳短，不進(jìn)位和為9即a + b之和。
可以發(fā)現(xiàn)上述是一個遞歸的過程蛛淋，所以也就不難寫出代碼了咙好。求兩個數(shù)的不進(jìn)位和實(shí)際上就是將兩個數(shù)異或操作即可。
Power of Two
Given an integer, write a function to determine if it is a power of two.
要為2的次方
1褐荷，2勾效，4，8，16
也就是每位分別單獨(dú)為1
1
10
100
1000
10000
所以n & (n-1)必須為0
public class Solution {
public boolean isPowerOfTwo(int n) {
if(n<=0)
return false;
return (n & (n-1)) == 0;
}
}
Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
按照上一題的思路葵第，我們先列舉出幾個4的次方數(shù)绘迁，觀察他門的規(guī)律
1
100
10000
1000000
我們發(fā)現(xiàn)不僅要2的次方的性質(zhì)，還要滿足 1所在的位必須是奇數(shù)位卒密，所以我們?nèi)〕銎鏀?shù)位，由于棠赛，1只在奇數(shù)位哮奇，所以取出奇數(shù)位后，應(yīng)該還和原來的數(shù)相等
取奇數(shù)位的方法在反轉(zhuǎn)bit那題中已經(jīng)講過睛约，就是x & 0x55555555
public class Solution {
public boolean isPowerOfFour(int num) {
return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) == num);
}
}
