位运算|比特位计数、汉明距离

位运算|比特位计数、汉明距离

338 比特位计数

/**

• 比特位计数
• 法一：Brian Kernighan 算法的原理是：对于任意整数 x，令 x=x & (x?1)，
• 该运算将 x 的二进制表示的最后一个 1 变成 0。
• 因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
• 法二：bits[x]=bits[x-y]+1，y为2的整数次幂，y&(y-1)=0
  */

/**
 * 比特位计数
 * 法一：Brian Kernighan 算法的原理是：对于任意整数 x，令 x=x & (x?1)，
 * 该运算将 x 的二进制表示的最后一个 1 变成 0。
 * 因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
 *
 * 法二：bits[x]=bits[x-y]+1，y为2的整数次幂，y&(y-1)=0
 */
public class $338 {
    //动态规划-最高有效位
    public int[] countBits2(int n) {
        int[] bits = new int[n+1];
        int highBit = 0;

        for (int i = 1; i <= n; i++) {
            if ((i & (i-1)) == 0) {
                highBit = i;
            }

            bits[i] = bits[i-highBit] + 1;
        }
        return bits;
    }
}

/**
 * 比特位计数
 * 法一：Brian Kernighan 算法的原理是：对于任意整数 x，令 x=x & (x?1)，
 * 该运算将 x 的二进制表示的最后一个 1 变成 0。
 * 因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
 *
 * 法二：bits[x]=bits[x-y]+1，y为2的整数次幂，y&(y-1)=0
 */
public class $338 {
    //动态规划-最高有效位
    public int[] countBits2(int n) {
        int[] bits = new int[n+1];
        int highBit = 0;

        for (int i = 1; i <= n; i++) {
            if ((i & (i-1)) == 0) {
                highBit = i;
            }

            bits[i] = bits[i-highBit] + 1;
        }
        return bits;
    }
}

461 汉明距离

/**
 * 汉明距离
 * s=x^y
 * 求s的比特位中1的数量
 * 法一：内置函数
 * 法二：z&=z-1
 * 法三：不断地检查 s 的最低位，如果最低位为 1，那么令计数器加一，
 * 然后我们令 s 整体右移一位，这样 s的最低位将被舍去，原本的次低位就变成了新的最低位。
 * 我们重复这个过程直到 s=0 为止。这样计数器中就累计了 s的二进制表示中 1 的数量。
 */
public class $461 {
    public int hammingDistance(int x, int y) {
        int z = x ^ y;

        return Integer.bitCount(z);

//        int cnt = 0;
//        while (z != 0) {
//            z = z & (z-1);
//            cnt++;
//        }
//        return cnt;

//        int cnt = 0;
//        while (z != 0) {
//            cnt += z & 1;
//            z >>= 1;
//        }
//        return cnt;
    }
}