lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/BitUtil.java

   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 package org.apache.lucene.util; // from org.apache.solr.util rev 555343
  19
  20 /**  A variety of high efficiency bit twiddling routines.
  21  * @lucene.internal
  22  */
  23 public final class BitUtil {
  24
  25   private BitUtil() {} // no instance
  26
  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
  31    *
  32   int pop(unsigned x) {
  33      x = x - ((x >> 1) & 0x55555555);
  34      x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  35      x = (x + (x >> 4)) & 0x0F0F0F0F;
  36      x = x + (x >> 8);
  37      x = x + (x >> 16);
  38      return x & 0x0000003F;
  39     }
  40   ***/
  41
  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;
  46     x = x + (x >>> 8);
  47     x = x + (x >>> 16);
  48     x = x + (x >>> 32);
  49     return ((int)x) & 0x7F;
  50   }
  51
  52   /*** Returns the number of set bits in an array of longs. */
  53   public static long pop_array(long A[], int wordOffset, int numWords) {
  54     /*
  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
  59     *
  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...
  62     *
  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'
  66     *
  67     */
  68     int n = wordOffset+numWords;
  69     long tot=0, tot8=0;
  70     long ones=0, twos=0, fours=0;
  71
  72     int i;
  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;}
  78        ***/
  79
  80       long twosA,twosB,foursA,foursB,eights;
  81
  82       // CSA(twosA, ones, ones, A[i], A[i+1])
  83       {
  84         long b=A[i], c=A[i+1];
  85         long u=ones ^ b;
  86         twosA=(ones & b)|( u & c);
  87         ones=u^c;
  88       }
  89       // CSA(twosB, ones, ones, A[i+2], A[i+3])
  90       {
  91         long b=A[i+2], c=A[i+3];
  92         long u=ones^b;
  93         twosB =(ones&b)|(u&c);
  94         ones=u^c;
  95       }
  96       //CSA(foursA, twos, twos, twosA, twosB)
  97       {
  98         long u=twos^twosA;
  99         foursA=(twos&twosA)|(u&twosB);
 100         twos=u^twosB;
 101       }
 102       //CSA(twosA, ones, ones, A[i+4], A[i+5])
 103       {
 104         long b=A[i+4], c=A[i+5];
 105         long u=ones^b;
 106         twosA=(ones&b)|(u&c);
 107         ones=u^c;
 108       }
 109       // CSA(twosB, ones, ones, A[i+6], A[i+7])
 110       {
 111         long b=A[i+6], c=A[i+7];
 112         long u=ones^b;
 113         twosB=(ones&b)|(u&c);
 114         ones=u^c;
 115       }
 116       //CSA(foursB, twos, twos, twosA, twosB)
 117       {
 118         long u=twos^twosA;
 119         foursB=(twos&twosA)|(u&twosB);
 120         twos=u^twosB;
 121       }
 122
 123       //CSA(eights, fours, fours, foursA, foursB)
 124       {
 125         long u=fours^foursA;
 126         eights=(fours&foursA)|(u&foursB);
 127         fours=u^foursB;
 128       }
 129       tot8 += pop(eights);
 130     }
 131
 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]);
 137
 138     if (i<=n-4) {
 139       long twosA, twosB, foursA, eights;
 140       {
 141         long b=A[i], c=A[i+1];
 142         long u=ones ^ b;
 143         twosA=(ones & b)|( u & c);
 144         ones=u^c;
 145       }
 146       {
 147         long b=A[i+2], c=A[i+3];
 148         long u=ones^b;
 149         twosB =(ones&b)|(u&c);
 150         ones=u^c;
 151       }
 152       {
 153         long u=twos^twosA;
 154         foursA=(twos&twosA)|(u&twosB);
 155         twos=u^twosB;
 156       }
 157       eights=fours&foursA;
 158       fours=fours^foursA;
 159
 160       tot8 += pop(eights);
 161       i+=4;
 162     }
 163
 164     if (i<=n-2) {
 165       long b=A[i], c=A[i+1];
 166       long u=ones ^ b;
 167       long twosA=(ones & b)|( u & c);
 168       ones=u^c;
 169
 170       long foursA=twos&twosA;
 171       twos=twos^twosA;
 172
 173       long eights=fours&foursA;
 174       fours=fours^foursA;
 175
 176       tot8 += pop(eights);
 177       i+=2;
 178     }
 179
 180     if (i<n) {
 181       tot += pop(A[i]);
 182     }
 183
 184     tot += (pop(fours)<<2)
 185             + (pop(twos)<<1)
 186             + pop(ones)
 187             + (tot8<<3);
 188
 189     return tot;
 190   }
 191
 192   /** Returns the popcount or cardinality of the two sets after an intersection.
 193    * Neither array is modified.
 194    */
 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;
 198     long tot=0, tot8=0;
 199     long ones=0, twos=0, fours=0;
 200
 201     int i;
 202     for (i = wordOffset; i <= n - 8; i+=8) {
 203       long twosA,twosB,foursA,foursB,eights;
 204
 205       // CSA(twosA, ones, ones, (A[i] & B[i]), (A[i+1] & B[i+1]))
 206       {
 207         long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
 208         long u=ones ^ b;
 209         twosA=(ones & b)|( u & c);
 210         ones=u^c;
 211       }
 212       // CSA(twosB, ones, ones, (A[i+2] & B[i+2]), (A[i+3] & B[i+3]))
 213       {
 214         long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
 215         long u=ones^b;
 216         twosB =(ones&b)|(u&c);
 217         ones=u^c;
 218       }
 219       //CSA(foursA, twos, twos, twosA, twosB)
 220       {
 221         long u=twos^twosA;
 222         foursA=(twos&twosA)|(u&twosB);
 223         twos=u^twosB;
 224       }
 225       //CSA(twosA, ones, ones, (A[i+4] & B[i+4]), (A[i+5] & B[i+5]))
 226       {
 227         long b=(A[i+4] & B[i+4]), c=(A[i+5] & B[i+5]);
 228         long u=ones^b;
 229         twosA=(ones&b)|(u&c);
 230         ones=u^c;
 231       }
 232       // CSA(twosB, ones, ones, (A[i+6] & B[i+6]), (A[i+7] & B[i+7]))
 233       {
 234         long b=(A[i+6] & B[i+6]), c=(A[i+7] & B[i+7]);
 235         long u=ones^b;
 236         twosB=(ones&b)|(u&c);
 237         ones=u^c;
 238       }
 239       //CSA(foursB, twos, twos, twosA, twosB)
 240       {
 241         long u=twos^twosA;
 242         foursB=(twos&twosA)|(u&twosB);
 243         twos=u^twosB;
 244       }
 245
 246       //CSA(eights, fours, fours, foursA, foursB)
 247       {
 248         long u=fours^foursA;
 249         eights=(fours&foursA)|(u&foursB);
 250         fours=u^foursB;
 251       }
 252       tot8 += pop(eights);
 253     }
 254
 255
 256     if (i<=n-4) {
 257       long twosA, twosB, foursA, eights;
 258       {
 259         long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
 260         long u=ones ^ b;
 261         twosA=(ones & b)|( u & c);
 262         ones=u^c;
 263       }
 264       {
 265         long b=(A[i+2] & B[i+2]), c=(A[i+3] & B[i+3]);
 266         long u=ones^b;
 267         twosB =(ones&b)|(u&c);
 268         ones=u^c;
 269       }
 270       {
 271         long u=twos^twosA;
 272         foursA=(twos&twosA)|(u&twosB);
 273         twos=u^twosB;
 274       }
 275       eights=fours&foursA;
 276       fours=fours^foursA;
 277
 278       tot8 += pop(eights);
 279       i+=4;
 280     }
 281
 282     if (i<=n-2) {
 283       long b=(A[i] & B[i]), c=(A[i+1] & B[i+1]);
 284       long u=ones ^ b;
 285       long twosA=(ones & b)|( u & c);
 286       ones=u^c;
 287
 288       long foursA=twos&twosA;
 289       twos=twos^twosA;
 290
 291       long eights=fours&foursA;
 292       fours=fours^foursA;
 293
 294       tot8 += pop(eights);
 295       i+=2;
 296     }
 297
 298     if (i<n) {
 299       tot += pop((A[i] & B[i]));
 300     }
 301
 302     tot += (pop(fours)<<2)
 303             + (pop(twos)<<1)
 304             + pop(ones)
 305             + (tot8<<3);
 306
 307     return tot;
 308   }
 309
 310   /** Returns the popcount or cardinality of the union of two sets.
 311     * Neither array is modified.
 312     */
 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;
 316      long tot=0, tot8=0;
 317      long ones=0, twos=0, fours=0;
 318
 319      int i;
 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;}
 325         ***/
 326
 327        long twosA,twosB,foursA,foursB,eights;
 328
 329        // CSA(twosA, ones, ones, (A[i] | B[i]), (A[i+1] | B[i+1]))
 330        {
 331          long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
 332          long u=ones ^ b;
 333          twosA=(ones & b)|( u & c);
 334          ones=u^c;
 335        }
 336        // CSA(twosB, ones, ones, (A[i+2] | B[i+2]), (A[i+3] | B[i+3]))
 337        {
 338          long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
 339          long u=ones^b;
 340          twosB =(ones&b)|(u&c);
 341          ones=u^c;
 342        }
 343        //CSA(foursA, twos, twos, twosA, twosB)
 344        {
 345          long u=twos^twosA;
 346          foursA=(twos&twosA)|(u&twosB);
 347          twos=u^twosB;
 348        }
 349        //CSA(twosA, ones, ones, (A[i+4] | B[i+4]), (A[i+5] | B[i+5]))
 350        {
 351          long b=(A[i+4] | B[i+4]), c=(A[i+5] | B[i+5]);
 352          long u=ones^b;
 353          twosA=(ones&b)|(u&c);
 354          ones=u^c;
 355        }
 356        // CSA(twosB, ones, ones, (A[i+6] | B[i+6]), (A[i+7] | B[i+7]))
 357        {
 358          long b=(A[i+6] | B[i+6]), c=(A[i+7] | B[i+7]);
 359          long u=ones^b;
 360          twosB=(ones&b)|(u&c);
 361          ones=u^c;
 362        }
 363        //CSA(foursB, twos, twos, twosA, twosB)
 364        {
 365          long u=twos^twosA;
 366          foursB=(twos&twosA)|(u&twosB);
 367          twos=u^twosB;
 368        }
 369
 370        //CSA(eights, fours, fours, foursA, foursB)
 371        {
 372          long u=fours^foursA;
 373          eights=(fours&foursA)|(u&foursB);
 374          fours=u^foursB;
 375        }
 376        tot8 += pop(eights);
 377      }
 378
 379
 380      if (i<=n-4) {
 381        long twosA, twosB, foursA, eights;
 382        {
 383          long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
 384          long u=ones ^ b;
 385          twosA=(ones & b)|( u & c);
 386          ones=u^c;
 387        }
 388        {
 389          long b=(A[i+2] | B[i+2]), c=(A[i+3] | B[i+3]);
 390          long u=ones^b;
 391          twosB =(ones&b)|(u&c);
 392          ones=u^c;
 393        }
 394        {
 395          long u=twos^twosA;
 396          foursA=(twos&twosA)|(u&twosB);
 397          twos=u^twosB;
 398        }
 399        eights=fours&foursA;
 400        fours=fours^foursA;
 401
 402        tot8 += pop(eights);
 403        i+=4;
 404      }
 405
 406      if (i<=n-2) {
 407        long b=(A[i] | B[i]), c=(A[i+1] | B[i+1]);
 408        long u=ones ^ b;
 409        long twosA=(ones & b)|( u & c);
 410        ones=u^c;
 411
 412        long foursA=twos&twosA;
 413        twos=twos^twosA;
 414
 415        long eights=fours&foursA;
 416        fours=fours^foursA;
 417
 418        tot8 += pop(eights);
 419        i+=2;
 420      }
 421
 422      if (i<n) {
 423        tot += pop((A[i] | B[i]));
 424      }
 425
 426      tot += (pop(fours)<<2)
 427              + (pop(twos)<<1)
 428              + pop(ones)
 429              + (tot8<<3);
 430
 431      return tot;
 432    }
 433
 434   /** Returns the popcount or cardinality of A & ~B
 435    * Neither array is modified.
 436    */
 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;
 440     long tot=0, tot8=0;
 441     long ones=0, twos=0, fours=0;
 442
 443     int i;
 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;}
 449        ***/
 450
 451       long twosA,twosB,foursA,foursB,eights;
 452
 453       // CSA(twosA, ones, ones, (A[i] & ~B[i]), (A[i+1] & ~B[i+1]))
 454       {
 455         long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
 456         long u=ones ^ b;
 457         twosA=(ones & b)|( u & c);
 458         ones=u^c;
 459       }
 460       // CSA(twosB, ones, ones, (A[i+2] & ~B[i+2]), (A[i+3] & ~B[i+3]))
 461       {
 462         long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
 463         long u=ones^b;
 464         twosB =(ones&b)|(u&c);
 465         ones=u^c;
 466       }
 467       //CSA(foursA, twos, twos, twosA, twosB)
 468       {
 469         long u=twos^twosA;
 470         foursA=(twos&twosA)|(u&twosB);
 471         twos=u^twosB;
 472       }
 473       //CSA(twosA, ones, ones, (A[i+4] & ~B[i+4]), (A[i+5] & ~B[i+5]))
 474       {
 475         long b=(A[i+4] & ~B[i+4]), c=(A[i+5] & ~B[i+5]);
 476         long u=ones^b;
 477         twosA=(ones&b)|(u&c);
 478         ones=u^c;
 479       }
 480       // CSA(twosB, ones, ones, (A[i+6] & ~B[i+6]), (A[i+7] & ~B[i+7]))
 481       {
 482         long b=(A[i+6] & ~B[i+6]), c=(A[i+7] & ~B[i+7]);
 483         long u=ones^b;
 484         twosB=(ones&b)|(u&c);
 485         ones=u^c;
 486       }
 487       //CSA(foursB, twos, twos, twosA, twosB)
 488       {
 489         long u=twos^twosA;
 490         foursB=(twos&twosA)|(u&twosB);
 491         twos=u^twosB;
 492       }
 493
 494       //CSA(eights, fours, fours, foursA, foursB)
 495       {
 496         long u=fours^foursA;
 497         eights=(fours&foursA)|(u&foursB);
 498         fours=u^foursB;
 499       }
 500       tot8 += pop(eights);
 501     }
 502
 503
 504     if (i<=n-4) {
 505       long twosA, twosB, foursA, eights;
 506       {
 507         long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
 508         long u=ones ^ b;
 509         twosA=(ones & b)|( u & c);
 510         ones=u^c;
 511       }
 512       {
 513         long b=(A[i+2] & ~B[i+2]), c=(A[i+3] & ~B[i+3]);
 514         long u=ones^b;
 515         twosB =(ones&b)|(u&c);
 516         ones=u^c;
 517       }
 518       {
 519         long u=twos^twosA;
 520         foursA=(twos&twosA)|(u&twosB);
 521         twos=u^twosB;
 522       }
 523       eights=fours&foursA;
 524       fours=fours^foursA;
 525
 526       tot8 += pop(eights);
 527       i+=4;
 528     }
 529
 530     if (i<=n-2) {
 531       long b=(A[i] & ~B[i]), c=(A[i+1] & ~B[i+1]);
 532       long u=ones ^ b;
 533       long twosA=(ones & b)|( u & c);
 534       ones=u^c;
 535
 536       long foursA=twos&twosA;
 537       twos=twos^twosA;
 538
 539       long eights=fours&foursA;
 540       fours=fours^foursA;
 541
 542       tot8 += pop(eights);
 543       i+=2;
 544     }
 545
 546     if (i<n) {
 547       tot += pop((A[i] & ~B[i]));
 548     }
 549
 550     tot += (pop(fours)<<2)
 551             + (pop(twos)<<1)
 552             + pop(ones)
 553             + (tot8<<3);
 554
 555     return tot;
 556   }
 557
 558   public static long pop_xor(long A[], long B[], int wordOffset, int numWords) {
 559     int n = wordOffset+numWords;
 560     long tot=0, tot8=0;
 561     long ones=0, twos=0, fours=0;
 562
 563     int i;
 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;}
 569        ***/
 570
 571       long twosA,twosB,foursA,foursB,eights;
 572
 573       // CSA(twosA, ones, ones, (A[i] ^ B[i]), (A[i+1] ^ B[i+1]))
 574       {
 575         long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
 576         long u=ones ^ b;
 577         twosA=(ones & b)|( u & c);
 578         ones=u^c;
 579       }
 580       // CSA(twosB, ones, ones, (A[i+2] ^ B[i+2]), (A[i+3] ^ B[i+3]))
 581       {
 582         long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
 583         long u=ones^b;
 584         twosB =(ones&b)|(u&c);
 585         ones=u^c;
 586       }
 587       //CSA(foursA, twos, twos, twosA, twosB)
 588       {
 589         long u=twos^twosA;
 590         foursA=(twos&twosA)|(u&twosB);
 591         twos=u^twosB;
 592       }
 593       //CSA(twosA, ones, ones, (A[i+4] ^ B[i+4]), (A[i+5] ^ B[i+5]))
 594       {
 595         long b=(A[i+4] ^ B[i+4]), c=(A[i+5] ^ B[i+5]);
 596         long u=ones^b;
 597         twosA=(ones&b)|(u&c);
 598         ones=u^c;
 599       }
 600       // CSA(twosB, ones, ones, (A[i+6] ^ B[i+6]), (A[i+7] ^ B[i+7]))
 601       {
 602         long b=(A[i+6] ^ B[i+6]), c=(A[i+7] ^ B[i+7]);
 603         long u=ones^b;
 604         twosB=(ones&b)|(u&c);
 605         ones=u^c;
 606       }
 607       //CSA(foursB, twos, twos, twosA, twosB)
 608       {
 609         long u=twos^twosA;
 610         foursB=(twos&twosA)|(u&twosB);
 611         twos=u^twosB;
 612       }
 613
 614       //CSA(eights, fours, fours, foursA, foursB)
 615       {
 616         long u=fours^foursA;
 617         eights=(fours&foursA)|(u&foursB);
 618         fours=u^foursB;
 619       }
 620       tot8 += pop(eights);
 621     }
 622
 623
 624     if (i<=n-4) {
 625       long twosA, twosB, foursA, eights;
 626       {
 627         long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
 628         long u=ones ^ b;
 629         twosA=(ones & b)|( u & c);
 630         ones=u^c;
 631       }
 632       {
 633         long b=(A[i+2] ^ B[i+2]), c=(A[i+3] ^ B[i+3]);
 634         long u=ones^b;
 635         twosB =(ones&b)|(u&c);
 636         ones=u^c;
 637       }
 638       {
 639         long u=twos^twosA;
 640         foursA=(twos&twosA)|(u&twosB);
 641         twos=u^twosB;
 642       }
 643       eights=fours&foursA;
 644       fours=fours^foursA;
 645
 646       tot8 += pop(eights);
 647       i+=4;
 648     }
 649
 650     if (i<=n-2) {
 651       long b=(A[i] ^ B[i]), c=(A[i+1] ^ B[i+1]);
 652       long u=ones ^ b;
 653       long twosA=(ones & b)|( u & c);
 654       ones=u^c;
 655
 656       long foursA=twos&twosA;
 657       twos=twos^twosA;
 658
 659       long eights=fours&foursA;
 660       fours=fours^foursA;
 661
 662       tot8 += pop(eights);
 663       i+=2;
 664     }
 665
 666     if (i<n) {
 667       tot += pop((A[i] ^ B[i]));
 668     }
 669
 670     tot += (pop(fours)<<2)
 671             + (pop(twos)<<1)
 672             + pop(ones)
 673             + (tot8<<3);
 674
 675     return tot;
 676   }
 677
 678   /* python code to generate ntzTable
 679   def ntz(val):
 680     if val==0: return 8
 681     i=0
 682     while (val&0x01)==0:
 683       i = i+1
 684       val >>= 1
 685     return i
 686   print ','.join([ str(ntz(i)) for i in range(256) ])
 687   ***/
 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};
 690
 691
 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.
 698     //
 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.
 704
 705     int lower = (int)val;
 706     int lowByte = lower & 0xff;
 707     if (lowByte != 0) return ntzTable[lowByte];
 708
 709     if (lower!=0) {
 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;
 717     } else {
 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;
 729     }
 730   }
 731
 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.
 737
 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;
 747   }
 748
 749   /** returns 0 based index of first set bit
 750    * (only works for x!=0)
 751    * <br/> This is an alternate implementation of ntz()
 752    */
 753   public static int ntz2(long x) {
 754    int n = 0;
 755    int y = (int)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;
 760   }
 761
 762   /** returns 0 based index of first set bit
 763    * <br/> This is an alternate implementation of ntz()
 764    */
 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
 769    int n = 1;
 770
 771    // do the first step as a long, all others as ints.
 772    int y = (int)x;
 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; }
 778    return n - (y & 1);
 779   }
 780
 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};
 783
 784   /** Returns the number of leading zero bits.
 785    */
 786   public static int nlz(long x) {
 787    int n = 0;
 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;}
 799    return n;
 800   */
 801   }
 802
 803
 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);
 807   }
 808
 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);
 812   }
 813
 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) {
 816     v--;
 817     v |= v >> 1;
 818     v |= v >> 2;
 819     v |= v >> 4;
 820     v |= v >> 8;
 821     v |= v >> 16;
 822     v++;
 823     return v;
 824   }
 825
 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) {
 828     v--;
 829     v |= v >> 1;
 830     v |= v >> 2;
 831     v |= v >> 4;
 832     v |= v >> 8;
 833     v |= v >> 16;
 834     v |= v >> 32;
 835     v++;
 836     return v;
 837   }
 838
 839 }