二進制位操作的相關算法

1. 直接交換整數a,b兩個變量的值，不使用其他變量

   a = a^b; 
   b = a^b;
   a = a^b;
              

   更簡單的寫法：

   a ^= b ^= a ^= b
              

   二進制層級的算法内容，主要涉及到位的運算與操作。

   二進制的位的基礎操作如下：

2. x & (x-1) ,該操作是把x的二進制表示的最低位的1給清零。例如 x = 0b1010110執行上面的語句後x變成0b1010100

3. x & !(x-1)得到最低位的1，例如

   x             = 0b1010110
   
   x-1           = 0b1010101
   
   !(x-1)        = 0b0101010
   
   x & !(x-1)    = 0b0000010
              

   于是x二進制表示中，最低位的1我們就取得了。

4. 交換第i位和第j位的值(最低位從0開始)

   例如：x = 0b0101 ,i = 1,j = 0;交換第i位和第j位後 x = 0b0110;

   代碼如下

   int swapBit(int x ,int i, int j){
       if((x >> i)&1 != (x>>j)&1){		// 判斷第i位和第j位是否一樣
           x ^= (1 << i) | (1 << j); 	//交換第i位和第j位
       }
       return x;
   }
              

   0b 0  1  0  1		//x的值
   0b 0  0  1  1		// (1 << i) | (1 << j)的結果
   0b 0  1  1  0		// 亦或操作的結果
              

5. 将64位整形二進制數進行倒轉

   例如：x = 0b11100倒轉後x = 0b00111

   基于第四步的位交換操作，很容易實作該功能

   int reserve(int x){
   	int j = Integer.size - 1;
       int i = 0;
       while(i < j){
           swapBit(x,i,j);
           x ++;
           j --;
       }
   }
              

一道算法面試題

對于64位或32位的無符号整形數x,我們把它的二進制表示中，1的個數稱為x的權重，例如 x = 7,它的二進制表示為111，那麼x的權重就是3，用S(k)表示64位或32位無符号整數中，權重是k的所有整數的集合，其中k不等于0和64， 給定一個整形數x，x屬于S(k),要求你找到另一個整形數y 屬于S(k),y不等于x，并且使得 |x-y|的值最小。

如果僅僅翻譯題目的要求，會陷入困境。

方法：小量資料分析模式，當沒有想法的時候可以用幾組樣例試一下，發現其中的規律。

1. x = 0b1011

   y = 0b1101

2. x = 0b11101

   y = 0b11011

多試幾組就會發現：從最右邊往左走，當第一次發現兩位不同的時候，交換兩位的位置。就會的到滿足條件的y。

代碼實作如下：

int findMinAbs(int x){
    for(int i = 0 ; i < Integer.size ;i++){
        if(swapBit(x,i,i+1) != x){//判斷相鄰兩位是否相等
            return swapBit(x,i,i+1);
        }
    }
    return x;
}