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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
#!/bin/bash
# Count bits pop_array(A, n) algorithm
# hacker's delight, page 71
# we verifiy it by cross-checking with the obvios method of counting bits
# for (s = i = 0; i < n; i++)
# if (x & (1 << i))
# s++;
# for each element of A. The result is summed up.
function dec2bin
{
local x=$1
local len=$2
local ret="`echo "ibase=10; obase=2; $x" | bc`"
local result=`printf "%0${len}d" $ret`
echo $result
}
function log_2
{
local result=0
local x=$1
while [[ "$x" -gt 1 ]]
do
((x >>= 1))
((result++))
done
echo $result
}
function is_power_of_2
{
local x=$1
((x = x & (x - 1)))
if [[ x -eq 0 ]]; then
echo 1
else
echo 0
fi
}
if [[ $# -ne 1 ]]; then
echo "Usage ./countbitsarray <size>"
exit 1
fi
size=$1
if [[ "$size" -lt 2 ]] || [[ ! `is_power_of_2 $size` -eq 1 ]]; then
echo "Size must be a power of 2 >= 2"
exit 1
fi
sizelog=`log_2 $size`
id=1
echo "$((id++)) zero 32"
((idzero = id - 1))
((idsum = idzero))
echo "$((id++)) one 32"
((idone = id - 1))
echo "$((id++)) one 5"
((idone5 = id - 1))
echo "$((id++)) constd 5 2"
((idtwo5 = id - 1))
echo "$((id++)) constd 5 4"
((idfour5 = id - 1))
echo "$((id++)) constd 5 8"
((ideight5 = id - 1))
echo "$((id++)) constd 5 16"
((idsixteen5 = id - 1))
echo "$((id++)) consth 32 55555555"
((idhex55555555 = id - 1))
echo "$((id++)) consth 32 33333333"
((idhex33333333 = id - 1))
echo "$((id++)) consth 32 0f0f0f0f"
((idhex0f0f0f0f = id - 1))
echo "$((id++)) consth 32 00ff00ff"
((idhex00ff00ff = id - 1))
echo "$((id++)) consth 32 0000ffff"
((idhex0000ffff = id - 1))
echo "$((id++)) array 32 $sizelog"
((idarray = id - 1))
for ((i = 0; i < $size; i += 31))
do
((ip31 = i + 31))
if [[ $size -lt ip31 ]]; then
lim=$size
else
lim=$ip31;
fi
((ids8 = idzero))
for ((j = i; j < $lim; j++))
do
binj="`dec2bin $j $sizelog`"
echo "$((id++)) const $sizelog $binj"
((lastid = id - 1))
echo "$((id++)) read 32 $idarray $lastid"
((idx = id - 1))
echo "$((id++)) srl 32 $idx $idone5"
((lastid = id - 1))
echo "$((id++)) and 32 $lastid $idhex55555555"
((lastid = id - 1))
echo "$((id++)) sub 32 $idx $lastid"
((idx = id - 1))
echo "$((id++)) srl 32 $idx $idtwo5"
((lastid = id - 1))
echo "$((id++)) and 32 $lastid $idhex33333333"
((idtemp = id - 1))
echo "$((id++)) and 32 $idx $idhex33333333"
((lastid = id - 1))
echo "$((id++)) add 32 $idtemp $lastid"
((idx = id - 1))
echo "$((id++)) srl 32 $idx $idfour5"
((lastid = id - 1))
echo "$((id++)) add 32 $idx $lastid"
((lastid = id - 1))
echo "$((id++)) and 32 $lastid $idhex0f0f0f0f"
((idx = id - 1))
echo "$((id++)) add 32 $ids8 $idx"
((ids8 = id - 1))
done
echo "$((id++)) srl 32 $ids8 $ideight5"
((lastid = id - 1))
echo "$((id++)) and 32 $lastid $idhex00ff00ff"
((idtemp = id - 1))
echo "$((id++)) and 32 $ids8 $idhex00ff00ff"
((lastid = id - 1))
echo "$((id++)) add 32 $idtemp $lastid"
((idx = id - 1))
echo "$((id++)) srl 32 $idx $idsixteen5"
((idtemp = id - 1))
echo "$((id++)) and 32 $idx $idhex0000ffff"
((lastid = id - 1))
echo "$((id++)) add 32 $idtemp $lastid"
((idx = id - 1))
echo "$((id++)) add 32 $idsum $idx"
((idsum = id - 1))
done
((idresult1 = idsum))
((idresult2 = idzero))
for ((i = 0; i < $size; i++))
do
binrep="`dec2bin $i $sizelog`"
echo "$((id++)) const $sizelog $binrep"
((idindex = id - 1))
echo "$((id++)) read 32 $idarray $idindex"
((idx = id - 1))
((idsum = idzero))
for ((j = 0; j < 32; j++))
do
echo "$((id++)) constd 5 $j"
((lastid = id - 1))
echo "$((id++)) sll 32 $idone $lastid"
((lastid = id - 1))
echo "$((id++)) and 32 $idx $lastid"
((lastid = id - 1))
echo "$((id++)) ne 1 $lastid $idzero"
((idcond = id - 1))
echo "$((id++)) inc 32 $idsum"
((lastid = id - 1))
echo "$((id++)) cond 32 $idcond $lastid $idsum"
((idsum = id - 1))
done
echo "$((id++)) add 32 $idresult2 $idsum"
((idresult2 = id - 1))
done
echo "$((id++)) eq 1 $idresult1 $idresult2"
((lastid = id - 1))
echo "$((id++)) root 1 -$lastid"
|
