EPI_PrimitiveTypes_No.002_SwapBi

题目描述

给一个64位整型数，看做一个64位数组，低位为index=0，即73=0b0100_1001，最低位1对应序号0.给出整数n和两个序号i和j，交换对应的比特，假设i和j总是在有效范围内。

思考过程

1. 暴力破解
   因为是2进制数，每一位只有0和1两种情况，那么i和j两个位置也就4种情况，可以一个个分别解决。
   至于如何提取那一位数，可以用一个1然后左移i或者j位，再与原来的数相与。但这样做有一个问题，就是如果有1的话在高位。
   因此可以考虑另一个做法：n右移i位，然后与1相与。

2. 更优雅的解法
   有几个事实：
   假如i和j对应位置上的数一样的话，就无需交换；
   假如不一样，那么必定是一个0和一个1，交换它们也就相当于就地取反。
   因此，可以得到一个更为优雅的解法：首先判断两位是否相等，如果不等则取反即可。

public static long swapBits(long x, short i, short j){
        // Extract the i-th and j-th bits, and see if they differ.
        if (((x >>> i) & 1) != ((x >>> j) & 1)){
        // i-th and j-th bits differ. We will swap them by flipping their values.
        // Select the bits to flip with bitMask. Since x^1 = 0 when x = 1 
        // and 1 when x = 0, we can perform the flip XOR .
        long bitMask = (1L << i)|(1L << j);
        x ^= bitMask;
        }
        return x ;
}

时间复杂度为O(1)。

总结

基础的位操作题，有几个要点：
如何判断某一个特定位是0还是1？(x >>> i) & 1
如何对某一个特定位取反？x ^=(1L << i)