How to count the number of set bits in ASCII string

这是最近看到的一个算法题,第一眼看过去连题目都看不懂啊囧。非计算机本科生表示对算法十分无力。第一直觉肯定是把ASCII的字符都换成int,然后题目就可以变成How to count the number of set bits in integer. google一下还真有答案.第一个高分回答表示各种位操作都看不懂。传说中的Hamming_weight算法。真是给跪了。

突然想到Java的Integer类本来就有个toBinaryString方法,再加上最近正好研究UUID生成,觉得用现成的方法实现一下。

直接贴源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class ASC2Bin {

private static int DEFAULT_LENGTH = 8;

public static String asc2bin(String str) {
StringBuilder binaryString = new StringBuilder(8 * str.length());
for (int i = 0; i < str.length(); i++) {
try {
int ascInt = (int) str.charAt(i);
StringBuilder temp = new StringBuilder(Integer.toBinaryString(ascInt));
String bin = null;
if (temp.length() <= DEFAULT_LENGTH) {
while (temp.length() < DEFAULT_LENGTH) {
temp.insert(0, "0");
}
bin = temp.toString();
} else if (temp.length() > DEFAULT_LENGTH) {
continue;
}
binaryString.append(bin);
} catch (NumberFormatException nfe) {
continue;
}
}
return binaryString.toString();
}

public static String bin2asc(String str) {
StringBuilder sb = new StringBuilder();

//10010001100101 split into 8 characters
for (int i = 0; i < str.length() - 1; i += DEFAULT_LENGTH) {

//grab the hex in pairs
String output = str.substring(i, (i + DEFAULT_LENGTH));
//convert hex to decimal
int decimal = Integer.parseInt(output, 2);
//convert the decimal to character
sb.append((char) decimal);
}

return sb.toString();
}

public static void main(String[] args) {
String binary = asc2bin("Hello world!");
System.out.println("binary : " + binary);
String asc = bin2asc(binary);
System.out.println("ASC : " + asc);
}

}

其实一开始的时候我并没有强制限定每一个ASCII字符都是8位bits,但是逆操作的时候遇到问题了。一般的ASCII字符在我本机CPU下的是7个bit,但是空格和其他符号都是6个bit。这个就比较麻烦了,不好直接按位数切分做逆操作。索性定死8位前面补0,方法比较土鳖,也没考虑性能(说实话我还真没那个本事),各位随便看看吧。