001: /**
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */package org.apache.solr.util;
017:
018: /** A variety of high efficiencly bit twiddling routines.
019: *
020: * @author yonik
021: * @version $Id$
022: */
023: public class BitUtil {
024:
025: /** Returns the number of bits set in the long */
026: public static int pop(long x) {
027: /* Hacker's Delight 32 bit pop function:
028: * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
029: *
030: int pop(unsigned x) {
031: x = x - ((x >> 1) & 0x55555555);
032: x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
033: x = (x + (x >> 4)) & 0x0F0F0F0F;
034: x = x + (x >> 8);
035: x = x + (x >> 16);
036: return x & 0x0000003F;
037: }
038: ***/
039:
040: // 64 bit java version of the C function from above
041: x = x - ((x >>> 1) & 0x5555555555555555L);
042: x = (x & 0x3333333333333333L)
043: + ((x >>> 2) & 0x3333333333333333L);
044: x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
045: x = x + (x >>> 8);
046: x = x + (x >>> 16);
047: x = x + (x >>> 32);
048: return ((int) x) & 0x7F;
049: }
050:
051: /*** Returns the number of set bits in an array of longs. */
052: public static long pop_array(long A[], int wordOffset, int numWords) {
053: /*
054: * Robert Harley and David Seal's bit counting algorithm, as documented
055: * in the revisions of Hacker's Delight
056: * http://www.hackersdelight.org/revisions.pdf
057: * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
058: *
059: * This function was adapted to Java, and extended to use 64 bit words.
060: * if only we had access to wider registers like SSE from java...
061: *
062: * This function can be transformed to compute the popcount of other functions
063: * on bitsets via something like this:
064: * sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
065: *
066: */
067: int n = wordOffset + numWords;
068: long tot = 0, tot8 = 0;
069: long ones = 0, twos = 0, fours = 0;
070:
071: int i;
072: for (i = wordOffset; i <= n - 8; i += 8) {
073: /*** C macro from Hacker's Delight
074: #define CSA(h,l, a,b,c) \
075: {unsigned u = a ^ b; unsigned v = c; \
076: h = (a & b) | (u & v); l = u ^ v;}
077: ***/
078:
079: long twosA, twosB, foursA, foursB, eights;
080:
081: // CSA(twosA, ones, ones, A[i], A[i+1])
082: {
083: long b = A[i], c = A[i + 1];
084: long u = ones ^ b;
085: twosA = (ones & b) | (u & c);
086: ones = u ^ c;
087: }
088: // CSA(twosB, ones, ones, A[i+2], A[i+3])
089: {
090: long b = A[i + 2], c = A[i + 3];
091: long u = ones ^ b;
092: twosB = (ones & b) | (u & c);
093: ones = u ^ c;
094: }
095: //CSA(foursA, twos, twos, twosA, twosB)
096: {
097: long u = twos ^ twosA;
098: foursA = (twos & twosA) | (u & twosB);
099: twos = u ^ twosB;
100: }
101: //CSA(twosA, ones, ones, A[i+4], A[i+5])
102: {
103: long b = A[i + 4], c = A[i + 5];
104: long u = ones ^ b;
105: twosA = (ones & b) | (u & c);
106: ones = u ^ c;
107: }
108: // CSA(twosB, ones, ones, A[i+6], A[i+7])
109: {
110: long b = A[i + 6], c = A[i + 7];
111: long u = ones ^ b;
112: twosB = (ones & b) | (u & c);
113: ones = u ^ c;
114: }
115: //CSA(foursB, twos, twos, twosA, twosB)
116: {
117: long u = twos ^ twosA;
118: foursB = (twos & twosA) | (u & twosB);
119: twos = u ^ twosB;
120: }
121:
122: //CSA(eights, fours, fours, foursA, foursB)
123: {
124: long u = fours ^ foursA;
125: eights = (fours & foursA) | (u & foursB);
126: fours = u ^ foursB;
127: }
128: tot8 += pop(eights);
129: }
130:
131: // handle trailing words in a binary-search manner...
132: // derived from the loop above by setting specific elements to 0.
133: // the original method in Hackers Delight used a simple for loop:
134: // for (i = i; i < n; i++) // Add in the last elements
135: // tot = tot + pop(A[i]);
136:
137: if (i <= n - 4) {
138: long twosA, twosB, foursA, eights;
139: {
140: long b = A[i], c = A[i + 1];
141: long u = ones ^ b;
142: twosA = (ones & b) | (u & c);
143: ones = u ^ c;
144: }
145: {
146: long b = A[i + 2], c = A[i + 3];
147: long u = ones ^ b;
148: twosB = (ones & b) | (u & c);
149: ones = u ^ c;
150: }
151: {
152: long u = twos ^ twosA;
153: foursA = (twos & twosA) | (u & twosB);
154: twos = u ^ twosB;
155: }
156: eights = fours & foursA;
157: fours = fours ^ foursA;
158:
159: tot8 += pop(eights);
160: i += 4;
161: }
162:
163: if (i <= n - 2) {
164: long b = A[i], c = A[i + 1];
165: long u = ones ^ b;
166: long twosA = (ones & b) | (u & c);
167: ones = u ^ c;
168:
169: long foursA = twos & twosA;
170: twos = twos ^ twosA;
171:
172: long eights = fours & foursA;
173: fours = fours ^ foursA;
174:
175: tot8 += pop(eights);
176: i += 2;
177: }
178:
179: if (i < n) {
180: tot += pop(A[i]);
181: }
182:
183: tot += (pop(fours) << 2) + (pop(twos) << 1) + pop(ones)
184: + (tot8 << 3);
185:
186: return tot;
187: }
188:
189: /** Returns the popcount or cardinality of the two sets after an intersection.
190: * Neither array is modified.
191: */
192: public static long pop_intersect(long A[], long B[],
193: int wordOffset, int numWords) {
194: // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
195: int n = wordOffset + numWords;
196: long tot = 0, tot8 = 0;
197: long ones = 0, twos = 0, fours = 0;
198:
199: int i;
200: for (i = wordOffset; i <= n - 8; i += 8) {
201: long twosA, twosB, foursA, foursB, eights;
202:
203: // CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
204: {
205: long b = (A[i] & B[i]), c = (A[i + 1] & B[i + 1]);
206: long u = ones ^ b;
207: twosA = (ones & b) | (u & c);
208: ones = u ^ c;
209: }
210: // CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
211: {
212: long b = (A[i + 2] & B[i + 2]), c = (A[i + 3] & B[i + 3]);
213: long u = ones ^ b;
214: twosB = (ones & b) | (u & c);
215: ones = u ^ c;
216: }
217: //CSA(foursA, twos, twos, twosA, twosB)
218: {
219: long u = twos ^ twosA;
220: foursA = (twos & twosA) | (u & twosB);
221: twos = u ^ twosB;
222: }
223: //CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
224: {
225: long b = (A[i + 4] & B[i + 4]), c = (A[i + 5] & B[i + 5]);
226: long u = ones ^ b;
227: twosA = (ones & b) | (u & c);
228: ones = u ^ c;
229: }
230: // CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
231: {
232: long b = (A[i + 6] & B[i + 6]), c = (A[i + 7] & B[i + 7]);
233: long u = ones ^ b;
234: twosB = (ones & b) | (u & c);
235: ones = u ^ c;
236: }
237: //CSA(foursB, twos, twos, twosA, twosB)
238: {
239: long u = twos ^ twosA;
240: foursB = (twos & twosA) | (u & twosB);
241: twos = u ^ twosB;
242: }
243:
244: //CSA(eights, fours, fours, foursA, foursB)
245: {
246: long u = fours ^ foursA;
247: eights = (fours & foursA) | (u & foursB);
248: fours = u ^ foursB;
249: }
250: tot8 += pop(eights);
251: }
252:
253: if (i <= n - 4) {
254: long twosA, twosB, foursA, eights;
255: {
256: long b = (A[i] & B[i]), c = (A[i + 1] & B[i + 1]);
257: long u = ones ^ b;
258: twosA = (ones & b) | (u & c);
259: ones = u ^ c;
260: }
261: {
262: long b = (A[i + 2] & B[i + 2]), c = (A[i + 3] & B[i + 3]);
263: long u = ones ^ b;
264: twosB = (ones & b) | (u & c);
265: ones = u ^ c;
266: }
267: {
268: long u = twos ^ twosA;
269: foursA = (twos & twosA) | (u & twosB);
270: twos = u ^ twosB;
271: }
272: eights = fours & foursA;
273: fours = fours ^ foursA;
274:
275: tot8 += pop(eights);
276: i += 4;
277: }
278:
279: if (i <= n - 2) {
280: long b = (A[i] & B[i]), c = (A[i + 1] & B[i + 1]);
281: long u = ones ^ b;
282: long twosA = (ones & b) | (u & c);
283: ones = u ^ c;
284:
285: long foursA = twos & twosA;
286: twos = twos ^ twosA;
287:
288: long eights = fours & foursA;
289: fours = fours ^ foursA;
290:
291: tot8 += pop(eights);
292: i += 2;
293: }
294:
295: if (i < n) {
296: tot += pop((A[i] & B[i]));
297: }
298:
299: tot += (pop(fours) << 2) + (pop(twos) << 1) + pop(ones)
300: + (tot8 << 3);
301:
302: return tot;
303: }
304:
305: /** Returns the popcount or cardinality of the union of two sets.
306: * Neither array is modified.
307: */
308: public static long pop_union(long A[], long B[], int wordOffset,
309: int numWords) {
310: // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \| B[\1]\)/g'
311: int n = wordOffset + numWords;
312: long tot = 0, tot8 = 0;
313: long ones = 0, twos = 0, fours = 0;
314:
315: int i;
316: for (i = wordOffset; i <= n - 8; i += 8) {
317: /*** C macro from Hacker's Delight
318: #define CSA(h,l, a,b,c) \
319: {unsigned u = a ^ b; unsigned v = c; \
320: h = (a & b) | (u & v); l = u ^ v;}
321: ***/
322:
323: long twosA, twosB, foursA, foursB, eights;
324:
325: // CSA(twosA, ones, ones, (A[i] | B[i]), (A[i+1] | B[i+1]))
326: {
327: long b = (A[i] | B[i]), c = (A[i + 1] | B[i + 1]);
328: long u = ones ^ b;
329: twosA = (ones & b) | (u & c);
330: ones = u ^ c;
331: }
332: // CSA(twosB, ones, ones, (A[i+2] | B[i+2]), (A[i+3] | B[i+3]))
333: {
334: long b = (A[i + 2] | B[i + 2]), c = (A[i + 3] | B[i + 3]);
335: long u = ones ^ b;
336: twosB = (ones & b) | (u & c);
337: ones = u ^ c;
338: }
339: //CSA(foursA, twos, twos, twosA, twosB)
340: {
341: long u = twos ^ twosA;
342: foursA = (twos & twosA) | (u & twosB);
343: twos = u ^ twosB;
344: }
345: //CSA(twosA, ones, ones, (A[i+4] | B[i+4]), (A[i+5] | B[i+5]))
346: {
347: long b = (A[i + 4] | B[i + 4]), c = (A[i + 5] | B[i + 5]);
348: long u = ones ^ b;
349: twosA = (ones & b) | (u & c);
350: ones = u ^ c;
351: }
352: // CSA(twosB, ones, ones, (A[i+6] | B[i+6]), (A[i+7] | B[i+7]))
353: {
354: long b = (A[i + 6] | B[i + 6]), c = (A[i + 7] | B[i + 7]);
355: long u = ones ^ b;
356: twosB = (ones & b) | (u & c);
357: ones = u ^ c;
358: }
359: //CSA(foursB, twos, twos, twosA, twosB)
360: {
361: long u = twos ^ twosA;
362: foursB = (twos & twosA) | (u & twosB);
363: twos = u ^ twosB;
364: }
365:
366: //CSA(eights, fours, fours, foursA, foursB)
367: {
368: long u = fours ^ foursA;
369: eights = (fours & foursA) | (u & foursB);
370: fours = u ^ foursB;
371: }
372: tot8 += pop(eights);
373: }
374:
375: if (i <= n - 4) {
376: long twosA, twosB, foursA, eights;
377: {
378: long b = (A[i] | B[i]), c = (A[i + 1] | B[i + 1]);
379: long u = ones ^ b;
380: twosA = (ones & b) | (u & c);
381: ones = u ^ c;
382: }
383: {
384: long b = (A[i + 2] | B[i + 2]), c = (A[i + 3] | B[i + 3]);
385: long u = ones ^ b;
386: twosB = (ones & b) | (u & c);
387: ones = u ^ c;
388: }
389: {
390: long u = twos ^ twosA;
391: foursA = (twos & twosA) | (u & twosB);
392: twos = u ^ twosB;
393: }
394: eights = fours & foursA;
395: fours = fours ^ foursA;
396:
397: tot8 += pop(eights);
398: i += 4;
399: }
400:
401: if (i <= n - 2) {
402: long b = (A[i] | B[i]), c = (A[i + 1] | B[i + 1]);
403: long u = ones ^ b;
404: long twosA = (ones & b) | (u & c);
405: ones = u ^ c;
406:
407: long foursA = twos & twosA;
408: twos = twos ^ twosA;
409:
410: long eights = fours & foursA;
411: fours = fours ^ foursA;
412:
413: tot8 += pop(eights);
414: i += 2;
415: }
416:
417: if (i < n) {
418: tot += pop((A[i] | B[i]));
419: }
420:
421: tot += (pop(fours) << 2) + (pop(twos) << 1) + pop(ones)
422: + (tot8 << 3);
423:
424: return tot;
425: }
426:
427: /** Returns the popcount or cardinality of A & ~B
428: * Neither array is modified.
429: */
430: public static long pop_andnot(long A[], long B[], int wordOffset,
431: int numWords) {
432: // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& ~B[\1]\)/g'
433: int n = wordOffset + numWords;
434: long tot = 0, tot8 = 0;
435: long ones = 0, twos = 0, fours = 0;
436:
437: int i;
438: for (i = wordOffset; i <= n - 8; i += 8) {
439: /*** C macro from Hacker's Delight
440: #define CSA(h,l, a,b,c) \
441: {unsigned u = a ^ b; unsigned v = c; \
442: h = (a & b) | (u & v); l = u ^ v;}
443: ***/
444:
445: long twosA, twosB, foursA, foursB, eights;
446:
447: // CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
448: {
449: long b = (A[i] & ~B[i]), c = (A[i + 1] & ~B[i + 1]);
450: long u = ones ^ b;
451: twosA = (ones & b) | (u & c);
452: ones = u ^ c;
453: }
454: // CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
455: {
456: long b = (A[i + 2] & ~B[i + 2]), c = (A[i + 3] & ~B[i + 3]);
457: long u = ones ^ b;
458: twosB = (ones & b) | (u & c);
459: ones = u ^ c;
460: }
461: //CSA(foursA, twos, twos, twosA, twosB)
462: {
463: long u = twos ^ twosA;
464: foursA = (twos & twosA) | (u & twosB);
465: twos = u ^ twosB;
466: }
467: //CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
468: {
469: long b = (A[i + 4] & ~B[i + 4]), c = (A[i + 5] & ~B[i + 5]);
470: long u = ones ^ b;
471: twosA = (ones & b) | (u & c);
472: ones = u ^ c;
473: }
474: // CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
475: {
476: long b = (A[i + 6] & ~B[i + 6]), c = (A[i + 7] & ~B[i + 7]);
477: long u = ones ^ b;
478: twosB = (ones & b) | (u & c);
479: ones = u ^ c;
480: }
481: //CSA(foursB, twos, twos, twosA, twosB)
482: {
483: long u = twos ^ twosA;
484: foursB = (twos & twosA) | (u & twosB);
485: twos = u ^ twosB;
486: }
487:
488: //CSA(eights, fours, fours, foursA, foursB)
489: {
490: long u = fours ^ foursA;
491: eights = (fours & foursA) | (u & foursB);
492: fours = u ^ foursB;
493: }
494: tot8 += pop(eights);
495: }
496:
497: if (i <= n - 4) {
498: long twosA, twosB, foursA, eights;
499: {
500: long b = (A[i] & ~B[i]), c = (A[i + 1] & ~B[i + 1]);
501: long u = ones ^ b;
502: twosA = (ones & b) | (u & c);
503: ones = u ^ c;
504: }
505: {
506: long b = (A[i + 2] & ~B[i + 2]), c = (A[i + 3] & ~B[i + 3]);
507: long u = ones ^ b;
508: twosB = (ones & b) | (u & c);
509: ones = u ^ c;
510: }
511: {
512: long u = twos ^ twosA;
513: foursA = (twos & twosA) | (u & twosB);
514: twos = u ^ twosB;
515: }
516: eights = fours & foursA;
517: fours = fours ^ foursA;
518:
519: tot8 += pop(eights);
520: i += 4;
521: }
522:
523: if (i <= n - 2) {
524: long b = (A[i] & ~B[i]), c = (A[i + 1] & ~B[i + 1]);
525: long u = ones ^ b;
526: long twosA = (ones & b) | (u & c);
527: ones = u ^ c;
528:
529: long foursA = twos & twosA;
530: twos = twos ^ twosA;
531:
532: long eights = fours & foursA;
533: fours = fours ^ foursA;
534:
535: tot8 += pop(eights);
536: i += 2;
537: }
538:
539: if (i < n) {
540: tot += pop((A[i] & ~B[i]));
541: }
542:
543: tot += (pop(fours) << 2) + (pop(twos) << 1) + pop(ones)
544: + (tot8 << 3);
545:
546: return tot;
547: }
548:
549: public static long pop_xor(long A[], long B[], int wordOffset,
550: int numWords) {
551: int n = wordOffset + numWords;
552: long tot = 0, tot8 = 0;
553: long ones = 0, twos = 0, fours = 0;
554:
555: int i;
556: for (i = wordOffset; i <= n - 8; i += 8) {
557: /*** C macro from Hacker's Delight
558: #define CSA(h,l, a,b,c) \
559: {unsigned u = a ^ b; unsigned v = c; \
560: h = (a & b) | (u & v); l = u ^ v;}
561: ***/
562:
563: long twosA, twosB, foursA, foursB, eights;
564:
565: // CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
566: {
567: long b = (A[i] ^ B[i]), c = (A[i + 1] ^ B[i + 1]);
568: long u = ones ^ b;
569: twosA = (ones & b) | (u & c);
570: ones = u ^ c;
571: }
572: // CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
573: {
574: long b = (A[i + 2] ^ B[i + 2]), c = (A[i + 3] ^ B[i + 3]);
575: long u = ones ^ b;
576: twosB = (ones & b) | (u & c);
577: ones = u ^ c;
578: }
579: //CSA(foursA, twos, twos, twosA, twosB)
580: {
581: long u = twos ^ twosA;
582: foursA = (twos & twosA) | (u & twosB);
583: twos = u ^ twosB;
584: }
585: //CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
586: {
587: long b = (A[i + 4] ^ B[i + 4]), c = (A[i + 5] ^ B[i + 5]);
588: long u = ones ^ b;
589: twosA = (ones & b) | (u & c);
590: ones = u ^ c;
591: }
592: // CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
593: {
594: long b = (A[i + 6] ^ B[i + 6]), c = (A[i + 7] ^ B[i + 7]);
595: long u = ones ^ b;
596: twosB = (ones & b) | (u & c);
597: ones = u ^ c;
598: }
599: //CSA(foursB, twos, twos, twosA, twosB)
600: {
601: long u = twos ^ twosA;
602: foursB = (twos & twosA) | (u & twosB);
603: twos = u ^ twosB;
604: }
605:
606: //CSA(eights, fours, fours, foursA, foursB)
607: {
608: long u = fours ^ foursA;
609: eights = (fours & foursA) | (u & foursB);
610: fours = u ^ foursB;
611: }
612: tot8 += pop(eights);
613: }
614:
615: if (i <= n - 4) {
616: long twosA, twosB, foursA, eights;
617: {
618: long b = (A[i] ^ B[i]), c = (A[i + 1] ^ B[i + 1]);
619: long u = ones ^ b;
620: twosA = (ones & b) | (u & c);
621: ones = u ^ c;
622: }
623: {
624: long b = (A[i + 2] ^ B[i + 2]), c = (A[i + 3] ^ B[i + 3]);
625: long u = ones ^ b;
626: twosB = (ones & b) | (u & c);
627: ones = u ^ c;
628: }
629: {
630: long u = twos ^ twosA;
631: foursA = (twos & twosA) | (u & twosB);
632: twos = u ^ twosB;
633: }
634: eights = fours & foursA;
635: fours = fours ^ foursA;
636:
637: tot8 += pop(eights);
638: i += 4;
639: }
640:
641: if (i <= n - 2) {
642: long b = (A[i] ^ B[i]), c = (A[i + 1] ^ B[i + 1]);
643: long u = ones ^ b;
644: long twosA = (ones & b) | (u & c);
645: ones = u ^ c;
646:
647: long foursA = twos & twosA;
648: twos = twos ^ twosA;
649:
650: long eights = fours & foursA;
651: fours = fours ^ foursA;
652:
653: tot8 += pop(eights);
654: i += 2;
655: }
656:
657: if (i < n) {
658: tot += pop((A[i] ^ B[i]));
659: }
660:
661: tot += (pop(fours) << 2) + (pop(twos) << 1) + pop(ones)
662: + (tot8 << 3);
663:
664: return tot;
665: }
666:
667: /* python code to generate ntzTable
668: def ntz(val):
669: if val==0: return 8
670: i=0
671: while (val&0x01)==0:
672: i = i+1
673: val >>= 1
674: return i
675: print ','.join([ str(ntz(i)) for i in range(256) ])
676: ***/
677: /** table of number of trailing zeros in a byte */
678: public static final byte[] ntzTable = { 8, 0, 1, 0, 2, 0, 1, 0, 3,
679: 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,
680: 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
681: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2,
682: 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,
683: 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,
684: 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7,
685: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,
686: 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3,
687: 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,
688: 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
689: 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,
690: 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,
691: 0, 1, 0, 2, 0, 1, 0 };
692:
693: /** Returns number of trailing zeros in the 64 bit long value. */
694: public static int ntz(long val) {
695: // A full binary search to determine the low byte was slower than
696: // a linear search for nextSetBit(). This is most likely because
697: // the implementation of nextSetBit() shifts bits to the right, increasing
698: // the probability that the first non-zero byte is in the rhs.
699: //
700: // This implementation does a single binary search at the top level only
701: // so that all other bit shifting can be done on ints instead of longs to
702: // remain friendly to 32 bit architectures. In addition, the case of a
703: // non-zero first byte is checked for first because it is the most common
704: // in dense bit arrays.
705:
706: int lower = (int) val;
707: int lowByte = lower & 0xff;
708: if (lowByte != 0)
709: return ntzTable[lowByte];
710:
711: if (lower != 0) {
712: lowByte = (lower >>> 8) & 0xff;
713: if (lowByte != 0)
714: return ntzTable[lowByte] + 8;
715: lowByte = (lower >>> 16) & 0xff;
716: if (lowByte != 0)
717: return ntzTable[lowByte] + 16;
718: // no need to mask off low byte for the last byte in the 32 bit word
719: // no need to check for zero on the last byte either.
720: return ntzTable[lower >>> 24] + 24;
721: } else {
722: // grab upper 32 bits
723: int upper = (int) (val >> 32);
724: lowByte = upper & 0xff;
725: if (lowByte != 0)
726: return ntzTable[lowByte] + 32;
727: lowByte = (upper >>> 8) & 0xff;
728: if (lowByte != 0)
729: return ntzTable[lowByte] + 40;
730: lowByte = (upper >>> 16) & 0xff;
731: if (lowByte != 0)
732: return ntzTable[lowByte] + 48;
733: // no need to mask off low byte for the last byte in the 32 bit word
734: // no need to check for zero on the last byte either.
735: return ntzTable[upper >>> 24] + 56;
736: }
737: }
738:
739: /** returns 0 based index of first set bit
740: * (only works for x!=0)
741: * <br/> This is an alternate implementation of ntz()
742: */
743: public static int ntz2(long x) {
744: int n = 0;
745: int y = (int) x;
746: if (y == 0) {
747: n += 32;
748: y = (int) (x >>> 32);
749: } // the only 64 bit shift necessary
750: if ((y & 0x0000FFFF) == 0) {
751: n += 16;
752: y >>>= 16;
753: }
754: if ((y & 0x000000FF) == 0) {
755: n += 8;
756: y >>>= 8;
757: }
758: return (ntzTable[y & 0xff]) + n;
759: }
760:
761: /** returns 0 based index of first set bit
762: * <br/> This is an alternate implementation of ntz()
763: */
764: public static int ntz3(long x) {
765: // another implementation taken from Hackers Delight, extended to 64 bits
766: // and converted to Java.
767: // Many 32 bit ntz algorithms are at http://www.hackersdelight.org/HDcode/ntz.cc
768: int n = 1;
769:
770: // do the first step as a long, all others as ints.
771: int y = (int) x;
772: if (y == 0) {
773: n += 32;
774: y = (int) (x >>> 32);
775: }
776: if ((y & 0x0000FFFF) == 0) {
777: n += 16;
778: y >>>= 16;
779: }
780: if ((y & 0x000000FF) == 0) {
781: n += 8;
782: y >>>= 8;
783: }
784: if ((y & 0x0000000F) == 0) {
785: n += 4;
786: y >>>= 4;
787: }
788: if ((y & 0x00000003) == 0) {
789: n += 2;
790: y >>>= 2;
791: }
792: return n - (y & 1);
793: }
794:
795: /** returns true if v is a power of two or zero*/
796: public static boolean isPowerOfTwo(int v) {
797: return ((v & (v - 1)) == 0);
798: }
799:
800: /** returns true if v is a power of two or zero*/
801: public static boolean isPowerOfTwo(long v) {
802: return ((v & (v - 1)) == 0);
803: }
804:
805: /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
806: public static int nextHighestPowerOfTwo(int v) {
807: v--;
808: v |= v >> 1;
809: v |= v >> 2;
810: v |= v >> 4;
811: v |= v >> 8;
812: v |= v >> 16;
813: v++;
814: return v;
815: }
816:
817: /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
818: public static long nextHighestPowerOfTwo(long v) {
819: v--;
820: v |= v >> 1;
821: v |= v >> 2;
822: v |= v >> 4;
823: v |= v >> 8;
824: v |= v >> 16;
825: v |= v >> 32;
826: v++;
827: return v;
828: }
829:
830: }
|