网站备案扫描,建设银行手机绑定网站,天津黑曼巴网站建设,贸易公司网站设计案例题目
输入一个非负数n#xff0c;请计算0到n之间每个数字的二进制形式中1的个数#xff0c;并输出一个数组。例如#xff0c;输入的n为4#xff0c;由于0、1、2、3、4的二进制形式中1的个数分别为0、1、1、2、1#xff0c;因此输出数组[0#xff0c;1#xff0c;1…题目
输入一个非负数n请计算0到n之间每个数字的二进制形式中1的个数并输出一个数组。例如输入的n为4由于0、1、2、3、4的二进制形式中1的个数分别为0、1、1、2、1因此输出数组[01121]。
分析1
很多人在面试的时候都能想到直观的解法使用一个for循环来计算从0到n的每个整数i的二进制形式中1的个数。于是问题转换成如何求一个整数i的二进制形式中1的个数。 计算整数i的二进制形式中1的个数有多种不同的方法其中一种比较高效的方法是每次用“ii-1”将整数i的最右边的1变成0。整数i减去1那么它最右边的1变成0。如果它的右边还有0则右边所有的0都变成1而其左边所有位都保持不变。下面对i和i-1进行位与运算相当于将其最右边的1变成0。以二进制的1100为例它减去1的结果是1011。1100和1011的位与运算的结果正好是1000。二进制的1100最右边的1变为0结果刚好就是1000。
解1
public class Test {public static void main(String[] args) {int[] result countBits(4);for (int res : result) {System.out.println(res);}}public static int[] countBits(int num) {int[] result new int[num 1];for (int i 0; i num; i) {int j i;while (j ! 0) {result[i];j j (j - 1);}}return result;}
}分析2
根据前面的分析可知“ii-1”将i的二进制形式中最右边的1变成0也就是说整数i的二进制形式中1的个数比“ii-1”的二进制形式中1的个数多1。
解2
public class Test {public static void main(String[] args) {int[] result countBits(4);for (int res : result) {System.out.println(res);}}public static int[] countBits(int num) {int[] result new int[num 1];for (int i 1; i num; i) {result[i] result[i (i - 1)] 1;}return result;}
}分析3
还可以使用另一种思路来解决这个问题。如果正整数i是一个偶数那么i相当于将“i/2”左移一位的结果因此偶数i和“i/2”的二进制形式中1的个数是相同的。如果i是奇数那么i相当于将“i/2”左移一位之后再将最右边一位设为1的结果因此奇数i的二进制形式中1的个数比“i/2”的1的个数多1。例如整数3的二进制形式是11有2个1。偶数6的二进制形式是110有2个1。奇数7的二进制形式是111有3个1。我们可以根据3的二进制形式中1的个数直接求出6和7的二进制形式中1的个数。
解3
public class Test {public static void main(String[] args) {int[] result countBits(4);for (int res : result) {System.out.println(res);}}public static int[] countBits(int num) {int[] result new int[num 1];for (int i 1; i num; i) {// 用“i1”计算“i/2”用“i1”计算“i%2”result[i] result[i 1] (i 1);}return result;}
}
