大连seo顾问,长沙网站seo推广,免费网站流量,网页制作素材模板【问题描述】[简单] 【解答思路】
1. 内置位计数功能
时间复杂度#xff1a;O(1) 空间复杂度#xff1a;O(1)
class Solution {public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y); }
}2. 移位 时间复杂度#xff1a;O(1) 空间复杂度#xff1…【问题描述】[简单] 【解答思路】
1. 内置位计数功能
时间复杂度O(1) 空间复杂度O(1)
class Solution {public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y); }
}
2. 移位 时间复杂度O(1) 空间复杂度O(1)
class Solution {public int hammingDistance(int x, int y) {int xor x ^ y;int distance 0;while (xor ! 0) {if (xor % 2 1)distance 1;xor xor 1;}return distance;}
}
3. 布赖恩·克尼根算法 Brian Kernighan 时间复杂度O(1) 空间复杂度O(1)
class Solution {public int hammingDistance(int x, int y) {int xor x ^ y;int distance 0;while (xor ! 0) {distance 1;// remove the rightmost bit of 1xor xor (xor - 1);}return distance;}
}【总结】
1. 汉明距离 2. 位运算
异或运算^ 运算规则0^00 0^11 1^01 1^10 即参加运算的两个对象如果两个相应位为“异”值不同则该位结果为1否则为0。 5 ^ 1 0101 ^ 0001 0100 4 5 ^ 3 0101 ^ 0011 0110 6 用法
翻转指定位 对应位异或1 X10101110使X低4位翻转用X ^0000 1111 1010 0001即可得到。两个数是否相等 0 5 ^ 5 0101 ^ 0101 0000 0
与运算 运算规则000; 010; 100; 111; 即两位同时为“1”结果才为“1”否则为0 5 1 0101 0001 0001 1 5 2 0101 0010 0000 0 用法 取指定位 对应位与1 设X10101110 取X的低4位用 X 0000 1111 00001110 即可得到
或运算| 运算规则0|00 0|11 1|01 1|11 即 参加运算的两个对象只要有一个为1其值为1 用法 指定位置置1 对应位或1 将X10100000的低4位置1 用X | 0000 1111 1010 1111即可得到
取反运算~ 运算规则~10 ~01 即对一个二进制数按位取反即将0变11变0
带符号左移运算 若左移时舍弃的高位不包含1则每左移一位相当于该数乘以2(右边补0) 3 1 0011 1 0110 6 带符号右移运算 正数操作数每右移一位相当于该数除以2 (左补0 or 补1得看被移数是正还是负) 5 1 0101 1 0010 2 5 2 0101 2 0001 1 -14 2 11110010 2 11111100 -4 无符号右移运算 5 1 0101 1 0010 2 -14 2 11111111 11111111 1111111111110010 2 00111111 11111111 1111111111111100 1073741820 移位总结
正数的左移与右移负数的无符号右移就是相应的补码移位所得在高位补0即可。负数的右移就是补码高位补1,然后按位取反加1即可。
3. 位运算 判相等换位异或^ 取位与1 置位或|1
4. Brian Kernighan算法
n(n-1) //n二进制最右位的 1 置 0
相关题目Brian Kernighan算法 [Leetcode][第201题][JAVA][数字范围按位与][位运算][Brian Kernighan]
转载链接https://leetcode-cn.com/problems/hamming-distance/solution/yi-ming-ju-chi-by-leetcode/
