預備知識
對於位運算，大家都很熟悉，基本的位操作有與、或、非、異或等等。在面試中經常會出現位運算相關的題，所以我就做了簡單的整理，參考了很多寫的很好的博客及書籍。
現在簡單說一下，移位運算。
左移運算：x << y。將x左移y位，將x最左邊的y位丟棄，在右邊補y個0。
右移運算：x >> y。將x右移y位，這需要區分x是有符號數還是無符號數。在x是無符號數時，只需將x的最右邊的y位丟棄，在左邊補上y個0。在x是有符號數時，又分為x是正數還是負數。正數時，同無符號數的處理相同；負數時，將將x的最右邊的y位丟棄，在左邊補上y個1。
位運算技巧
計算一個數的二進制中1的個數
通過與初始值為1的標志位進行與運算，判斷最低位是否為1；然後將標志位左移，判斷次低位是否為1；一直這樣計算，直到將每一位都判斷完畢。
[cpp]
/*
計算一個數的二進制中1的個數
*/
int countOf1(int num)
{
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(num & flag)
{
count++;
}
flag = flag << 1;
}
return count;
}
/*
計算一個數的二進制中1的個數
*/
int countOf1(int num)
{
int count = 0;
unsigned int flag = 1;
while(flag)
{
if(num & flag)
{
count++;
}
flag = flag << 1;
}
return count;
}
還有一種方法，一個整數減一，可以得到該整數的最右邊的1變為0，這個1右邊的0變為1。對這個整數和整數減一進行與運算，將該整數的最右邊的1變為0，其余位保持不變。直到該整數變為0，進行的與運算的次數即為整數中1的個數。
[cpp]
/*
計算一個數的二進制中1的個數
*/
int countOf1_2(int num)
{
int count = 0;
while(num)
{
num = num & (num - 1);
count++;
}
return count;
}
/*
計算一個數的二進制中1的個數
*/
int countOf1_2(int num)
{
int count = 0;
while(num)
{
num = num & (num - 1);
count++;
}
return count;
}
判斷一個數是否是2的n次方
一個數是2的n次方，則這個數的最高位是1，其余位為0。根據上一題的第二種解法可以很容易得到解決方案。將這個整數與整數減一進行與運算，如果得到的結果為零，可證明該數為2的n次方。
[cpp]
/*
判斷一個數是否為2的n次方（一個數為2的n次方，則最高位為1，其余位為0）
*/
bool is2Power(int num)
{
bool flag = true;
num = num & (num - 1); //計算num和num - 1的與的結果
if(num) //如果結果為0，則不是2的n次方
{
flag = false;
}
return flag;
}
/*
判斷一個數是否為2的n次方（一個數為2的n次方，則最高位為1，其余位為0）
*/
bool is2Power(int num)
{
bool flag = true;
num = num & (num - 1); //計算num和num - 1的與的結果
if(num) //如果結果為0，則不是2的n次方
{
flag = false;
}
return flag;
}
整數n經過多少步可以變為整數m
n和m的異或結果可以得知兩數不同位的個數，再調用計算一個數中1的個數的方法，即可得到結果。
[cpp]
/*
求解n變化為m，需要進行的操作步數
*/
int countChange(int n,int m)
{
n = n ^ m; //求n和m的異或,再計算結果中1的個數
return countOf1_2(n);
}
/*
求解n變化為m，需要進行的操作步數
*/
int countChange(int n,int m)
{
n = n ^ m; //求n和m的異或,再計算結果中1的個數
return countOf1_2(n);
}
獲得最大的int值
[cpp]
/*
獲取最大的int
得到結果：2147483647
*/
int getMaxInt()
{
return (1 << 31) - 1;
}
/*
使用g++編譯，出現warning: left shift count is negative
*/
int getMaxInt_2()
{
return (1 << -1) - 1;
}
int getMaxInt_3()
{
return ~(1 << 31);
}
/*
在不了解int的長度情況下使用
*/
int getMaxInt_4()
{
return ((unsigned int) -1) >> 1;
}
/*
獲取最大的int
得到結果：2147483647
*/
int getMaxInt()
{
return (1 << 31) - 1;
}
/*
使用g++編譯，出現warning: left shift count is negative
*/
int getMaxInt_2()
{
return (1 << -1) - 1;
}
int getMaxInt_3()
{
return ~(1 << 31);
}
/*
在不了解int的長度情況下使用
*/
int getMaxInt_4()
{
return ((unsigned int) -1) >> 1;
}
獲得最小的int值
與獲得最大的int方法類似。
[cpp]
/*
求最小int
得到結果：-2147483648
*/
int getMinInt()
{
return 1 << 31;
}
/*
同樣在g++下編譯，出現warning: left shift count is negative
*/
int getMinInt_2()
{
return 1 << -1;
}
/*
求最小int
得到結果：-2147483648
*/
int getMinInt()
{
return 1 << 31;
}
/*
同樣在g++下編譯，出現warning: left shift count is negative
*/
int getMinInt_2()
{
return 1 << -1;
}
獲得最大的long
[cpp]
/*
求最大long
得到結果：9223372036854775807
*/
long getMaxLong()
{
return ((unsigned long) -1) >> 1;
}
/*
求最大long
得到結果：9223372036854775807
*/
long getMaxLong()
{
return ((unsigned long) -1) >> 1;
}
判斷一個數的奇偶性
判斷奇偶性，實質是判斷最後一位是否是1.
[cpp]
/*
判斷一個數的奇偶性.返回1，為奇數;返回0，為偶數
*/
bool isOdd(int num)
{
return num & 1 == 1;
}
/*
判斷一個數的奇偶性.返回1，為奇數;返回0，為偶數
*/
bool isOdd(int num)
{
return num & 1 == 1;
}
交換兩個數(不借助第三變量)
不用第三個變量交換兩個數的方法也有幾種，例如a = a + b; b = a - b; a = a - b。下面這種方法可以實現的基礎是一個數m與另一個數n異或，再與n異或，得到的結果是m.
[cpp]
/*
不適用臨時變量，交換兩個數
a = a ^ b
b = b ^ a
a = a ^ b
*/
void mySwap(int* a,int* b)
{
(*a) ^= (*b) ^= (*a) ^= (*b);
}
/*
不適用臨時變量，交換兩個數
a = a ^ b
b = b ^ a
a = a ^ b
*/
void mySwap(int* a,int* b)
{
(*a) ^= (*b) ^= (*a) ^= (*b);
}
求一個數的絕對值
下面的方法實現的基礎是將n右移31位，可以獲得n的符號。
[cpp]
/*
取絕對值
n右移31位，可以獲得n的符號。若n為正數，得到0；若n為負數，得到 -1
*/
int myAbs(int n){
return (n ^ n >> 31) - (n >> 31);
}
/*
取絕對值
n右移31位，可以獲得n的符號。若n為正數，得到0；若n為負數，得到 -1
*/
int myAbs(int n){
return (n ^ n >> 31) - (n >> 31);
}
求兩個數的平均值
第一種方法較為普遍且簡單，不多說了。第二種方法，需要知道的是，( m ^ n ) >> 1得到的結果是m和n其中一個數的有些位為1的值的一半，m & n得到的結果是m 和n都為1的那些位，兩個結果相加得到m和n的平均數。
[cpp]
/*
求m和n的平均數
*/
int getAverage(int m,int n){
return (m + n) >> 1;
}
/*
求m和n的平均數
(m ^ n) >> 1 -> 獲得m和n兩個數中一個數的某些位為1的一半
m & n -> 獲得m和n兩個數中都為1的某些位
*/
int getAverage_2(int m,int n){
return ((m ^ n) >> 1) + (m & n);
}
/*
求m和n的平均數
*/
int getAverage(int m,int n){
return (m + n) >> 1;
}
/*
求m和n的平均數
(m ^ n) >> 1 -> 獲得m和n兩個數中一個數的某些位為1的一半
m & n -> 獲得m和n兩個數中都為1的某些位
*/
int getAverage_2(int m,int n){
return ((m ^ n) >> 1) + (m & n);
}
求解倒數第m位相關問題
[cpp]
/*
獲取n的倒數第m位的值（從1開始計數）
*/
int getMthByTail(int n,int m){
return (n >> (m - 1)) & 1;
}
/*
將n的倒數第m位設為1
*/
int setMthByTail21(int n,int m)
{
return n | (1 << (m - 1));
}
/*
將n的倒數第m位設為0
*/
int setMthByTail20(int n,int m)
{
return n & ~(1 << (m - 1));
}
/*
獲取n的倒數第m位的值（從1開始計數）
*/
int getMthByTail(int n,int m){
return (n >> (m - 1)) & 1;
}
/*
將n的倒數第m位設為1
*/
int setMthByTail21(int n,int m)
{
return n | (1 << (m - 1));
}
/*
將n的倒數第m位設為0
*/
int setMthByTail20(int n,int m)
{
return n & ~(1 << (m - 1));
}
