位运算

Last updated 2 years ago

位运算

汉明距离

方法1:数组

public boolean isUnique(String astr) {
    char[] ch = new char[26];
    for (char c : astr.toCharArray()) {
        if (ch[c - 'a'] != 0) return false;
        ch[c - 'a']++;
    }
    return true;
}

方法2:位运算

        public boolean isUnique(String astr) {
            int mark = 0;
            for (char ch : astr.toCharArray()) {
                //拿到每个字符的移动的位数 [0-25]开始
                int bit = ch - 'a';
                //如果这一位被对冲掉，返回false
                if ((mark & (1 << bit)) != 0) {
                    return false;
                } else {
                    //拼凑mark
                    mark |= (1 << bit);
                }
//                PrintUtils.toBinaryString(mark, 26);
            }
            return true;
        }

方法1:基本位运算

public boolean hasAlternatingBits(int n) {
    int t = -1;//初始值
    while (n > 0) {
        //拿到最右边的一位
        int bit = n & 1;
        //如果当前的bit位于上一位t是相同的，则返回false
        //异或（ ^ ）每一位进行比较，相同为0，不同为1
        if ((t ^ bit) == 0) return false;
        //当前位bit 赋值给上一位 t
        t = bit;
        //右移一位
        n >>= 1;
    }
    return true;
}

方法2:高阶位运算

public boolean hasAlternatingBits(int n) {
    n = n ^ (n >> 1);
    return (n & n + 1) == 0;
}

方法3:库函数

public boolean hasAlternatingBits(int n) {
  	//调用库函数
    char[] bits = Integer.toBinaryString(n).toCharArray();
    for (int i = 0; i < bits.length - 1; i++) {
        if (bits[i] == bits[i + 1]) {
            return false;
        }
    }
    return true;
}

方法1:模拟

数据范围不大，模拟即可，两步走，
- step1.统计每一个数二进制数中1的个数，记为bits
- step2.判断bits是否是质数
其中step1的操作:

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：
方法1：
- 第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000
- 第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000
- 第三次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000 我们发现，每计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：
    
count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}  
方法2：见下面的「返回i的二进制最低位位1的权值」
count = 0  
while(a){  
  a -= a & (-a);  
  count++;  
}  
方法3：
count = 0  
while(a){  
  count+=a&1;  
  a >>>= 1;//无符号右移 相当于 /2 
}

public int countPrimeSetBits(int left, int right) {
    int res = 0;
    for (int a = left; a <= right; a++) {
        if (isPrime(count(a))) res++;
    }
    return res;
}


public int count(int a) {
    int cnt = 0;
    while (a > 0) {
        cnt += a & 1;
        a >>= 1;
    }
    return cnt;
}


/**
 * 判断一个数是否是素数
 */
public boolean isPrime(int a) {
    if (a < 2) return false;
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0) return false;
    }
    return true;
}

方法2:打表

注意到数据的范围是100000，转成二进制是11110100001001000000，20位，也就是说每一位都为1的话，也只有20位，需要拿到20位以下质数打表

public int countPrimeSetBits(int left, int right) {
    List<Integer> primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19);
    int cnt = 0;
    for (int i = left; i <= right; i++) {
        int bits = 0;
        for (int x = i; x > 0; x >>= 1) {
            bits += x & 1;
        }
        if (primes.contains(bits)) cnt++;
    }
    return cnt;
}

方法3:DP打表

质数的结果可以通过打表的方式获取，每个数的位数也可以通过打表的方式获取
f[i]表示当前数i的二进制1的个数
- 初始时0的二进制1的个数是0,1的二进制1的个数是1个
- 一般情况下f[i]与i>>1的结果有关，判断下当前位是否是1即可f[i & 1]，

public int countPrimeSetBits(int left, int right) {
    List<Integer> primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19);
    int[] f = count(right);
    int cnt = 0;
    for (int i = left; i <= right; i++) {
        if (primes.contains(f[i])) cnt++;
    }
    return cnt;
}


public int[] count(int x) {
    if (x == 0) return new int[]{};
    int[] f = new int[x + 1];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= x; i++) {
        f[i] = f[i >> 1] + f[i & 1];
    }
    return f;
}

Follow Up

如果left和right的数据范围不是10^6而扩大到10亿，如何优化算法

我能想到的是通过埃筛的方式快速的筛质数，然后打表
你会如何做呢？欢迎评论区留言~

public int binaryGap(int n) {
    //前一个为1的位置的索引，当前的索引
    int prev = -1, cur = 0;
    int gap = 0;
    while (n > 0) {
        //记录下当前位为1的索引，如果满足更新gap的条件，开始更新
        if ((n & 1) == 1) {
            if (prev != -1) gap = Math.max(gap, cur - prev);
            prev = cur;
        }
        n >>= 1;//向右移位，去掉一位
        PrintUtils.toBinaryString(n,8);
        cur++;//当前位+1
    }
    return gap;
}

扩展阅读

Previous博弈问题 Next数学

Last updated 2 years ago