汉明重量 & 位运算应用
汉明重量
它是一种特殊的汉明距离。指一个字符串与一个等长的“零”字符串 的汉明距离,即一个字符串中非零的字符个数。
题目描述
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数
public int hammingWeight(int n) {
int bits = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask) != 0) {
bits++;
}
mask <<= 1; //从最右边开始挨个往左比对
}
return bits;
}
改进版:
(图片参考自 :https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode/)
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
// int[] nums = new int[32];
int count = 0;
while(n!=0){
n &= (n-1);
count++ ;
}
return count;
}
}
汉明距离
它是一种概念。即两个等长的字符串对应位置上的字符不同的个数 。
在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如:
1011101 与 1001001 之间的汉明距离是 2。
2143896 与 2233796 之间的汉明距离是 3。
"toned" 与 "roses" 之间的汉明距离是 3。
位运算常用技巧
两数交换
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
优点是不会产生精度缺失
判断奇偶
只要根据最未位是0还是1来决定,为0就是偶数,为1就是奇数。
因此可以用if ((a & 1) == 0)
代替if (a % 2 == 0)
来判断a
是不是偶数。
优点是可以判断负数的奇偶性
取绝对值
int my_abs(int a)
{
int i = a >> 31;
return i == 0 ? a : (~a + 1);
}