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
|
#!/bin/bash
# Count bits pop(x) algorithm, rotate and sum method,
# hacker's delight, page 70
# we verify it by cross-checking with the obvious method of counting bits
# for (s = i = 0; i < n; i++)
# if (x & (1 << i))
# s++;
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 ./countbitsrotate <num-bits>"
exit 1
fi
numbits=$1
if [[ "$numbits" -le 1 ]] || [[ ! `is_power_of_2 $numbits` -eq 1 ]]; then
echo "Number of bits must be a power of 2 > 1"
exit 1
fi
numbitslog=`log_2 $numbits`
id=1
echo "$((id++)) var $numbits x"
((idx = id - 1))
((idsum = idx))
((idxorig = idx))
for ((i = 1; i < $numbits; i++))
do
echo "$((id++)) constd $numbitslog $i"
((lastid = id - 1))
echo "$((id++)) rol $numbits $idx $lastid"
((idx = id - 1))
echo "$((id++)) add $numbits $idsum $idx"
((idsum = id - 1))
done
echo "$((id++)) neg $numbits $idsum"
((idresult1 = id - 1))
echo "$((id++)) zero $numbits"
((idsum = id - 1))
((idzero = idsum))
echo "$((id++)) one $numbits"
((idone = id - 1))
for ((i = 0; i < $numbits; i++))
do
echo "$((id++)) constd $numbitslog $i"
((lastid = id - 1))
echo "$((id++)) sll $numbits $idone $lastid"
((lastid = id - 1))
echo "$((id++)) and $numbits $idxorig $lastid"
((lastid = id - 1))
echo "$((id++)) ne 1 $lastid $idzero"
((idcond = id - 1))
echo "$((id++)) inc $numbits $idsum"
((lastid = id - 1))
echo "$((id++)) cond $numbits $idcond $lastid $idsum"
((idsum = id - 1))
done
((idresult2 = idsum))
echo "$((id++)) eq 1 $idresult1 $idresult2"
((lastid = id - 1))
echo "$((id++)) root 1 -$lastid"
|
