麦包包在网站建设方面,WordPress子站站群,论坛网站备案,wordpress 数字交易位移的妙用
1、位1的个数
1.1、题目描述
LeetCode191. 编写一个函数#xff0c;输入是一个无符号整数(以二进制串的形式)#xff0c;返回其二进制表达式中数字位为 ‘1’ 的个数。 示例1#xff1a; 输入#xff1a;00000000000000000000000000001011 输出#xff1…位移的妙用
1、位1的个数
1.1、题目描述
LeetCode191. 编写一个函数输入是一个无符号整数(以二进制串的形式)返回其二进制表达式中数字位为 ‘1’ 的个数。 示例1 输入00000000000000000000000000001011 输出3 示例2 输入00000000000000000100000000000000 输出1 1.2、问题分析与解答
首先我们可以根据题目要求直接计算题目给定的n是32位二进制表示下的一个整数计算位1的个数的最简单的方法就是遍历n的二进制表示的每一位判断每一位是否为1同时进行计数。
那么怎么判断某一位是否为1呢例如00001001001000100001100010001001首先我们注意要识别到最低位的1可以这么做
00001001001000100001100010001001 00000000000000000000000000000001 00000000000000000000000000000001 也就是说将原始数字和1进行与运算就能知道最低位是不是为1了那其他位置该怎么算呢
第一种思路是让原始数据不断右移或者是让1不断左移。例如将原始数据右移1位
00000100100100010000110001000100 00000000000000000000000000000001 00000000000000000000000000000000 很显然此时可以判断出第二位是0然后依次将原始数据右移就能判断出每个位置是否为1了。因此是不是1计算一下(n i) 1就可以了代码如下
public int hammingWeight(int n) {int count 0;for (int i 0; i 32; i) {count (n i) 1;}return count;
} 除了上述方法外还有一种方法
按位与运算有一个性质对于整数n计算n (n - 1)的结果为将n的二进制表示的最后一个1变为0。
利用这条性质令n n (n - 1)则n的二进制表示中的1的数量减少一个。重复该操作知道n的二进制表示中的全部数位变为0则操作次数即为n的位1的个数还是看上面的例子
n: 00000100100100010000110001000100
n-1: 00000100100100010000110001000011
n(n-1): 00000100100100010000110001000000 可以看到此时n(n-1)的结果比上一个n少了一个1如果一直循环执行的话到最后n等于0时退出循环这时循环的次数就是原来n中1的个数代码如下
public int hammingWeight(int n) {int count 0;while (n ! 0) {n n (n - 1);count;}return count;
}2、比特位计数
2.1、问题描述
LeetCode338. 给你一个整数n对于 0 i n 中的每一个i计算其二进制表示中1的个数返回一个长度为n 1的数组ans作为答案。 示例: 输入n2 输出[0, 1, 1] 解释0到n有012三个数字每个数字含有1的个数分别为0 1 1个如下 0 -- 0 1 -- 1 2 -- 10 2.2、问题分析与解答
本题是上题的扩展可以直接遍历0到n的每个数在遍历的过程中对每个数计算其位1的个数。
代码如下
public int[] countBits(int n) {int[] bits new int[n 1];for (int i 0; i n; i) {bits[i] countOnes(i);}return bits;
}public int countOnes(int x) {int ones 0;while (x 0) {x x (x - 1);ones;}return ones;
}
