Leetcode Tags(13)Bit Manipulation
发布时间:2020-12-14 03:46:33 所属栏目:大数据 来源:网络整理
导读:一、477.汉明距离总和 输入: 4 , 14 , 2 输出: 6 解释: 在二进制表示中,4表示为0100,14表示为1110,2表示为0010。(这样表示是为了体现后四位之间关系)HammingDistance( 4 , 14 ) + HammingDistance( 4 , 2 ) + HammingDistance( 14 , 2 ) = 2 + 2 + 2 =
一、477.汉明距离总和 输入: 4,14,2 输出: 6 解释: 在二进制表示中,4表示为0100,14表示为1110,2表示为0010。(这样表示是为了体现后四位之间关系) HammingDistance(4,14) + HammingDistance(4,2) + HammingDistance(14,2) = 2 + 2 + 2 = 6. 1.常规做法,Time Limit Exceeded public int totalHammingDistance(int[] nums) { int sum = 0; int xor = 0; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { xor = nums[i] ^ nums[j]; while (xor != 0 ) { if ((xor & 1) == 1) sum++; xor = xor >> 1; } } } return sum; } 2.更快的做法 public int totalHammingDistance(int[] nums) { int total = 0,n = nums.length; for (int j=0;j<32;j++) { int bitCount = 0; for (int i=0;i<n;i++) bitCount += (nums[i] >> j) & 1; total += bitCount*(n - bitCount); } return total; } 这是因为: 假设4,14,2,则 0 1 0 0 1 1 1 0 0 0 1 0 那么,从第4列开始看,1在的位数为0 第3列1的位数为2:2 *(3-2) 第2列1的位数为2:2 *(3-2) 第1列1的位数为1:1 *(3-1) 也就是说,如果有bitcount个1,n-bitcount个0,那么这bitcount个1分别和n-bitcount个0搭配都能成为1和0,也就是bitcount * (n-bitcount)个 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |