开始找工作了,笔试面试中难免会碰到一些算法题,准备从今天开始,每天总结一些值得注意的题目。
现在主要从【编程之美】这本书中摘选吧。
题目:对于一个字节(8位)的无符号整型变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能高。
书中总共给出了五种解法,我觉得比较实用的就前三种,后两种(使用分支操作和查表法现实中很难用到)
最好的方法当然是第三种了,当位数多时,效果更明显。
public class BinaralySearch {
public static void main(String[] args) {
int i = 444444444; //十进制数
String binary = Integer.toBinaryString(i);
System.out.println("Binary value of " + i + " is " + binary + ".");
System.out.println(count1(i));
System.out.println(count2(i));
System.out.println(count3(i));
}
//解法一,根据除法的特性,如果除以2余1,说明当前位为1
public static int count1(int a){
int count=0;
while(a>0){
if(a%2==1)count++;//除2余1
a/=2;
}
return count;
}
//解法二,除2可以用右移一位来实现
//同时,判断最后一位是否为1也可以用&操作来实现
public static int count2(int a){
int count=0;
while(a>0){
count+=a&0x01;//用&操作判断最后一位是否为1
a>>=1;
}
return count;
}
//解法一,二的本质都是相同的,都是用除2来实现的,得循环8次
//解法三的思路很巧,只需循环1的个数次即可
//每次循环都把最低位的1去掉了
public static int count3(int a){
int count=0;
while(a>0){
count++;
a&=(a-1);//通过&运算把最低位的1变成0
}
return count;
}
}
扩展问题1:如果是32位时,应该用哪种方法,显然应该用第三种
扩展问题2:判断整数A和B的二进制表示中有多少位是不同的。
A,B先做异或,再求1的个数,
public static int differentBit(int a,int b){
return count3(a^b);
}
分享到:
相关推荐
对于一个字节(8bit)的变量,求其二进制表示中“1”的个数,要求算法的执行效 率尽可能地高。
(android demo)算法实现:计算十进制数N的二进制形式中包含数字1的个数
C++计算一个数字的二进制中0或1的个数原理及代码
d行对应每个测试数据,把转换成的2进制数中哪一位是1的位数输出,按升序排列。 (比如说1101,它的第3位是1,第2位是1,第1位是0,第0位是1,所以输出 0 2 3) 输入样例: 1 13 输出样例: 0 2 3
判断32位无符号整数二进制中1的个数,与大家分享下。不是原创
二进制中 1 的个数请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。示例 1:输入:000000000000000000000000000010
统计整数的二进制表示形式中有几个1(java实现),代码中有三种方法,分别是利用除、余的方法,位运算,以及利用“与”运算的方法。其中第三种方法效率最高,二进制数中有几个1,算法中的循环内的运算就执行几次。
二进制中1的个数.md
汇编实现统计输入数据中1的个数,转换为二进制判断
Delphi - 判断一个二进制数中有多少个1.mht
java基础面试题二进制中1的个数本资源系百度网盘分享地址
二进制位不同的个数 Time Limit:1000MS Memory Limit:65536KB Total Submit:16 Accepted:9 Description 对于两个非负整数x 和y,函数f(x,y) 定义为x 和y 在二进制表示时,其对应位不同的个数。例如,f(2,3)=1, f...
15. 二进制中 1 的个数题目链接牛客网题目描述输入一个整数,输出该数二进制表示中 1 的个数。解题思路n&(n-1) 位运算可以将 n 的位级表示中最低的那
801. 二进制中1的个数算法:#位运算每次减去给定整数 x 二进制中的最后一位 1(lowbit(n) = n & -n),一共能减几次 x 二进制中就有几个
介绍了二进制中1的个数,有需要的朋友可以参考一下
课程设计——统计一个数二进制表示中1的个数
题目输入一个整数,输出该数32位二进制表示中1的个数(其中负数用补码表示)示例输入输出题解二进制移位法//将 mark0x01 和 n 进行 ‘&’ 运算//
剑指 Offer 15. 二进制中1的个数方法一:位运算* @param {number} n - a positive integervar hammingW
将一个整数转换为二进制形式,统计二进制数中1的个数,如果是负数,按补码统计1的个数 def oneNumber(n): print(bin(n)) if n < 0: # 在python中,负数与0xFFFFFFFF按位与,实际上按照语法,负数在做与操作...