[数据结构与算法]Leetcode刷题之位运算（Java）

位运算是算法题中比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括：

^  按位异或
&  按位与
|  按位或
~  取反
<< 左移位
>> 右移位

力扣例题

461. 汉明距离

分析：

异或运算保留不同的二进制的位，&1取出最后一位，>>向右移位。

题解：

class Solution {
    public int hammingDistance(int x, int y) {
    	//将两数进行按位异或运算，将二进制位不同的位置为1
    	int n = x ^ y;
    	int count = 0;
    	System.out.println("source n: "+Integer.toBinaryString(n)+"\n");
    	
    	while(n!=0) {
    		//每次取得最后一位计入结果
    		count += n&1;
    		System.out.println("n&1: " + Integer.toBinaryString(n&1));
    		//记录后向右移位
    		n >>= 1;
    		System.out.println("n >>= 1: "+Integer.toBinaryString(n)+"\n");
    	}
    	
    	return count;
    }
}

190. 颠倒二进制位

分析：

将n视作一个长为32的二进制串，从低位往高位枚举n的每一位，将其倒序添加到反转结果reverse中。

题解：

class Solution {
	public int reverseBits(int n) {
        int reverse = 0;
        //整形有32位，对每一位逐个处理
        for(int i=0;i<32;++i) {
        	//将reverse左移一位，留出最低位
        	reverse <<= 1;
        	//将reverse最低位赋值为n的最后一位
        	reverse += n&1;
        	//将n右移一位
        	n >>= 1;
        }
        return reverse;
    }
}

136. 只出现一次的数字

分析：

x ^ x = 0；x ^ 0 = x。将数组内的所有数字异或，出现两次的数字异或结果为0，0与出现一次的数字异或可以得到数字本身。

同种位运算满足交换律和结合律。

题解：

class Solution {
    public int singleNumber(int[] nums) {
    	int ans = 0;
    	for(int i=0;i<nums.length;++i) {
    		ans ^= nums[i];
    	}
    	return ans;
    }
}

342. 4的幂

分析：

可以先保证是2的幂，再次基础上利用4的幂对3取模余数为1的性质得到答案。

对于2的幂有：n & (n-1) = 0

题解：

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
}

318. 最大单词的长度乘积

分析：

因为这里并不在意字符串中字母的顺序，因此可以为每个字符串创建一个长为26的二进制串，包含了的字母位置为1。这样按位与运算后，有相同字母的字符串不为0。

题解：

class Solution {
	public int maxProduct(String[] words) {
    	int n = words.length;
    	int[] binary = new int[n];
    	
    	for(int i=0;i<n;++i) {
    		int len = words[i].length();
    		for(int j=0;j<len;++j) {
					//这个得到对应位为1的二进制串的方法需要想通
    			binary[i] |= 1 << (words[i].charAt(j)-'a');
    		}
    	}
    	
    	int max = 0;
    	for(int i=0;i<n;++i) {
    		for(int j=i+1;j<n;++j) {
    			if((binary[i]&binary[j]) == 0) {
    				max = Math.max(max, words[i].length()*words[j].length());
    			}
    		}
    	}
    	
    	return max;
    }
}

338. 比特位计数

分析：

可以结合位运算与动态规划，设dp[i]表示i的二进制串中1的个数。如果i的最后一位是1的话，dp[i] = dp[i-1]+1；如果i的最后一位是0的话，dp[i] = dp[i>>1]，相当于忽略最后一位。

题解：

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n+1];
        
        for(int i=1;i<=n;++i) {
        	if((i&1)==1) {
        		dp[i] = dp[i-1]+1;
        	}
        	else {
        		dp[i] = dp[i>>1];
        	}
        }
        
        return dp;
    }
}