Lucene.Net  3.0.3
Lucene.Net is a port of the Lucene search engine library, written in C# and targeted at .NET runtime users.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Pages
BitUtil.cs
Go to the documentation of this file.
1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 using System;
19 using Lucene.Net.Support;
20 
21 namespace Lucene.Net.Util
22 {
23  // from org.apache.solr.util rev 555343
24 
25  /// <summary>A variety of high efficiencly bit twiddling routines.
26  ///
27  /// </summary>
28  /// <version> $Id$
29  /// </version>
30  public class BitUtil
31  {
32 
33  /// <summary>Returns the number of bits set in the long </summary>
34  public static int Pop(long x)
35  {
36  /* Hacker's Delight 32 bit pop function:
37  * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
38  *
39  int pop(unsigned x) {
40  x = x - ((x >> 1) & 0x55555555);
41  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
42  x = (x + (x >> 4)) & 0x0F0F0F0F;
43  x = x + (x >> 8);
44  x = x + (x >> 16);
45  return x & 0x0000003F;
46  }
47  ***/
48 
49  // 64 bit java version of the C function from above
50  x = x - ((Number.URShift(x, 1)) & 0x5555555555555555L);
51  x = (x & 0x3333333333333333L) + ((Number.URShift(x, 2)) & 0x3333333333333333L);
52  x = (x + (Number.URShift(x, 4))) & 0x0F0F0F0F0F0F0F0FL;
53  x = x + (Number.URShift(x, 8));
54  x = x + (Number.URShift(x, 16));
55  x = x + (Number.URShift(x, 32));
56  return ((int) x) & 0x7F;
57  }
58 
59  /// <summary> Returns the number of set bits in an array of longs. </summary>
60  public static long Pop_array(long[] A, int wordOffset, int numWords)
61  {
62  /*
63  * Robert Harley and David Seal's bit counting algorithm, as documented
64  * in the revisions of Hacker's Delight
65  * http://www.hackersdelight.org/revisions.pdf
66  * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
67  *
68  * This function was adapted to Java, and extended to use 64 bit words.
69  * if only we had access to wider registers like SSE from java...
70  *
71  * This function can be transformed to compute the popcount of other functions
72  * on bitsets via something like this:
73  * sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
74  *
75  */
76  int n = wordOffset + numWords;
77  long tot = 0, tot8 = 0;
78  long ones = 0, twos = 0, fours = 0;
79 
80  int i;
81  for (i = wordOffset; i <= n - 8; i += 8)
82  {
83  /* C macro from Hacker's Delight
84  #define CSA(h,l, a,b,c) \
85  {unsigned u = a ^ b; unsigned v = c; \
86  h = (a & b) | (u & v); l = u ^ v;}
87  ***/
88 
89  long twosA, twosB, foursA, foursB, eights;
90 
91  // CSA(twosA, ones, ones, A[i], A[i+1])
92  {
93  long b = A[i], c = A[i + 1];
94  long u = ones ^ b;
95  twosA = (ones & b) | (u & c);
96  ones = u ^ c;
97  }
98  // CSA(twosB, ones, ones, A[i+2], A[i+3])
99  {
100  long b = A[i + 2], c = A[i + 3];
101  long u = ones ^ b;
102  twosB = (ones & b) | (u & c);
103  ones = u ^ c;
104  }
105  //CSA(foursA, twos, twos, twosA, twosB)
106  {
107  long u = twos ^ twosA;
108  foursA = (twos & twosA) | (u & twosB);
109  twos = u ^ twosB;
110  }
111  //CSA(twosA, ones, ones, A[i+4], A[i+5])
112  {
113  long b = A[i + 4], c = A[i + 5];
114  long u = ones ^ b;
115  twosA = (ones & b) | (u & c);
116  ones = u ^ c;
117  }
118  // CSA(twosB, ones, ones, A[i+6], A[i+7])
119  {
120  long b = A[i + 6], c = A[i + 7];
121  long u = ones ^ b;
122  twosB = (ones & b) | (u & c);
123  ones = u ^ c;
124  }
125  //CSA(foursB, twos, twos, twosA, twosB)
126  {
127  long u = twos ^ twosA;
128  foursB = (twos & twosA) | (u & twosB);
129  twos = u ^ twosB;
130  }
131 
132  //CSA(eights, fours, fours, foursA, foursB)
133  {
134  long u = fours ^ foursA;
135  eights = (fours & foursA) | (u & foursB);
136  fours = u ^ foursB;
137  }
138  tot8 += Pop(eights);
139  }
140 
141  // handle trailing words in a binary-search manner...
142  // derived from the loop above by setting specific elements to 0.
143  // the original method in Hackers Delight used a simple for loop:
144  // for (i = i; i < n; i++) // Add in the last elements
145  // tot = tot + pop(A[i]);
146 
147  if (i <= n - 4)
148  {
149  long twosA, twosB, foursA, eights;
150  {
151  long b = A[i], c = A[i + 1];
152  long u = ones ^ b;
153  twosA = (ones & b) | (u & c);
154  ones = u ^ c;
155  }
156  {
157  long b = A[i + 2], c = A[i + 3];
158  long u = ones ^ b;
159  twosB = (ones & b) | (u & c);
160  ones = u ^ c;
161  }
162  {
163  long u = twos ^ twosA;
164  foursA = (twos & twosA) | (u & twosB);
165  twos = u ^ twosB;
166  }
167  eights = fours & foursA;
168  fours = fours ^ foursA;
169 
170  tot8 += Pop(eights);
171  i += 4;
172  }
173 
174  if (i <= n - 2)
175  {
176  long b = A[i], c = A[i + 1];
177  long u = ones ^ b;
178  long twosA = (ones & b) | (u & c);
179  ones = u ^ c;
180 
181  long foursA = twos & twosA;
182  twos = twos ^ twosA;
183 
184  long eights = fours & foursA;
185  fours = fours ^ foursA;
186 
187  tot8 += Pop(eights);
188  i += 2;
189  }
190 
191  if (i < n)
192  {
193  tot += Pop(A[i]);
194  }
195 
196  tot += (Pop(fours) << 2) + (Pop(twos) << 1) + Pop(ones) + (tot8 << 3);
197 
198  return tot;
199  }
200 
201  /// <summary>Returns the popcount or cardinality of the two sets after an intersection.
202  /// Neither array is modified.
203  /// </summary>
204  public static long Pop_intersect(long[] A, long[] B, int wordOffset, int numWords)
205  {
206  // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
207  int n = wordOffset + numWords;
208  long tot = 0, tot8 = 0;
209  long ones = 0, twos = 0, fours = 0;
210 
211  int i;
212  for (i = wordOffset; i <= n - 8; i += 8)
213  {
214  long twosA, twosB, foursA, foursB, eights;
215 
216  // CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
217  {
218  long b = (A[i] & B[i]), c = (A[i + 1] & B[i + 1]);
219  long u = ones ^ b;
220  twosA = (ones & b) | (u & c);
221  ones = u ^ c;
222  }
223  // CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
224  {
225  long b = (A[i + 2] & B[i + 2]), c = (A[i + 3] & B[i + 3]);
226  long u = ones ^ b;
227  twosB = (ones & b) | (u & c);
228  ones = u ^ c;
229  }
230  //CSA(foursA, twos, twos, twosA, twosB)
231  {
232  long u = twos ^ twosA;
233  foursA = (twos & twosA) | (u & twosB);
234  twos = u ^ twosB;
235  }
236  //CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
237  {
238  long b = (A[i + 4] & B[i + 4]), c = (A[i + 5] & B[i + 5]);
239  long u = ones ^ b;
240  twosA = (ones & b) | (u & c);
241  ones = u ^ c;
242  }
243  // CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
244  {
245  long b = (A[i + 6] & B[i + 6]), c = (A[i + 7] & B[i + 7]);
246  long u = ones ^ b;
247  twosB = (ones & b) | (u & c);
248  ones = u ^ c;
249  }
250  //CSA(foursB, twos, twos, twosA, twosB)
251  {
252  long u = twos ^ twosA;
253  foursB = (twos & twosA) | (u & twosB);
254  twos = u ^ twosB;
255  }
256 
257  //CSA(eights, fours, fours, foursA, foursB)
258  {
259  long u = fours ^ foursA;
260  eights = (fours & foursA) | (u & foursB);
261  fours = u ^ foursB;
262  }
263  tot8 += Pop(eights);
264  }
265 
266 
267  if (i <= n - 4)
268  {
269  long twosA, twosB, foursA, eights;
270  {
271  long b = (A[i] & B[i]), c = (A[i + 1] & B[i + 1]);
272  long u = ones ^ b;
273  twosA = (ones & b) | (u & c);
274  ones = u ^ c;
275  }
276  {
277  long b = (A[i + 2] & B[i + 2]), c = (A[i + 3] & B[i + 3]);
278  long u = ones ^ b;
279  twosB = (ones & b) | (u & c);
280  ones = u ^ c;
281  }
282  {
283  long u = twos ^ twosA;
284  foursA = (twos & twosA) | (u & twosB);
285  twos = u ^ twosB;
286  }
287  eights = fours & foursA;
288  fours = fours ^ foursA;
289 
290  tot8 += Pop(eights);
291  i += 4;
292  }
293 
294  if (i <= n - 2)
295  {
296  long b = (A[i] & B[i]), c = (A[i + 1] & B[i + 1]);
297  long u = ones ^ b;
298  long twosA = (ones & b) | (u & c);
299  ones = u ^ c;
300 
301  long foursA = twos & twosA;
302  twos = twos ^ twosA;
303 
304  long eights = fours & foursA;
305  fours = fours ^ foursA;
306 
307  tot8 += Pop(eights);
308  i += 2;
309  }
310 
311  if (i < n)
312  {
313  tot += Pop((A[i] & B[i]));
314  }
315 
316  tot += (Pop(fours) << 2) + (Pop(twos) << 1) + Pop(ones) + (tot8 << 3);
317 
318  return tot;
319  }
320 
321  /// <summary>Returns the popcount or cardinality of the union of two sets.
322  /// Neither array is modified.
323  /// </summary>
324  public static long Pop_union(long[] A, long[] B, int wordOffset, int numWords)
325  {
326  // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \| B[\1]\)/g'
327  int n = wordOffset + numWords;
328  long tot = 0, tot8 = 0;
329  long ones = 0, twos = 0, fours = 0;
330 
331  int i;
332  for (i = wordOffset; i <= n - 8; i += 8)
333  {
334  /* C macro from Hacker's Delight
335  #define CSA(h,l, a,b,c) \
336  {unsigned u = a ^ b; unsigned v = c; \
337  h = (a & b) | (u & v); l = u ^ v;}
338  ***/
339 
340  long twosA, twosB, foursA, foursB, eights;
341 
342  // CSA(twosA, ones, ones, (A[i] | B[i]), (A[i+1] | B[i+1]))
343  {
344  long b = (A[i] | B[i]), c = (A[i + 1] | B[i + 1]);
345  long u = ones ^ b;
346  twosA = (ones & b) | (u & c);
347  ones = u ^ c;
348  }
349  // CSA(twosB, ones, ones, (A[i+2] | B[i+2]), (A[i+3] | B[i+3]))
350  {
351  long b = (A[i + 2] | B[i + 2]), c = (A[i + 3] | B[i + 3]);
352  long u = ones ^ b;
353  twosB = (ones & b) | (u & c);
354  ones = u ^ c;
355  }
356  //CSA(foursA, twos, twos, twosA, twosB)
357  {
358  long u = twos ^ twosA;
359  foursA = (twos & twosA) | (u & twosB);
360  twos = u ^ twosB;
361  }
362  //CSA(twosA, ones, ones, (A[i+4] | B[i+4]), (A[i+5] | B[i+5]))
363  {
364  long b = (A[i + 4] | B[i + 4]), c = (A[i + 5] | B[i + 5]);
365  long u = ones ^ b;
366  twosA = (ones & b) | (u & c);
367  ones = u ^ c;
368  }
369  // CSA(twosB, ones, ones, (A[i+6] | B[i+6]), (A[i+7] | B[i+7]))
370  {
371  long b = (A[i + 6] | B[i + 6]), c = (A[i + 7] | B[i + 7]);
372  long u = ones ^ b;
373  twosB = (ones & b) | (u & c);
374  ones = u ^ c;
375  }
376  //CSA(foursB, twos, twos, twosA, twosB)
377  {
378  long u = twos ^ twosA;
379  foursB = (twos & twosA) | (u & twosB);
380  twos = u ^ twosB;
381  }
382 
383  //CSA(eights, fours, fours, foursA, foursB)
384  {
385  long u = fours ^ foursA;
386  eights = (fours & foursA) | (u & foursB);
387  fours = u ^ foursB;
388  }
389  tot8 += Pop(eights);
390  }
391 
392 
393  if (i <= n - 4)
394  {
395  long twosA, twosB, foursA, eights;
396  {
397  long b = (A[i] | B[i]), c = (A[i + 1] | B[i + 1]);
398  long u = ones ^ b;
399  twosA = (ones & b) | (u & c);
400  ones = u ^ c;
401  }
402  {
403  long b = (A[i + 2] | B[i + 2]), c = (A[i + 3] | B[i + 3]);
404  long u = ones ^ b;
405  twosB = (ones & b) | (u & c);
406  ones = u ^ c;
407  }
408  {
409  long u = twos ^ twosA;
410  foursA = (twos & twosA) | (u & twosB);
411  twos = u ^ twosB;
412  }
413  eights = fours & foursA;
414  fours = fours ^ foursA;
415 
416  tot8 += Pop(eights);
417  i += 4;
418  }
419 
420  if (i <= n - 2)
421  {
422  long b = (A[i] | B[i]), c = (A[i + 1] | B[i + 1]);
423  long u = ones ^ b;
424  long twosA = (ones & b) | (u & c);
425  ones = u ^ c;
426 
427  long foursA = twos & twosA;
428  twos = twos ^ twosA;
429 
430  long eights = fours & foursA;
431  fours = fours ^ foursA;
432 
433  tot8 += Pop(eights);
434  i += 2;
435  }
436 
437  if (i < n)
438  {
439  tot += Pop((A[i] | B[i]));
440  }
441 
442  tot += (Pop(fours) << 2) + (Pop(twos) << 1) + Pop(ones) + (tot8 << 3);
443 
444  return tot;
445  }
446 
447  /// <summary>Returns the popcount or cardinality of A &amp; ~B
448  /// Neither array is modified.
449  /// </summary>
450  public static long Pop_andnot(long[] A, long[] B, int wordOffset, int numWords)
451  {
452  // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& ~B[\1]\)/g'
453  int n = wordOffset + numWords;
454  long tot = 0, tot8 = 0;
455  long ones = 0, twos = 0, fours = 0;
456 
457  int i;
458  for (i = wordOffset; i <= n - 8; i += 8)
459  {
460  /* C macro from Hacker's Delight
461  #define CSA(h,l, a,b,c) \
462  {unsigned u = a ^ b; unsigned v = c; \
463  h = (a & b) | (u & v); l = u ^ v;}
464  ***/
465 
466  long twosA, twosB, foursA, foursB, eights;
467 
468  // CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
469  {
470  long b = (A[i] & ~ B[i]), c = (A[i + 1] & ~ B[i + 1]);
471  long u = ones ^ b;
472  twosA = (ones & b) | (u & c);
473  ones = u ^ c;
474  }
475  // CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
476  {
477  long b = (A[i + 2] & ~ B[i + 2]), c = (A[i + 3] & ~ B[i + 3]);
478  long u = ones ^ b;
479  twosB = (ones & b) | (u & c);
480  ones = u ^ c;
481  }
482  //CSA(foursA, twos, twos, twosA, twosB)
483  {
484  long u = twos ^ twosA;
485  foursA = (twos & twosA) | (u & twosB);
486  twos = u ^ twosB;
487  }
488  //CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
489  {
490  long b = (A[i + 4] & ~ B[i + 4]), c = (A[i + 5] & ~ B[i + 5]);
491  long u = ones ^ b;
492  twosA = (ones & b) | (u & c);
493  ones = u ^ c;
494  }
495  // CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
496  {
497  long b = (A[i + 6] & ~ B[i + 6]), c = (A[i + 7] & ~ B[i + 7]);
498  long u = ones ^ b;
499  twosB = (ones & b) | (u & c);
500  ones = u ^ c;
501  }
502  //CSA(foursB, twos, twos, twosA, twosB)
503  {
504  long u = twos ^ twosA;
505  foursB = (twos & twosA) | (u & twosB);
506  twos = u ^ twosB;
507  }
508 
509  //CSA(eights, fours, fours, foursA, foursB)
510  {
511  long u = fours ^ foursA;
512  eights = (fours & foursA) | (u & foursB);
513  fours = u ^ foursB;
514  }
515  tot8 += Pop(eights);
516  }
517 
518 
519  if (i <= n - 4)
520  {
521  long twosA, twosB, foursA, eights;
522  {
523  long b = (A[i] & ~ B[i]), c = (A[i + 1] & ~ B[i + 1]);
524  long u = ones ^ b;
525  twosA = (ones & b) | (u & c);
526  ones = u ^ c;
527  }
528  {
529  long b = (A[i + 2] & ~ B[i + 2]), c = (A[i + 3] & ~ B[i + 3]);
530  long u = ones ^ b;
531  twosB = (ones & b) | (u & c);
532  ones = u ^ c;
533  }
534  {
535  long u = twos ^ twosA;
536  foursA = (twos & twosA) | (u & twosB);
537  twos = u ^ twosB;
538  }
539  eights = fours & foursA;
540  fours = fours ^ foursA;
541 
542  tot8 += Pop(eights);
543  i += 4;
544  }
545 
546  if (i <= n - 2)
547  {
548  long b = (A[i] & ~ B[i]), c = (A[i + 1] & ~ B[i + 1]);
549  long u = ones ^ b;
550  long twosA = (ones & b) | (u & c);
551  ones = u ^ c;
552 
553  long foursA = twos & twosA;
554  twos = twos ^ twosA;
555 
556  long eights = fours & foursA;
557  fours = fours ^ foursA;
558 
559  tot8 += Pop(eights);
560  i += 2;
561  }
562 
563  if (i < n)
564  {
565  tot += Pop((A[i] & ~ B[i]));
566  }
567 
568  tot += (Pop(fours) << 2) + (Pop(twos) << 1) + Pop(ones) + (tot8 << 3);
569 
570  return tot;
571  }
572 
573  public static long Pop_xor(long[] A, long[] B, int wordOffset, int numWords)
574  {
575  int n = wordOffset + numWords;
576  long tot = 0, tot8 = 0;
577  long ones = 0, twos = 0, fours = 0;
578 
579  int i;
580  for (i = wordOffset; i <= n - 8; i += 8)
581  {
582  /* C macro from Hacker's Delight
583  #define CSA(h,l, a,b,c) \
584  {unsigned u = a ^ b; unsigned v = c; \
585  h = (a & b) | (u & v); l = u ^ v;}
586  ***/
587 
588  long twosA, twosB, foursA, foursB, eights;
589 
590  // CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
591  {
592  long b = (A[i] ^ B[i]), c = (A[i + 1] ^ B[i + 1]);
593  long u = ones ^ b;
594  twosA = (ones & b) | (u & c);
595  ones = u ^ c;
596  }
597  // CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
598  {
599  long b = (A[i + 2] ^ B[i + 2]), c = (A[i + 3] ^ B[i + 3]);
600  long u = ones ^ b;
601  twosB = (ones & b) | (u & c);
602  ones = u ^ c;
603  }
604  //CSA(foursA, twos, twos, twosA, twosB)
605  {
606  long u = twos ^ twosA;
607  foursA = (twos & twosA) | (u & twosB);
608  twos = u ^ twosB;
609  }
610  //CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
611  {
612  long b = (A[i + 4] ^ B[i + 4]), c = (A[i + 5] ^ B[i + 5]);
613  long u = ones ^ b;
614  twosA = (ones & b) | (u & c);
615  ones = u ^ c;
616  }
617  // CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
618  {
619  long b = (A[i + 6] ^ B[i + 6]), c = (A[i + 7] ^ B[i + 7]);
620  long u = ones ^ b;
621  twosB = (ones & b) | (u & c);
622  ones = u ^ c;
623  }
624  //CSA(foursB, twos, twos, twosA, twosB)
625  {
626  long u = twos ^ twosA;
627  foursB = (twos & twosA) | (u & twosB);
628  twos = u ^ twosB;
629  }
630 
631  //CSA(eights, fours, fours, foursA, foursB)
632  {
633  long u = fours ^ foursA;
634  eights = (fours & foursA) | (u & foursB);
635  fours = u ^ foursB;
636  }
637  tot8 += Pop(eights);
638  }
639 
640 
641  if (i <= n - 4)
642  {
643  long twosA, twosB, foursA, eights;
644  {
645  long b = (A[i] ^ B[i]), c = (A[i + 1] ^ B[i + 1]);
646  long u = ones ^ b;
647  twosA = (ones & b) | (u & c);
648  ones = u ^ c;
649  }
650  {
651  long b = (A[i + 2] ^ B[i + 2]), c = (A[i + 3] ^ B[i + 3]);
652  long u = ones ^ b;
653  twosB = (ones & b) | (u & c);
654  ones = u ^ c;
655  }
656  {
657  long u = twos ^ twosA;
658  foursA = (twos & twosA) | (u & twosB);
659  twos = u ^ twosB;
660  }
661  eights = fours & foursA;
662  fours = fours ^ foursA;
663 
664  tot8 += Pop(eights);
665  i += 4;
666  }
667 
668  if (i <= n - 2)
669  {
670  long b = (A[i] ^ B[i]), c = (A[i + 1] ^ B[i + 1]);
671  long u = ones ^ b;
672  long twosA = (ones & b) | (u & c);
673  ones = u ^ c;
674 
675  long foursA = twos & twosA;
676  twos = twos ^ twosA;
677 
678  long eights = fours & foursA;
679  fours = fours ^ foursA;
680 
681  tot8 += Pop(eights);
682  i += 2;
683  }
684 
685  if (i < n)
686  {
687  tot += Pop((A[i] ^ B[i]));
688  }
689 
690  tot += (Pop(fours) << 2) + (Pop(twos) << 1) + Pop(ones) + (tot8 << 3);
691 
692  return tot;
693  }
694 
695  /* python code to generate ntzTable
696  def ntz(val):
697  if val==0: return 8
698  i=0
699  while (val&0x01)==0:
700  i = i+1
701  val >>= 1
702  return i
703  print ','.join([ str(ntz(i)) for i in range(256) ])
704  ***/
705 
706  /// <summary>table of number of trailing zeros in a byte </summary>
707  //
708  public static readonly byte[] ntzTable = new byte[]
709  {
710  8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1,
711  0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
712  1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2,
713  0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
714  2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1,
715  0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0,
716  1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
717  0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
718  3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1,
719  0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0,
720  1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,
721  0, 1, 0
722  };
723 
724 
725  /// <summary>Returns number of trailing zeros in a 64 bit long value. </summary>
726  public static int Ntz(long val)
727  {
728  // A full binary search to determine the low byte was slower than
729  // a linear search for nextSetBit(). This is most likely because
730  // the implementation of nextSetBit() shifts bits to the right, increasing
731  // the probability that the first non-zero byte is in the rhs.
732  //
733  // This implementation does a single binary search at the top level only
734  // so that all other bit shifting can be done on ints instead of longs to
735  // remain friendly to 32 bit architectures. In addition, the case of a
736  // non-zero first byte is checked for first because it is the most common
737  // in dense bit arrays.
738 
739  int lower = (int) val;
740  int lowByte = lower & 0xff;
741  if (lowByte != 0)
742  return ntzTable[lowByte];
743 
744  if (lower != 0)
745  {
746  lowByte = (Number.URShift(lower, 8)) & 0xff;
747  if (lowByte != 0)
748  return ntzTable[lowByte] + 8;
749  lowByte = (Number.URShift(lower, 16)) & 0xff;
750  if (lowByte != 0)
751  return ntzTable[lowByte] + 16;
752  // no need to mask off low byte for the last byte in the 32 bit word
753  // no need to check for zero on the last byte either.
754  return ntzTable[Number.URShift(lower, 24)] + 24;
755  }
756  else
757  {
758  // grab upper 32 bits
759  int upper = (int) (val >> 32);
760  lowByte = upper & 0xff;
761  if (lowByte != 0)
762  return ntzTable[lowByte] + 32;
763  lowByte = (Number.URShift(upper, 8)) & 0xff;
764  if (lowByte != 0)
765  return ntzTable[lowByte] + 40;
766  lowByte = (Number.URShift(upper, 16)) & 0xff;
767  if (lowByte != 0)
768  return ntzTable[lowByte] + 48;
769  // no need to mask off low byte for the last byte in the 32 bit word
770  // no need to check for zero on the last byte either.
771  return ntzTable[Number.URShift(upper, 24)] + 56;
772  }
773  }
774 
775  /// <summary>Returns number of trailing zeros in a 32 bit int value. </summary>
776  public static int Ntz(int val)
777  {
778  // This implementation does a single binary search at the top level only.
779  // In addition, the case of a non-zero first byte is checked for first
780  // because it is the most common in dense bit arrays.
781 
782  int lowByte = val & 0xff;
783  if (lowByte != 0)
784  return ntzTable[lowByte];
785  lowByte = (Number.URShift(val, 8)) & 0xff;
786  if (lowByte != 0)
787  return ntzTable[lowByte] + 8;
788  lowByte = (Number.URShift(val, 16)) & 0xff;
789  if (lowByte != 0)
790  return ntzTable[lowByte] + 16;
791  // no need to mask off low byte for the last byte.
792  // no need to check for zero on the last byte either.
793  return ntzTable[Number.URShift(val, 24)] + 24;
794  }
795 
796  /// <summary>returns 0 based index of first set bit
797  /// (only works for x!=0)
798  /// <br/> This is an alternate implementation of ntz()
799  /// </summary>
800  public static int Ntz2(long x)
801  {
802  int n = 0;
803  int y = (int) x;
804  if (y == 0)
805  {
806  n += 32; y = (int) (Number.URShift(x, 32));
807  } // the only 64 bit shift necessary
808  if ((y & 0x0000FFFF) == 0)
809  {
810  n += 16; y = Number.URShift(y, 16);
811  }
812  if ((y & 0x000000FF) == 0)
813  {
814  n += 8; y = Number.URShift(y, 8);
815  }
816  return (ntzTable[y & 0xff]) + n;
817  }
818 
819  /// <summary>returns 0 based index of first set bit
820  /// <br/> This is an alternate implementation of ntz()
821  /// </summary>
822  public static int Ntz3(long x)
823  {
824  // another implementation taken from Hackers Delight, extended to 64 bits
825  // and converted to Java.
826  // Many 32 bit ntz algorithms are at http://www.hackersdelight.org/HDcode/ntz.cc
827  int n = 1;
828 
829  // do the first step as a long, all others as ints.
830  int y = (int) x;
831  if (y == 0)
832  {
833  n += 32; y = (int) (Number.URShift(x, 32));
834  }
835  if ((y & 0x0000FFFF) == 0)
836  {
837  n += 16; y = Number.URShift(y, 16);
838  }
839  if ((y & 0x000000FF) == 0)
840  {
841  n += 8; y = Number.URShift(y, 8);
842  }
843  if ((y & 0x0000000F) == 0)
844  {
845  n += 4; y = Number.URShift(y, 4);
846  }
847  if ((y & 0x00000003) == 0)
848  {
849  n += 2; y = Number.URShift(y, 2);
850  }
851  return n - (y & 1);
852  }
853 
854 
855  /// <summary>returns true if v is a power of two or zero</summary>
856  public static bool IsPowerOfTwo(int v)
857  {
858  return ((v & (v - 1)) == 0);
859  }
860 
861  /// <summary>returns true if v is a power of two or zero</summary>
862  public static bool IsPowerOfTwo(long v)
863  {
864  return ((v & (v - 1)) == 0);
865  }
866 
867  /// <summary>returns the next highest power of two, or the current value if it's already a power of two or zero</summary>
868  public static int NextHighestPowerOfTwo(int v)
869  {
870  v--;
871  v |= v >> 1;
872  v |= v >> 2;
873  v |= v >> 4;
874  v |= v >> 8;
875  v |= v >> 16;
876  v++;
877  return v;
878  }
879 
880  /// <summary>returns the next highest power of two, or the current value if it's already a power of two or zero</summary>
881  public static long NextHighestPowerOfTwo(long v)
882  {
883  v--;
884  v |= v >> 1;
885  v |= v >> 2;
886  v |= v >> 4;
887  v |= v >> 8;
888  v |= v >> 16;
889  v |= v >> 32;
890  v++;
891  return v;
892  }
893  }
894 }
Generated on Thu Jan 3 2013 02:34:13 for Lucene.Net by   doxygen 1.8.3