這篇文章總結目前我做過的位運算相關習題，在之后的刷題過程中將會不斷擴充此專題。題目列表如下：
1. 190 顛倒的二進制位
2. 191 位1的個數(shù)
3. 231 2的冪
4. 371 兩整數(shù)之和
5. 405 數(shù)字轉化為十六進制
190 顛倒的二進制位
題目大意
顛倒給定的 32 位無符號整數(shù)的二進制位。
示例1：
輸入: 00000010100101000001111010011100
輸出: 00111001011110000010100101000000
解釋: 輸入的二進制串 00000010100101000001111010011100 表示無符號整數(shù) 43261596，
因此返回 964176192，其二進制表示形式為 00111001011110000010100101000000。
示例2：
輸入：11111111111111111111111111111101
輸出：10111111111111111111111111111111
解釋：輸入的二進制串 11111111111111111111111111111101 表示無符號整數(shù) 4294967293，
因此返回 3221225471 其二進制表示形式為 10101111110010110010011101101001。
思路
利用位運算，原數(shù)每次循環(huán)右移1位，取末尾數(shù)字，然后新數(shù)加上這個末尾再循環(huán)左移。
代碼
public int reverseBits(int n) {
int t = 0;
for(int i = 0;i<32;i++)
t+= (1&(n>>i))<<(31-i);
return t;
}
運行時間2ms。
位1的個數(shù)
題目大意
編寫一個函數(shù)，輸入是一個無符號整數(shù)，返回其二進制表達式中數(shù)字位數(shù)為 ‘1’ 的個數(shù)。
示例1：
輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進制串 00000000000000000000000000001011 中，共有三位為 '1'。
示例2：
輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'。
思路一：位運算
利用循環(huán)右移操作，每次移動1位，并且取出末尾與1做&操作，若不為1，說明末尾是0。
public int hammingWeight(int n) {
int cnt = 0;
for(int i=0;i<32;i++)
{
cnt += n&1;
n >>=1;
}
return cnt;
}
思路二：n與n-1做位運算
當n與n-1做&運算，會把最后一個1的位變成0。
public int hammingWeight(int n) {
int cnt = 0;
while(n!=0) {
++cnt;
n = n&(n-1);
}
return cnt;
}
運行時間2ms。
231 2的冪
題目大意
給定一個整數(shù)，編寫一個函數(shù)來判斷它是否是 2 的冪次方。
示例1：
輸入: 1
輸出: true
解釋: 2^0 = 1
示例2：
輸入: 16
輸出: true
解釋: 24 = 16
方法一：暴力法
采用迭代的方法，一個一個試。此題會超時。
public boolean isPowerOfTwo(int n) {
if(n==1) return true;
int cur = 1;
while(cur<n) {
cur *=2;
if(cur==n) return true;
}
return false;
}
方法二：二分查找
采用打表和二分查找的方法，將int范圍內的所有2^n全部存入一個整數(shù)表中，然后對整數(shù)表進行二分查找。
int[] res = new int[31];
private void form() {
res[0] = 1;
for(int i=1;i<31;i++)
res[i]=res[i-1]*2;
}
public boolean isPowerOfTwo(int n) {
form();
if(n!=1 && n%2==1) return false;
int low = 0;
int high = 30;
while(low<high) {
int mid = (low+high)>>1;
if(res[mid]==n) return true;
else if(res[mid] > n)
high = mid -1;
else if(res[mid] < n)
low = mid+1;
}
return res[low]==n?true:false;
}
運行時間3ms,87.42%。
方法三：位運算
將2^n 和 2^n-1做與運算，結果一定為0。
public boolean isPowerOfTwo(int n) {
if(n<=0) return false;
return (n&(n-1))==0?true:false;
}
運行時間2ms, 98.23%。
兩整數(shù)之和
題目大意
不使用運算符 + 和 - ???????，計算兩整數(shù) ???????a 、b ???????之和。
示例1：
輸入: a = 1, b = 2
輸出: 3
輸入: a = -2, b = 3
輸出: 1
思路
不用運算符，考慮位運算。a^b 得到不考慮進位的a+b結果；a&b<<1得到a+b的進位。
public int getSum(int a, int b) {
while(b!=0) {
int carry = (a&b)<<1;
a = a^b;
b = carry;
}
return a;
}
405 數(shù)字轉化為十六進制
題目大意
給定一個整數(shù)，編寫一個算法將這個數(shù)轉換為十六進制數(shù)。對于負整數(shù)，我們通常使用補碼運算。
注意：
十六進制中所有字母(a-f)都必須是小寫。
十六進制字符串中不能包含多余的前導零。如果要轉化的數(shù)為0，那么以單個字符'0'來表示；對于其他情況，十六進制字符串中的第一個字符將不會是0字符。
給定的數(shù)確保在32位有符號整數(shù)范圍內。
不能使用任何由庫提供的將數(shù)字直接轉換或格式化為十六進制的方法。
示例1：
輸入:
26
輸出:
"1a"
示例2：
輸入:
-1
輸出:
"ffffffff"
方法：位運算
public String toHex(int num) {
if(num==0) return "0";
char[] dict = {'0','1','2','3','4','5','6','7','8','9',
'a','b','c','d','e','f'};
StringBuffer sb = new StringBuffer();
while(num!=0) {
sb.append(dict[num&0xf]);
num = num >>> 4;
}
return sb.reverse().toString();
}
&0xf: 取末尾四位。
運行時間1ms,擊敗88.12%。
