程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C/C++位運算技巧

C/C++位運算技巧

編輯:C++入門知識

預備知識
對於位運算,大家都很熟悉,基本的位操作有與、或、非、異或等等。在面試中經常會出現位運算相關的題,所以我就做了簡單的整理,參考了很多寫的很好的博客及書籍。

現在簡單說一下,移位運算。

左移運算: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));
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved