|
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-12-06
看了几遍，觉得都有道理，具体什么情况，咱们测一下
目前三种方法我都列出来，不知道我写的是不是和大家写的有出入，如果有请指正 public class CountBit {
public static void main(String[] args) {
CountBit cnt = new CountBit();
long start = System.currentTimeMillis();
int times = 100000000;
cnt.testAdvanceVersion(times);
long p0 = System.currentTimeMillis();
cnt.testLoopVersion(times);
long p1 = System.currentTimeMillis();
cnt.testJDKVersion(times);
long p2 = System.currentTimeMillis();
System.out.println(""+times+"次均匀分布");
System.out.println("使用编程之美算法,单位（毫秒）：");
System.out.println(p0-start);
System.out.println("使用循环移位算法,单位（毫秒）：");
System.out.println(p1-p0);
System.out.println("使用JDK改版算法,单位（毫秒）：");
System.out.println(p2-p1);
}
/**
* jdk的算法改byte版，纯粹使用位操作
* @param b byte value
* @return count of 1
*/
public int bitCountJDK(byte b) {
int i = (b>>>31<<7) + (b&0x7F);
i = (i&0x55)+(i>>>1&0x55);
i = (i&0x33)+(i>>>2&0x33);
return (i&0x0F)+(i>>>4);
}
/**
* 编程之美的算法
* @param b byte value
* @return count of 1
*/
public int bitCountAdvance(byte b) {
int i = (b>>>31<<7) + (b&0x7F);
int result = 0;
while(i!=0) {
result++;
i&=i-1;
}
return result;
}
/***
* 移位、循环的算法
* @param b byte value
* @return count of 1
*/
public int bitCountLoop(byte b) {
int i = (b>>>31<<7) + (b&0x7F);
int result = 0;
while(i!=0) {
result+= i&1;
i>>>=1;
}
return result;
}
private void testAdvanceVersion(int times) {
for(int i=0;i<times;i++) {
bitCountAdvance((byte)((i&255)-128));
}
}
private void testLoopVersion(int times) {
for(int i=0;i<times;i++) {
bitCountLoop((byte)((i&255)-128));
}
}
private void testJDKVersion(int times) {
for(int i=0;i<times;i++) {
bitCountJDK((byte)((i&255)-128));
}
}
}
得到结果 100000000次均匀分布 使用编程之美算法,单位（毫秒）： 1641 使用循环移位算法,单位（毫秒）： 1282 使用JDK改版算法,单位（毫秒）： 770 让我很吃惊的是 编程之美那个算法是最差的。 本以为在均匀的情况下jdk应该是最快的，编程之美第二、循环移位最慢。 欢迎讨论 |
| 返回顶楼 | |
|
发表时间：2011-12-07
superobin 写道 看了几遍，觉得都有道理，具体什么情况，咱们测一下
目前三种方法我都列出来，不知道我写的是不是和大家写的有出入，如果有请指正 public class CountBit {
public static void main(String[] args) {
CountBit cnt = new CountBit();
long start = System.currentTimeMillis();
int times = 100000000;
cnt.testAdvanceVersion(times);
long p0 = System.currentTimeMillis();
cnt.testLoopVersion(times);
long p1 = System.currentTimeMillis();
cnt.testJDKVersion(times);
long p2 = System.currentTimeMillis();
System.out.println(""+times+"次均匀分布");
System.out.println("使用编程之美算法,单位（毫秒）：");
System.out.println(p0-start);
System.out.println("使用循环移位算法,单位（毫秒）：");
System.out.println(p1-p0);
System.out.println("使用JDK改版算法,单位（毫秒）：");
System.out.println(p2-p1);
}
/**
* jdk的算法改byte版，纯粹使用位操作
* @param b byte value
* @return count of 1
*/
public int bitCountJDK(byte b) {
int i = (b>>>31<<7) + (b&0x7F);
i = (i&0x55)+(i>>>1&0x55);
i = (i&0x33)+(i>>>2&0x33);
return (i&0x0F)+(i>>>4);
}
/**
* 编程之美的算法
* @param b byte value
* @return count of 1
*/
public int bitCountAdvance(byte b) {
int i = (b>>>31<<7) + (b&0x7F);
int result = 0;
while(i!=0) {
result++;
i&=i-1;
}
return result;
}
/***
* 移位、循环的算法
* @param b byte value
* @return count of 1
*/
public int bitCountLoop(byte b) {
int i = (b>>>31<<7) + (b&0x7F);
int result = 0;
while(i!=0) {
result+= i&1;
i>>>=1;
}
return result;
}
private void testAdvanceVersion(int times) {
for(int i=0;i<times;i++) {
bitCountAdvance((byte)((i&255)-128));
}
}
private void testLoopVersion(int times) {
for(int i=0;i<times;i++) {
bitCountLoop((byte)((i&255)-128));
}
}
private void testJDKVersion(int times) {
for(int i=0;i<times;i++) {
bitCountJDK((byte)((i&255)-128));
}
}
}
得到结果 100000000次均匀分布 使用编程之美算法,单位（毫秒）： 1641 使用循环移位算法,单位（毫秒）： 1282 使用JDK改版算法,单位（毫秒）： 770 让我很吃惊的是 编程之美那个算法是最差的。 本以为在均匀的情况下jdk应该是最快的，编程之美第二、循环移位最慢。 欢迎讨论 你好，我运行了多次，最快的是jdk、其次是编程之美， 100000000次均匀分布 使用编程之美算法,单位（毫秒）： 645 使用循环移位算法,单位（毫秒）： 945 使用JDK改版算法,单位（毫秒）： 633 |
| 返回顶楼 | |
|
发表时间：2011-12-16
最后修改：2011-12-16
编程之美给了五种算法
数小的话 直接空间换时间 复杂度是o(1) 数大的话借助n&(n-1) 复杂度是o(M) M是1的个数 |
| 返回顶楼 | |
