|
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-11-29
无意中看到这个题目，开始想到的是把byte的二进制数据转为一个数组，然后再遍历数组，计算数组中1出现的次数。
感觉这应该是这简单，效率也比较低的做法。 在编程之美上看到如下做法： 把byte数据取2的模，如果余数为1则说明当前位置出现的是1，否则是0，然后不断把byte往右边移位，也就是除以2， 代码如下：
public static int countByte(byte b)
{
int count = 0;
while (b > 0)
{
if (b % 2 == 1)
{
++count;
}
b = (byte)(b / 2);
}
return count;
}
感觉这是一个很不错的思路，记录下。 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2011-11-29
不错。 这个算法可以通用化。 问题通用描述，一个byte数据，用N进制表达，请统计数字Digit出现的次数。 public static int countByte(byte b, int N, int Digit) { int count = 0; while (b > 0) { if (b % N == Digit) { ++count; } b = (byte)(b / N); } return count; } |
| 返回顶楼 | |
|
发表时间：2011-11-29
楼上的分好多啊，羡慕。
|
| 返回顶楼 | |
|
发表时间：2011-12-01
最后修改：2011-12-01
楼主，如果byte小于0咋办？
看看jdk的源码 public static int bitCount(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
|
| 返回顶楼 | |
|
发表时间：2011-12-01
superobin 写道 楼主，如果byte小于0咋办？
看看jdk的源码 public static int bitCount(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}貌似我那方法，只适合于无符号整数。 |
| 返回顶楼 | |
|
发表时间：2011-12-01
kidneyball 写道 zhangyou1010 写道 superobin 写道 楼主，如果byte小于0咋办？
看看jdk的源码 public static int bitCount(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}貌似我那方法，只适合于无符号整数。 问题是题目要求是byte呀,把0xFF传进去直接就变成-1了 需要先把负数转回来，这是一种方案：
public class BitCount {
private static int bitCount(byte i) {
int a = i & 0xFF;
int count = 0;
while (a > 0) {
count += a & 1;
a >>>= 1;
}
return count;
}
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(bitCount((byte) 0xFF));
}
}
|
| 返回顶楼 | |
|
发表时间：2011-12-02
嘎嘎，本人最近刚好用了一下byte，像你这种情况只需不断右移然后和1取与运算就行了。
byte b = ...;
int count = 0;
for (i=0; i<4; i++) {
if ((b >> i) & 1) == 1) count ++;
}
|
| 返回顶楼 | |
|
发表时间：2011-12-02
最后修改：2011-12-02
|
| 返回顶楼 | |
|
发表时间：2011-12-02
#include <stdio.h>
static int bits(unsigned int n){ int c = 0; for(; n != 0; n >>= 1){ c += n & 1; } return c; } int main(){ int n = -231232; printf("count:%d",bits(n)); } PS.不知道有没有记错，CRC的算法好像有更快的 |
| 返回顶楼 | |
|
发表时间：2011-12-02
最后修改：2011-12-02
kidneyball 写道 kidneyball 写道 zhangyou1010 写道 superobin 写道 楼主，如果byte小于0咋办？
看看jdk的源码 public static int bitCount(int i) {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}貌似我那方法，只适合于无符号整数。 问题是题目要求是byte呀,把0xFF传进去直接就变成-1了 需要先把负数转回来，这是一种方案：
public class BitCount {
private static int bitCount(byte i) {
int a = i & 0xFF;
int count = 0;
while (a > 0) {
count += a & 1;
a >>>= 1;
}
return count;
}
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(bitCount((byte) 0xFF));
}
}
实际上就是做一个简单的byte换成unsigned int 只要判断byte<0就+256就行了 jdk的源码还可以在简化，因为只要处理8位 public static int bitCount(byte b) {
int i = b;
if (b < 0)
i = b + 256;
i -= i >>> 1 & 0x55;
i = (i & 0x33) + (i >>> 2 & 0x33);
i = i + (i >>> 4) & 0x0f;
return i & 15;
}
|
| 返回顶楼 | |
