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
9 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 package org.apache.lucene.util; // from org.apache.solr.util rev 555343
20 /** A variety of high efficiency bit twiddling routines.
23 public final class BitUtil {
25 private BitUtil() {} // no instance
27 /** Returns the number of bits set in the long */
28 public static int pop(long x) {
29 /* Hacker's Delight 32 bit pop function:
30 * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
33 x = x - ((x >> 1) & 0x55555555);
34 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
35 x = (x + (x >> 4)) & 0x0F0F0F0F;
38 return x & 0x0000003F;
42 // 64 bit java version of the C function from above
43 x = x - ((x >>> 1) & 0x5555555555555555L);
44 x = (x & 0x3333333333333333L) + ((x >>>2 ) & 0x3333333333333333L);
45 x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0FL;
49 return ((int)x) & 0x7F;
52 /*** Returns the number of set bits in an array of longs. */
53 public static long pop_array(long A[], int wordOffset, int numWords) {
55 * Robert Harley and David Seal's bit counting algorithm, as documented
56 * in the revisions of Hacker's Delight
57 * http://www.hackersdelight.org/revisions.pdf
58 * http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.cc
60 * This function was adapted to Java, and extended to use 64 bit words.
61 * if only we had access to wider registers like SSE from java...
63 * This function can be transformed to compute the popcount of other functions
64 * on bitsets via something like this:
65 * sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
68 int n = wordOffset+numWords;
70 long ones=0, twos=0, fours=0;
73 for (i = wordOffset; i <= n - 8; i+=8) {
74 /*** C macro from Hacker's Delight
75 #define CSA(h,l, a,b,c) \
76 {unsigned u = a ^ b; unsigned v = c; \
77 h = (a & b) | (u & v); l = u ^ v;}
80 long twosA,twosB,foursA,foursB,eights;
82 // CSA(twosA, ones, ones, A[i], A[i+1])
84 long b=A[i], c=A[i+1];
86 twosA=(ones & b)|( u & c);
89 // CSA(twosB, ones, ones, A[i+2], A[i+3])
91 long b=A[i+2], c=A[i+3];
93 twosB =(ones&b)|(u&c);
96 //CSA(foursA, twos, twos, twosA, twosB)
99 foursA=(twos&twosA)|(u&twosB);
102 //CSA(twosA, ones, ones, A[i+4], A[i+5])
104 long b=A[i+4], c=A[i+5];
106 twosA=(ones&b)|(u&c);
109 // CSA(twosB, ones, ones, A[i+6], A[i+7])
111 long b=A[i+6], c=A[i+7];
113 twosB=(ones&b)|(u&c);
116 //CSA(foursB, twos, twos, twosA, twosB)
119 foursB=(twos&twosA)|(u&twosB);
123 //CSA(eights, fours, fours, foursA, foursB)
126 eights=(fours&foursA)|(u&foursB);
132 // handle trailing words in a binary-search manner...
133 // derived from the loop above by setting specific elements to 0.
134 // the original method in Hackers Delight used a simple for loop:
135 // for (i = i; i < n; i++) // Add in the last elements
136 // tot = tot + pop(A[i]);
139 long twosA, twosB, foursA, eights;
141 long b=A[i], c=A[i+1];
143 twosA=(ones & b)|( u & c);
147 long b=A[i+2], c=A[i+3];
149 twosB =(ones&b)|(u&c);
154 foursA=(twos&twosA)|(u&twosB);
165 long b=A[i], c=A[i+1];
167 long twosA=(ones & b)|( u & c);
170 long foursA=twos&twosA;
173 long eights=fours&foursA;
184 tot += (pop(fours)<<2)
192 /** Returns the popcount or cardinality of the two sets after an intersection.
193 * Neither array is modified.
195 public static long pop_intersect(long A[], long B[], int wordOffset, int numWords) {
196 // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& B[\1]\)/g'
197 int n = wordOffset+numWords;
199 long ones=0, twos=0, fours=0;
202 for (i = wordOffset; i <= n - 8; i+=8) {
203 long twosA,twosB,foursA,foursB,eights;
205 // CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
207 long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
209 twosA=(ones & b)|( u & c);
212 // CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
214 long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
216 twosB =(ones&b)|(u&c);
219 //CSA(foursA, twos, twos, twosA, twosB)
222 foursA=(twos&twosA)|(u&twosB);
225 //CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
227 long b=(A[i+4] & B[i+4]), c=(A[i+5] & B[i+5]);
229 twosA=(ones&b)|(u&c);
232 // CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
234 long b=(A[i+6] & B[i+6]), c=(A[i+7] & B[i+7]);
236 twosB=(ones&b)|(u&c);
239 //CSA(foursB, twos, twos, twosA, twosB)
242 foursB=(twos&twosA)|(u&twosB);
246 //CSA(eights, fours, fours, foursA, foursB)
249 eights=(fours&foursA)|(u&foursB);
257 long twosA, twosB, foursA, eights;
259 long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
261 twosA=(ones & b)|( u & c);
265 long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
267 twosB =(ones&b)|(u&c);
272 foursA=(twos&twosA)|(u&twosB);
283 long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
285 long twosA=(ones & b)|( u & c);
288 long foursA=twos&twosA;
291 long eights=fours&foursA;
299 tot += pop((A[i] & B[i]));
302 tot += (pop(fours)<<2)
310 /** Returns the popcount or cardinality of the union of two sets.
311 * Neither array is modified.
313 public static long pop_union(long A[], long B[], int wordOffset, int numWords) {
314 // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \| B[\1]\)/g'
315 int n = wordOffset+numWords;
317 long ones=0, twos=0, fours=0;
320 for (i = wordOffset; i <= n - 8; i+=8) {
321 /*** C macro from Hacker's Delight
322 #define CSA(h,l, a,b,c) \
323 {unsigned u = a ^ b; unsigned v = c; \
324 h = (a & b) | (u & v); l = u ^ v;}
327 long twosA,twosB,foursA,foursB,eights;
329 // CSA(twosA, ones, ones, (A[i] | B[i]), (A[i+1] | B[i+1]))
331 long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
333 twosA=(ones & b)|( u & c);
336 // CSA(twosB, ones, ones, (A[i+2] | B[i+2]), (A[i+3] | B[i+3]))
338 long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
340 twosB =(ones&b)|(u&c);
343 //CSA(foursA, twos, twos, twosA, twosB)
346 foursA=(twos&twosA)|(u&twosB);
349 //CSA(twosA, ones, ones, (A[i+4] | B[i+4]), (A[i+5] | B[i+5]))
351 long b=(A[i+4] | B[i+4]), c=(A[i+5] | B[i+5]);
353 twosA=(ones&b)|(u&c);
356 // CSA(twosB, ones, ones, (A[i+6] | B[i+6]), (A[i+7] | B[i+7]))
358 long b=(A[i+6] | B[i+6]), c=(A[i+7] | B[i+7]);
360 twosB=(ones&b)|(u&c);
363 //CSA(foursB, twos, twos, twosA, twosB)
366 foursB=(twos&twosA)|(u&twosB);
370 //CSA(eights, fours, fours, foursA, foursB)
373 eights=(fours&foursA)|(u&foursB);
381 long twosA, twosB, foursA, eights;
383 long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
385 twosA=(ones & b)|( u & c);
389 long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
391 twosB =(ones&b)|(u&c);
396 foursA=(twos&twosA)|(u&twosB);
407 long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
409 long twosA=(ones & b)|( u & c);
412 long foursA=twos&twosA;
415 long eights=fours&foursA;
423 tot += pop((A[i] | B[i]));
426 tot += (pop(fours)<<2)
434 /** Returns the popcount or cardinality of A & ~B
435 * Neither array is modified.
437 public static long pop_andnot(long A[], long B[], int wordOffset, int numWords) {
438 // generated from pop_array via sed 's/A\[\([^]]*\)\]/\(A[\1] \& ~B[\1]\)/g'
439 int n = wordOffset+numWords;
441 long ones=0, twos=0, fours=0;
444 for (i = wordOffset; i <= n - 8; i+=8) {
445 /*** C macro from Hacker's Delight
446 #define CSA(h,l, a,b,c) \
447 {unsigned u = a ^ b; unsigned v = c; \
448 h = (a & b) | (u & v); l = u ^ v;}
451 long twosA,twosB,foursA,foursB,eights;
453 // CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
455 long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
457 twosA=(ones & b)|( u & c);
460 // CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
462 long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
464 twosB =(ones&b)|(u&c);
467 //CSA(foursA, twos, twos, twosA, twosB)
470 foursA=(twos&twosA)|(u&twosB);
473 //CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
475 long b=(A[i+4] & ~B[i+4]), c=(A[i+5] & ~B[i+5]);
477 twosA=(ones&b)|(u&c);
480 // CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
482 long b=(A[i+6] & ~B[i+6]), c=(A[i+7] & ~B[i+7]);
484 twosB=(ones&b)|(u&c);
487 //CSA(foursB, twos, twos, twosA, twosB)
490 foursB=(twos&twosA)|(u&twosB);
494 //CSA(eights, fours, fours, foursA, foursB)
497 eights=(fours&foursA)|(u&foursB);
505 long twosA, twosB, foursA, eights;
507 long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
509 twosA=(ones & b)|( u & c);
513 long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
515 twosB =(ones&b)|(u&c);
520 foursA=(twos&twosA)|(u&twosB);
531 long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
533 long twosA=(ones & b)|( u & c);
536 long foursA=twos&twosA;
539 long eights=fours&foursA;
547 tot += pop((A[i] & ~B[i]));
550 tot += (pop(fours)<<2)
558 public static long pop_xor(long A[], long B[], int wordOffset, int numWords) {
559 int n = wordOffset+numWords;
561 long ones=0, twos=0, fours=0;
564 for (i = wordOffset; i <= n - 8; i+=8) {
565 /*** C macro from Hacker's Delight
566 #define CSA(h,l, a,b,c) \
567 {unsigned u = a ^ b; unsigned v = c; \
568 h = (a & b) | (u & v); l = u ^ v;}
571 long twosA,twosB,foursA,foursB,eights;
573 // CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
575 long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
577 twosA=(ones & b)|( u & c);
580 // CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
582 long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
584 twosB =(ones&b)|(u&c);
587 //CSA(foursA, twos, twos, twosA, twosB)
590 foursA=(twos&twosA)|(u&twosB);
593 //CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
595 long b=(A[i+4] ^ B[i+4]), c=(A[i+5] ^ B[i+5]);
597 twosA=(ones&b)|(u&c);
600 // CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
602 long b=(A[i+6] ^ B[i+6]), c=(A[i+7] ^ B[i+7]);
604 twosB=(ones&b)|(u&c);
607 //CSA(foursB, twos, twos, twosA, twosB)
610 foursB=(twos&twosA)|(u&twosB);
614 //CSA(eights, fours, fours, foursA, foursB)
617 eights=(fours&foursA)|(u&foursB);
625 long twosA, twosB, foursA, eights;
627 long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
629 twosA=(ones & b)|( u & c);
633 long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
635 twosB =(ones&b)|(u&c);
640 foursA=(twos&twosA)|(u&twosB);
651 long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
653 long twosA=(ones & b)|( u & c);
656 long foursA=twos&twosA;
659 long eights=fours&foursA;
667 tot += pop((A[i] ^ B[i]));
670 tot += (pop(fours)<<2)
678 /* python code to generate ntzTable
686 print ','.join([ str(ntz(i)) for i in range(256) ])
688 /** table of number of trailing zeros in a byte */
689 public static final byte[] ntzTable = {8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};
692 /** Returns number of trailing zeros in a 64 bit long value. */
693 public static int ntz(long val) {
694 // A full binary search to determine the low byte was slower than
695 // a linear search for nextSetBit(). This is most likely because
696 // the implementation of nextSetBit() shifts bits to the right, increasing
697 // the probability that the first non-zero byte is in the rhs.
699 // This implementation does a single binary search at the top level only
700 // so that all other bit shifting can be done on ints instead of longs to
701 // remain friendly to 32 bit architectures. In addition, the case of a
702 // non-zero first byte is checked for first because it is the most common
703 // in dense bit arrays.
705 int lower = (int)val;
706 int lowByte = lower & 0xff;
707 if (lowByte != 0) return ntzTable[lowByte];
710 lowByte = (lower>>>8) & 0xff;
711 if (lowByte != 0) return ntzTable[lowByte] + 8;
712 lowByte = (lower>>>16) & 0xff;
713 if (lowByte != 0) return ntzTable[lowByte] + 16;
714 // no need to mask off low byte for the last byte in the 32 bit word
715 // no need to check for zero on the last byte either.
716 return ntzTable[lower>>>24] + 24;
718 // grab upper 32 bits
719 int upper=(int)(val>>32);
720 lowByte = upper & 0xff;
721 if (lowByte != 0) return ntzTable[lowByte] + 32;
722 lowByte = (upper>>>8) & 0xff;
723 if (lowByte != 0) return ntzTable[lowByte] + 40;
724 lowByte = (upper>>>16) & 0xff;
725 if (lowByte != 0) return ntzTable[lowByte] + 48;
726 // no need to mask off low byte for the last byte in the 32 bit word
727 // no need to check for zero on the last byte either.
728 return ntzTable[upper>>>24] + 56;
732 /** Returns number of trailing zeros in a 32 bit int value. */
733 public static int ntz(int val) {
734 // This implementation does a single binary search at the top level only.
735 // In addition, the case of a non-zero first byte is checked for first
736 // because it is the most common in dense bit arrays.
738 int lowByte = val & 0xff;
739 if (lowByte != 0) return ntzTable[lowByte];
740 lowByte = (val>>>8) & 0xff;
741 if (lowByte != 0) return ntzTable[lowByte] + 8;
742 lowByte = (val>>>16) & 0xff;
743 if (lowByte != 0) return ntzTable[lowByte] + 16;
744 // no need to mask off low byte for the last byte.
745 // no need to check for zero on the last byte either.
746 return ntzTable[val>>>24] + 24;
749 /** returns 0 based index of first set bit
750 * (only works for x!=0)
751 * <br/> This is an alternate implementation of ntz()
753 public static int ntz2(long x) {
756 if (y==0) {n+=32; y = (int)(x>>>32); } // the only 64 bit shift necessary
757 if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
758 if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
759 return (ntzTable[ y & 0xff ]) + n;
762 /** returns 0 based index of first set bit
763 * <br/> This is an alternate implementation of ntz()
765 public static int ntz3(long x) {
766 // another implementation taken from Hackers Delight, extended to 64 bits
767 // and converted to Java.
768 // Many 32 bit ntz algorithms are at http://www.hackersdelight.org/HDcode/ntz.cc
771 // do the first step as a long, all others as ints.
773 if (y==0) {n+=32; y = (int)(x>>>32); }
774 if ((y & 0x0000FFFF) == 0) { n+=16; y>>>=16; }
775 if ((y & 0x000000FF) == 0) { n+=8; y>>>=8; }
776 if ((y & 0x0000000F) == 0) { n+=4; y>>>=4; }
777 if ((y & 0x00000003) == 0) { n+=2; y>>>=2; }
781 /** table of number of leading zeros in a byte */
782 public static final byte[] nlzTable = {8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
784 /** Returns the number of leading zero bits.
786 public static int nlz(long x) {
788 // do the first step as a long
789 int y = (int)(x>>>32);
790 if (y==0) {n+=32; y = (int)(x); }
791 if ((y & 0xFFFF0000) == 0) { n+=16; y<<=16; }
792 if ((y & 0xFF000000) == 0) { n+=8; y<<=8; }
793 return n + nlzTable[y >>> 24];
794 /* implementation without table:
795 if ((y & 0xF0000000) == 0) { n+=4; y<<=4; }
796 if ((y & 0xC0000000) == 0) { n+=2; y<<=2; }
797 if ((y & 0x80000000) == 0) { n+=1; y<<=1; }
798 if ((y & 0x80000000) == 0) { n+=1;}
804 /** returns true if v is a power of two or zero*/
805 public static boolean isPowerOfTwo(int v) {
806 return ((v & (v-1)) == 0);
809 /** returns true if v is a power of two or zero*/
810 public static boolean isPowerOfTwo(long v) {
811 return ((v & (v-1)) == 0);
814 /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
815 public static int nextHighestPowerOfTwo(int v) {
826 /** returns the next highest power of two, or the current value if it's already a power of two or zero*/
827 public static long nextHighestPowerOfTwo(long v) {