之前面试遇到过这样的问题:写一个方法,统计出一个int型数值中比特值为1的比特个数,后来群里也讨论过,在这里总结一下。
直观的看一下这个问题的解法。
假设一个int型数值为80。
首先,将这个数值转化成二进制形式。
80 = 00000000 00000000 00000000 01010000
然后数一数为1的bit有几个,很明显是2个,那么结果就是2。
但是写程序要怎么做呢?
首先看一个小技巧,x & (x-1)会把x中最右边为1的bit变成0,利用这个小技巧我们可以写出下面的程序:
public static int bitCount(int n){
int count = 0;
while(n != 0){
n = n & (n-1);
count++;
}
return count;
}
这个过程相当于从右往左数1的个数,假设n为-1,就得数32次,相当于一个线性时间的操作,有没有更好的呢?
在Hackers Delight里面介绍了很好的技巧。
这种技巧是一种分治的思想,假设我们要求32位数值的bit-1个数,我们只要计算出前16位和后16位的bit-1个数,然后把他们加起来就行了,那么对于16位的bit-1个数的求法,我们采取同样的方式...直到我们计算2位bit-1个数的时候,我们只要把两个1位bit的值加起来就好了,这相当于是子问题的基本情况,递归的出口。
下面的图展示了这个过程:
注:图片来之Hackers Delight。
按照这个思路,我们便可以写出如下代码:
public static int bitCount1(int n){
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
return n;
}
相对于上面线性时间的求法来说,这个"分治"的求法只用了log(32)=5步便完成了运算,非常巧妙。
但是。这个还能优化,首先想一下结果最大也就是32了,所以可以减少一些"与"操作,在最后让n和0x0000003f相与就行了。从上图可以看出,当我们在进行8位到16位步骤的时候,8位的高4位对于我们来说已经没用了,所以从这里开始,我们可以不管高位,减少"与"操作,这样能减少一些指令。
代码如下:
public static int bitCount1(int n){
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 0x0000003f;
}
其实n可以看成是(n & 0x55555555)加上(((n >>> 1) & 0x55555555) << 1),也就是
n = (n & 0x55555555) + (((n >>> 1) & 0x55555555) * 2)
(n & 0x55555555) = n - (((n >>> 1) & 0x55555555) * 2)
将这个代入上面的程序,就得到如下代码:
public static int bitCount2(int n){
n = n - ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 0x0000003f;
}
这样一来,代码的第一行又减少了一个指令。
OK!
这段代码也被Java采用作为Integer类中bitCount方法的实现。
- 大小: 44.5 KB
分享到:
相关推荐
C语言06-外中断INT0-INT1-INT2-INT3- INT4测试(STC32G-DEMO-CODE-220311kw)C语言06-外中断INT0-INT1-INT2-INT3- INT4测试(STC32G-DEMO-CODE-220311kw)C语言06-外中断INT0-INT1-INT2-INT3- INT4测试(STC32G-DEMO...
C51单片机-外中断INT0-INT1-INT2-INT3- INT4测试
程序使用的是STC12C5A系列单片机,程序功能是,INT0-INT1-外中断测试
long型转换为int型 long型转换为int型 long型转换为int型 long型转换为int型 long型转换为int型 long型转换为int型 long型转换为int型 long型转换为int型 long型转换为int型 long型转换为int型 long型转换为int型 ...
4附加题:用循环求 任意一个int类型的数字里面含有多少个 1. 用java 实现的小程序实例 while(i){ if(((j>>i)&1)==1){ a++; } i++; }
Fatigue analysis using ANSYS
2.首先来两个int类型的数据(或double型): 4.将int型(double型)转换为QByteArray型: 5.QString与QByteArray之
S7-200SMART中如何把1个INT整型数据转换成REAL浮点型数据?
用于windows安装python工具包过程中缺少stdint.h的情况。
Chatglm2-6b-int4资源文件
padis-int人口预测软件
int[] a = { 4, 2, 1, 3, 5 }; int[] b = { 2, 3, 5 ,6,7}; 获得的结果 [4, 1, 6, 7] (先是a中与b中不同的数字,再是b中与a中不同的数字)
本文为Aldec的linting工具ALINT-PRO的中文培训材料,由Aldec中国的区域技术经理进行翻译、整理和撰写后发布,包含基本操作、快速上手实验等。
S-VNX2__-021003WF-INTCN-64BIT_.exe
单片机外部中断测试,利用LED显示来判断外部中断可用性。
定义一个方法传入一个 int 类型数组,输出这个数组中每一个数字及其出现的个数 例如 传入数组[1,2,2,2,3,3,4,4,4,4] 打印结果: 数字 1 出现了 1 次 数字 2 出现了 3 次…
● Goal: Convert FP32 CNNs into INT8 without significant accuracy loss. ● Why: INT8 math has higher throughput, and lower memory requirements. ● Challenge: INT8 has significantly lower precision and...
caffe的int8的量化工具,float32转int8,压缩至原来的4倍左右。
已编译Zint动态库-VS2015
aldec alint 是一个设计规则的设定与检查的工具,用于规范FPGA的代码编写