/docs/MyDocs

To get this branch, use:
bzr branch http://darksoft.org/webbzr/docs/MyDocs

« back to all changes in this revision

Viewing changes to Development/algoritms/BitCount.java

  • Committer: Suren A. Chilingaryan
  • Date: 2009-04-09 03:21:08 UTC
  • Revision ID: csa@dside.dyndns.org-20090409032108-w4edamdh4adrgdu3
import

Show diffs side-by-side

added added

removed removed

Lines of Context:
Development/algoritms/BitCount.java
 
1
 
 
2
/* BitUtils - Tim Tyler 2000.
 
3
 * 
 
4
 */
 
5
 
 
6
/*
 
7
 * ToDo:
 
8
 *
 
9
 * Add more utilities...
 
10
 *
 
11
 */
 
12
 
 
13
   public class BitUtils {
 
14
   /** Count the number of set bits in a byte;
 
15
    *  @param x the byte to have its bits counted
 
16
    *  @returns the number of bits set in x
 
17
    *  @author Tim Tyler tt@iname.com
 
18
    */
 
19
      static int bitCount(byte x) {
 
20
         int temp;
 
21
         int y = (int)x;
 
22
      
 
23
         temp = 0x55;
 
24
         y = (y & temp) + (y >>> 1 & temp);
 
25
         temp = 0x33;
 
26
         y = (y & temp) + (y >>> 2 & temp);
 
27
      
 
28
         return (y & 0x07) + (y >>> 4);
 
29
      }
 
30
   
 
31
   
 
32
   /** Count the number of set bits in a short;
 
33
    *  @param x the short to have its bits counted
 
34
    *  @returns the number of bits set in x
 
35
    *  @author Tim Tyler tt@iname.com
 
36
    */
 
37
      static int bitCount(short x) {
 
38
         int temp;
 
39
         int y = (int)x;
 
40
      
 
41
         temp = 0x5555;
 
42
         y = (y & temp) + (y >>> 1 & temp);
 
43
         temp = 0x3333;
 
44
         y = (y & temp) + (y >>> 2 & temp);
 
45
         temp = 0x0707;
 
46
         y = (y & temp) + (y >>> 4 & temp);
 
47
      
 
48
         return (y & 0x000f) + (y >>> 8);
 
49
      }
 
50
   
 
51
   
 
52
   /** Count the number of set bits in an int;
 
53
    *  @param x the int to have its bits counted
 
54
    *  @author Tim Tyler tt@iname.com
 
55
    *  @returns the number of bits set in x
 
56
    */
 
57
      static int bitCount(int x) {
 
58
         int temp;
 
59
      
 
60
         temp = 0x55555555;
 
61
         x = (x & temp) + (x >>> 1 & temp); 
 
62
         temp = 0x33333333;
 
63
         x = (x & temp) + (x >>> 2 & temp); 
 
64
         temp = 0x07070707;
 
65
         x = (x & temp) + (x >>> 4 & temp); 
 
66
         temp = 0x000F000F;
 
67
         x = (x & temp) + (x >>> 8 & temp); 
 
68
      
 
69
         return (x & 0x1F) + (x >>> 16);
 
70
      }
 
71
   
 
72
   
 
73
   /** Count the number of set bits in an long;
 
74
    *  @param x the long to have its bits counted
 
75
    *  @author Tim Tyler tt@iname.com
 
76
    *  @returns the number of bits set in x
 
77
    */
 
78
      static int bitCount(long x) {
 
79
         long temp;
 
80
      
 
81
         temp = 0x5555555555555555L;
 
82
         x = (x & temp) + (x >>> 1 & temp);
 
83
         temp = 0x3333333333333333L;
 
84
         x = (x & temp) + (x >>> 2 & temp);
 
85
         temp = 0x0707070707070707L;
 
86
         x = (x & temp) + (x >>> 4 & temp);
 
87
         temp = 0x000F000F000F000FL;
 
88
         x = (x & temp) + (x >>> 8 & temp);
 
89
         temp = 0x0000001F0000001FL;
 
90
         x = (x & temp) + (x >>> 16 & temp);
 
91
      
 
92
         return (int)((x & 0x3f) + (x >>> 32));
 
93
      }
 
94
   
 
95
   
 
96
   /** Count the number of set bits in an int;
 
97
    *  @param x the int to have its bits counted
 
98
    *  @author Tim Tyler tt@iname.com
 
99
    *  @returns the number of bits set in x
 
100
    */
 
101
   
 
102
      static int slowBitCount(int x) {
 
103
      
 
104
         int temp1 = 0x77777777;
 
105
         int temp2 = 0x33333333;
 
106
         int temp3 = 0x11111111;
 
107
      
 
108
         return (((x - ((x >>> 1) & temp1) - ((x >>> 2) & temp2) - ((x >>> 3) & temp3)) +
 
109
                      ((x - ((x >>> 1) & temp1) - ((x >>> 2) & temp2) - ((x >>> 3) & temp3)) >>> 4)) & 0x0F0F0F0F) % 255;
 
110
      
 
111
      }
 
112
   
 
113
   
 
114
   /** 
 
115
    * Counts number of 1 bits in a 32 bit unsigned number. 
 
116
    * 
 
117
    * @param x unsigned 32 bit number whose bits you wish to count. 
 
118
    * 
 
119
    * @return number of 1 bits in x. 
 
120
    * @author Roedy Green roedy@mindprod.com 
 
121
    */ 
 
122
      public static int countBits(int x ) { 
 
123
      // collapsing partial parallel sums method 
 
124
      // collapse 32x1 bit counts to 16x2 bit counts, mask 01010101 
 
125
         x = (x >>> 1 & 0x55555555) + (x & 0x55555555); 
 
126
      // collapse 16x2 bit counts to 8x4 bit counts, mask 00110011 
 
127
         x = (x >>> 2 & 0x33333333) + (x & 0x33333333); 
 
128
      // collapse 8x4 bit counts to 4x8 bit counts, mask 00001111 
 
129
         x = (x >>> 4 & 0x0f0f0f0f) + (x & 0x0f0f0f0f); 
 
130
      // collapse 4x8 bit counts to 2x16 bit counts 
 
131
         x = (x >>> 8 & 0x00ff00ff) + (x & 0x00ff00ff); 
 
132
      // collapse 2x16 bit counts to 1x32 bit count 
 
133
         return(x >>> 16) + (x & 0x0000ffff); 
 
134
      } 
 
135
   
 
136
   /** 
 
137
    * Counts number of 1 bits in a 32 bit unsigned number. 
 
138
    * This method counts the number of bits set within the given 
 
139
    * integer. Given an n-bit value with k of those bits set, the 
 
140
    * efficiency of this algorithm is O(k) rather than the O(n) of 
 
141
    * an algorithm that simply looped through all bits counting non 
 
142
    * zero ones. 
 
143
    * 
 
144
    * @param x unsigned 32 bit number whose bits you wish to count. 
 
145
    * 
 
146
    * @return number of 1 bits in x. 
 
147
    * @author Dale King KingD@TCE.com KingD@TCE.com 
 
148
    */ 
 
149
      public static int countBits3( int x ) { 
 
150
         int count = 0; 
 
151
         while ( x != 0 ) 
 
152
         { 
 
153
         // The result of this operation is to subtract off 
 
154
         // the least significant non-zero bit. This can be seen 
 
155
         // from noting that subtracting 1 from any number causes 
 
156
         // all bits up to and including the least significant 
 
157
         // non-zero bit to be complemented. 
 
158
         // 
 
159
         // For example: 
 
160
         // 10101100 x 
 
161
         // 10101011 x-1 
 
162
         // 10101000 (x - 1) & x 
 
163
            x &= x - 1; 
 
164
            count++; 
 
165
         } 
 
166
         return count; 
 
167
      } 
 
168
   
 
169
   
 
170
      // main method (timings)
 
171
      public static void main(String args[]) {
 
172
         int temp;
 
173
         long start_time;
 
174
         int N = 50000000;
 
175
      
 
176
         Log.log("START...");
 
177
      
 
178
         do {
 
179
            start_time = System.currentTimeMillis();
 
180
            for (int x = 0; x < N; x++) {
 
181
               temp = countBits(x);
 
182
            }
 
183
         
 
184
            Log.log("countBits:" + (System.currentTimeMillis() - start_time));
 
185
         
 
186
            start_time = System.currentTimeMillis();
 
187
            for (int x = 0; x < N; x++) {
 
188
               temp = bitCount(x);
 
189
            }
 
190
         
 
191
            Log.log("bitCount:" + (System.currentTimeMillis() - start_time));
 
192
         
 
193
         
 
194
         } while (1==1);
 
195
      }
 
196
   }