> 六 种 求二进制数中1的个数 算法 java 实现
六 种 求二进制数中1的个数 算法 java 实现
xiangjigen & &
发布时间： & &
浏览：1 & &
回复：0 & &
悬赏：0.0希赛币
6 种 求二进制数中1的个数 算法 java 实现
　　package BitC
* 任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4
* @author vivizhyy
public interface BitCountMethods {
/** 移位+计数 */
public int normal(int x);
/** 不断清除x的二进制表示中最右边的1，同时累加计数器，直至x为0 */
public int quick(int x);
* @see #static8bit(int)
public int static4bit(int x);
* 首先构造一个包含256个元素的表table，table[i]即i中1的个数，这里的i是[0-255]之间任意一个值。
* 然后对于任意一个32bit无符号整数n
* ，我们将其拆分成四个8bit，然后分别求出每个8bit中1的个数，再累加求和即可，这里用移位的方法，每次右移8位
* ，并与0xff相与，取得最低位的8bit
* ，累加后继续移位，如此往复，直到n为0。所以对于任意一个32位整数，需要查表4次。以十进制数为例
* ，其对应的二进制数为
* ，对应的四次查表过程如下：红色表示当前8bit，绿色表示右移后高位补零。
* 第一次（n & 0xff）
* 第二次（(n $>$ 8) & 0xff）
* 第三次（(n $>$ 16) & 0xff）
* 第四次（(n $>$ 24) & 0xff）
public int static8bit(int x);
/** 先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。
public int parallel(int x);
public int perfectness(int x);
　　package BitC
public class BitCounts implements BitCountMethods {
public int normal(int x) {
int c = 0;
for (; x & 0; x $>>$= 1) {
c += x & 1; // 如果当前位是 1，计数器加 1
public int quick(int x) {
int c = 0;
for (; x & 0; c++) {
x &= (x - 1); // 清除最右边的 1
public int static4bit(int x) {
int[] table = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
int c = 0;
for (; x & 0; x $>>$= 4) {
c += table[x & 0xF];
public int static8bit(int x) {
int[] table = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2,
2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3,
4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,
4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2,
3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4,
4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5,
6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,
4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5,
5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5,
4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5,
6, 6, 7, 6, 7, 7, 8, };
int c = 0;
for(; x & 0; x $>>$= 8){
c += table[x & 0xFF];
public int parallel(int x) {
x = (x & 0x) + ((x $>>$ 1) & 0x);
x = (x & 0x) + ((x $>>$ 2) & 0x);
x = (x & 0x0f0f0f0f) + ((x $>>$ 4) & 0x0f0f0f0f);
//0x00ff = 11 1111
x = (x & 0x00ff00ff) + ((x $>>$ 8) & 0x00ff00ff);
//0x0000ffff = 00 11
x = (x & 0x0000ffff) + ((x $>>$ 16) & 0x0000ffff);
public int perfectness(int x) {
int temp = x - (x $>>$ 1) &
- (x $>>$ 2) & ;
return (temp +(temp $>>$3)) &
　　package BitC
import static org.junit.Assert.*;
import org.junit.T
public class BitCountMethodsTest {
BitCountMethods bcm = new BitCounts();
int x = 123;
public final void testNormal() {
assert(bcm.normal(x) == 6);
public final void testQuick() {
assert(bcm.quick(x) == 6);
public final void testStatic4bit() {
assert(bcm.static4bit(x) == 6);
public final void testStatic8bit() {
assert(bcm.static8bit(x) == 6);
public final void testParallel() {
assert(bcm.parallel(x) == 6);
public final void testPerfectness() {
assert(bcm.perfectness(x) == 6);
本问题标题：
本问题地址：
温馨提示：本问题已经关闭，不能解答。
暂无合适的专家
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&算法的强大——快速计算一个正二进制整数中包含多少个1
我的图书馆
算法的强大——快速计算一个正二进制整数中包含多少个1
　　原题：一个正整数，转成二进制后，这个二进制数包含多少个1？
　　这个问题在网上看过多次，几番思考，也没有什么好的办法。采用最基本的办法，逐位判断，是1的统计加1，最后将统计数返回。
　　以下是这个思路的VB2008代码，不失一般性，将正整数的范围控制在（1~231-1）
　　Private Function&GetCount1OfValue(ByVal&Value&As Integer)&As Integer　　　　Dim&i&As Integer, Count&As Integer&= 0　　　　For&i = 0&To&30　　　　　　If&(Value&And&2 ^ i) = 2 ^ i&Then&Count += 1　　　　Next　　　　Return&Count　　End Function
　　但是近日，在网上发现一个很巧妙的算法，能够快速实现上述的计算功能。代码贴于下方
　　Private Function&GetCount1OfValue(ByVal&Value&As Integer)&As Integer　　
　　　　Dim&Count&As Integer&= 0
　　　　Do While&Value & 0
　　　　　　Value = Value&And&(Value - 1)
　　　　　　Count +=1
　　　　Loop
　　　　Return&Count
　　End Function
　　这段代码的精髓就是在这一句：Value = Value And (Value - 1)
　　曾经用过类似语句的在我的博客“”
　　那么这句语句到底起到什么作用呢？看下面的分析
　　假设Value=X1X2……Xn-1Xn，其中Xi(1≤i≤n)为1或0
　　不妨设Xi是最右边的1，那么Value就可以写成如下的形式
　　Value=X1X2……Xi-1Xi0……0，其中(1≤i≤n)，Xi后面有n-i个0
　　因为Xi=1，所以Value=X1X2……Xi-110……0，其中(1≤i≤n)，1后面有n-i个0
　　则Value-1=X1X2……Xi-101……1，其中(1≤i≤n)，0后面有n-i个1
　　则Value And (Value-1)=X1X2……Xi-100……0，其中(1≤i≤n)，Xi-1后面有n-i+1个0
　　因此，Value And (Value-1)的效果把最右边的1变成0
　　在上面的代码中，每把最右边的1变成0，则统计数加1，直到所有的1变成0为止。
　　这两个算法，第一个算法的循环次数是固定的，是31次，无论数值是多少（必须在范围之内）。而第二个算法和Value中的1的个数有关，循环的次数就是1的个数，可见该算法之妙。
TA的最新馆藏[转]&[转]&如何利用汇编判断一个8位二进制数里有几个0
09-03-22 &匿名提问
2．二进制数 在计算机中，由于其物理特性（只有两种状态：有电、无电）的原因，所以在计算机的物理设备中获取、存储、传递、加工信息时只能采用二进制数。二进制数是由两个数字0、1任意组合构成的，其特点是逢二进一。例如：1001，这里不读一千零一，而是读作：一零零一或幺零零幺。为了与其它的数制的数区别开来，我们在二进制数的外面加括号，且在其右下方加注2，或者在其后标B。 任何一个二进制数亦可拆分成由各位数字与其对应的权的乘积的总和。其整数部分的权由低向高依次是：1、2、4、8、16、32、64、128、……，其小数部分的权由高向低依次是：0.5、0.25、0.125、0.0625、……。 二进制数也有其运算规则： 加法：0+0=0????0+1=1???1+0=1????1+1=10 乘法：0×0=0????0×1=0????1×0=0????1×1=1 二进制数与十进制数如何转换： （1） 二进制数—→十进制数 对于较小的二进制数： 对于较大的二进制数： 方法1：各位上的数乘权求和??例如： （=1×25+0×24+1×23+1×22+0×21+1×20=45 （）2=1×23+1×22+0×21+0×20+1×2-1+1×2-2+0×2-3+1×2-4=12.8125 方法2：任何一个二进制数可转化成若干个100…0?的数相加的总和??例如： （=（+（1000）2+（100）2+（1）2 而这种100…00形式的二进制数与十进制数有如下关联：1后有n个0，则这个二进数所对应的十进制数为2n。 所以：（=（+（1000）2+（100）2+（1）2=25+23+22+20=45 （2）十进制数—→二进制数 整数部分：整除以2取余法。例如：75 75/2=37…1??37/2=18…1??18/2=9…0??9/2=4…1??4/2=2…0??2/2=1…0???1/2=0…1 将得到的一系列的余数倒过来书写就得到该数所对应的二进制数（ 小数部分：乘以2取整法。例如：0.7 0.7×2=1.4…1??0.4×2=0.8…0???0.8×2=1.6…1???0.6×2=1.2…1??0.2×2=0.4…0
请登录后再发表评论!
先定义一个变量：ＢＩＴＦＬＡＧ　＝０１Ｈ然后用ＴＥＳＴ指令将数据与ＢＩＴＦＬＡＧ比较，不为０则计数器加１然后ＢＩＴＦＬＡＧ　左移１位，在比较，依次循环８次
请登录后再发表评论!}