← Back to branch summary

~ubuntu-branches/ubuntu/vivid/elki/vivid

« back to all changes in this revision

Viewing changes to src/de/lmu/ifi/dbs/elki/utilities/BitsUtil.java

  • Committer: Package Import Robot
  • Author(s): Erich Schubert
  • Date: 2012-12-14 20:45:15 UTC
  • mfrom: (1.1.6)
  • Revision ID: package-import@ubuntu.com-20121214204515-4m0d0er9ivtu5w9d
Tags: 0.5.5-1
New upstream release: 0.5.5 interim release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/de/lmu/ifi/dbs/elki/utilities/BitsUtil.java
112
112
   */
113
113
  public static long[] copy(long[] v, int mincap) {
114
114
    int words = ((mincap - 1) >>> LONG_LOG2_SIZE) + 1;
115
 
    if(v.length == words) {
 
115
    if (v.length == words) {
116
116
      return Arrays.copyOf(v, v.length);
117
117
    }
118
118
    long[] ret = new long[words];
132
132
   */
133
133
  public static long[] copy(long[] v, int mincap, int shift) {
134
134
    int words = ((mincap - 1) >>> LONG_LOG2_SIZE) + 1;
135
 
    if(v.length == words && shift == 0) {
 
135
    if (v.length == words && shift == 0) {
136
136
      return Arrays.copyOf(v, v.length);
137
137
    }
138
138
    long[] ret = new long[words];
139
139
    final int shiftWords = shift >>> LONG_LOG2_SIZE;
140
140
    final int shiftBits = shift & LONG_LOG2_MASK;
141
141
    // Simple case - multiple of word size
142
 
    if(shiftBits == 0) {
143
 
      for(int i = shiftWords; i < ret.length; i++) {
 
142
    if (shiftBits == 0) {
 
143
      for (int i = shiftWords; i < ret.length; i++) {
144
144
        ret[i] |= v[i - shiftWords];
145
145
      }
146
146
      return ret;
148
148
    // Overlapping case
149
149
    final int unshiftBits = Long.SIZE - shiftBits;
150
150
    final int end = Math.min(ret.length, v.length + shiftWords) - 1;
151
 
    for(int i = end; i > shiftWords; i--) {
 
151
    for (int i = end; i > shiftWords; i--) {
152
152
      final int src = i - shiftWords;
153
153
      ret[i] |= (v[src] << shiftBits) | (v[src - 1] >>> unshiftBits);
154
154
    }
206
206
    final int last = v.length - 1;
207
207
    int o;
208
208
    // Sub word level:
209
 
    for(o = 1; o < Long.SIZE; o <<= 1) {
210
 
      for(int i = 0; i < last; i++) {
 
209
    for (o = 1; o < Long.SIZE; o <<= 1) {
 
210
      for (int i = 0; i < last; i++) {
211
211
        v[i] ^= (v[i] >>> o) ^ (v[i + 1] << (Long.SIZE - o));
212
212
      }
213
213
      v[last] ^= (v[last] >>> o);
214
214
    }
215
215
    // Word level:
216
 
    for(o = 1; o <= last; o <<= 1) {
217
 
      for(int i = o; i <= last; i++) {
 
216
    for (o = 1; o <= last; o <<= 1) {
 
217
      for (int i = o; i <= last; i++) {
218
218
        v[i - o] ^= v[i];
219
219
      }
220
220
    }
228
228
   * @return true when all zero
229
229
   */
230
230
  public static boolean isZero(long[] v) {
231
 
    for(int i = 0; i < v.length; i++) {
232
 
      if(v[i] != 0) {
 
231
    for (int i = 0; i < v.length; i++) {
 
232
      if (v[i] != 0) {
233
233
        return false;
234
234
      }
235
235
    }
256
256
   */
257
257
  public static long cardinality(long[] v) {
258
258
    int sum = 0;
259
 
    for(int i = 0; i < v.length; i++) {
 
259
    for (int i = 0; i < v.length; i++) {
260
260
      sum += Long.bitCount(v[i]);
261
261
    }
262
262
    return sum;
382
382
   */
383
383
  public static long[] xorI(long[] v, long[] o) {
384
384
    assert (o.length <= v.length) : "Bit set sizes do not agree.";
385
 
    for(int i = 0; i < o.length; i++) {
 
385
    for (int i = 0; i < o.length; i++) {
386
386
      v[i] ^= o[i];
387
387
    }
388
388
    return v;
397
397
   * @return v
398
398
   */
399
399
  public static long[] xorI(long[] v, long[] o, int off) {
400
 
    if(off == 0) {
 
400
    if (off == 0) {
401
401
      return xorI(v, o);
402
402
    }
403
 
    if(off < 0) {
 
403
    if (off < 0) {
404
404
      throw new UnsupportedOperationException("Negative shifts are not supported.");
405
405
    }
406
406
    // Break shift into integers to shift and bits to shift
407
407
    final int shiftWords = off >>> LONG_LOG2_SIZE;
408
408
    final int shiftBits = off & LONG_LOG2_MASK;
409
409
 
410
 
    if(shiftWords >= v.length) {
 
410
    if (shiftWords >= v.length) {
411
411
      return v;
412
412
    }
413
413
    // Simple case - multiple of word size
414
 
    if(shiftBits == 0) {
 
414
    if (shiftBits == 0) {
415
415
      final int end = Math.min(v.length, o.length + shiftWords);
416
 
      for(int i = shiftWords; i < end; i++) {
 
416
      for (int i = shiftWords; i < end; i++) {
417
417
        v[i] ^= o[i - shiftWords];
418
418
      }
419
419
      return v;
421
421
    // Overlapping case
422
422
    final int unshiftBits = Long.SIZE - shiftBits;
423
423
    final int end = Math.min(v.length, o.length + shiftWords) - 1;
424
 
    for(int i = end; i > shiftWords; i--) {
 
424
    for (int i = end; i > shiftWords; i--) {
425
425
      final int src = i - shiftWords;
426
426
      v[i] ^= (o[src] << shiftBits) | (o[src - 1] >>> unshiftBits);
427
427
    }
439
439
  public static long[] orI(long[] v, long[] o) {
440
440
    assert (o.length <= v.length) : "Bit set sizes do not agree.";
441
441
    final int max = Math.min(v.length, o.length);
442
 
    for(int i = 0; i < max; i++) {
 
442
    for (int i = 0; i < max; i++) {
443
443
      v[i] |= o[i];
444
444
    }
445
445
    return v;
456
456
   * @return v
457
457
   */
458
458
  public static long[] orI(long[] v, long[] o, int off) {
459
 
    if(off == 0) {
 
459
    if (off == 0) {
460
460
      return orI(v, o);
461
461
    }
462
 
    if(off < 0) {
 
462
    if (off < 0) {
463
463
      throw new UnsupportedOperationException("Negative shifts are not supported.");
464
464
    }
465
465
    // Break shift into integers to shift and bits to shift
466
466
    final int shiftWords = off >>> LONG_LOG2_SIZE;
467
467
    final int shiftBits = off & LONG_LOG2_MASK;
468
468
 
469
 
    if(shiftWords >= v.length) {
 
469
    if (shiftWords >= v.length) {
470
470
      return v;
471
471
    }
472
472
    // Simple case - multiple of word size
473
 
    if(shiftBits == 0) {
 
473
    if (shiftBits == 0) {
474
474
      final int end = Math.min(v.length, o.length + shiftWords);
475
 
      for(int i = shiftWords; i < end; i++) {
 
475
      for (int i = shiftWords; i < end; i++) {
476
476
        v[i] |= o[i - shiftWords];
477
477
      }
478
478
      return v;
480
480
    // Overlapping case
481
481
    final int unshiftBits = Long.SIZE - shiftBits;
482
482
    final int end = Math.min(v.length, o.length + shiftWords) - 1;
483
 
    for(int i = end; i > shiftWords; i--) {
 
483
    for (int i = end; i > shiftWords; i--) {
484
484
      final int src = i - shiftWords;
485
485
      v[i] |= (o[src] << shiftBits) | (o[src - 1] >>> unshiftBits);
486
486
    }
497
497
   */
498
498
  public static long[] andI(long[] v, long[] o) {
499
499
    int i = 0;
500
 
    for(; i < o.length; i++) {
 
500
    for (; i < o.length; i++) {
501
501
      v[i] |= o[i];
502
502
    }
503
503
    // Zero higher words
514
514
   * @return v
515
515
   */
516
516
  public static long[] andI(long[] v, long[] o, int off) {
517
 
    if(off == 0) {
 
517
    if (off == 0) {
518
518
      return andI(v, o);
519
519
    }
520
 
    if(off < 0) {
 
520
    if (off < 0) {
521
521
      throw new UnsupportedOperationException("Negative shifts are not supported.");
522
522
    }
523
523
    // Break shift into integers to shift and bits to shift
524
524
    final int shiftWords = off >>> LONG_LOG2_SIZE;
525
525
    final int shiftBits = off & LONG_LOG2_MASK;
526
526
 
527
 
    if(shiftWords >= v.length) {
 
527
    if (shiftWords >= v.length) {
528
528
      return v;
529
529
    }
530
530
    // Simple case - multiple of word size
531
 
    if(shiftBits == 0) {
 
531
    if (shiftBits == 0) {
532
532
      final int end = Math.min(v.length, o.length + shiftWords);
533
 
      for(int i = shiftWords; i < end; i++) {
 
533
      for (int i = shiftWords; i < end; i++) {
534
534
        v[i] &= o[i - shiftWords];
535
535
      }
536
536
      // Clear bottom words
541
541
    final int unshiftBits = Long.SIZE - shiftBits;
542
542
    final int end = Math.min(v.length, o.length + shiftWords) - 1;
543
543
    Arrays.fill(v, end + 1, v.length, 0);
544
 
    for(int i = end; i > shiftWords; i--) {
 
544
    for (int i = end; i > shiftWords; i--) {
545
545
      final int src = i - shiftWords;
546
546
      v[i] &= (o[src] << shiftBits) | (o[src - 1] >>> unshiftBits);
547
547
    }
558
558
   * @return v
559
559
   */
560
560
  public static long[] invertI(long[] v) {
561
 
    for(int i = 0; i < v.length; i++) {
 
561
    for (int i = 0; i < v.length; i++) {
562
562
      v[i] = ~v[i];
563
563
    }
564
564
    return v;
574
574
   * @return Bitset
575
575
   */
576
576
  public static long[] shiftRightI(long[] v, int off) {
577
 
    if(off == 0) {
 
577
    if (off == 0) {
578
578
      return v;
579
579
    }
580
 
    if(off < 0) {
 
580
    if (off < 0) {
581
581
      return shiftLeftI(v, -off);
582
582
    }
583
583
    // Break shift into integers to shift and bits to shift
584
584
    final int shiftWords = off >>> LONG_LOG2_SIZE;
585
585
    final int shiftBits = off & LONG_LOG2_MASK;
586
586
 
587
 
    if(shiftWords >= v.length) {
 
587
    if (shiftWords >= v.length) {
588
588
      return zeroI(v);
589
589
    }
590
590
    // Simple case - multiple of word size
591
 
    if(shiftBits == 0) {
 
591
    if (shiftBits == 0) {
592
592
      // Move whole words down
593
593
      System.arraycopy(v, shiftWords, v, 0, v.length - shiftWords);
594
594
      // Fill top words with zeros
598
598
    // Overlapping case
599
599
    final int unshiftBits = Long.SIZE - shiftBits;
600
600
    // Bottom-up to not overlap the operations.
601
 
    for(int i = 0; i < v.length - shiftWords - 1; i++) {
 
601
    for (int i = 0; i < v.length - shiftWords - 1; i++) {
602
602
      final int src = i + shiftWords;
603
603
      v[i] = (v[src + 1] << unshiftBits) | (v[src] >>> shiftBits);
604
604
    }
619
619
   * @return Bitset
620
620
   */
621
621
  public static long[] shiftLeftI(long[] v, int off) {
622
 
    if(off == 0) {
 
622
    if (off == 0) {
623
623
      return v;
624
624
    }
625
 
    if(off < 0) {
 
625
    if (off < 0) {
626
626
      return shiftRightI(v, -off);
627
627
    }
628
628
    // Break shift into integers to shift and bits to shift
629
629
    final int shiftWords = off >>> LONG_LOG2_SIZE;
630
630
    final int shiftBits = off & LONG_LOG2_MASK;
631
631
 
632
 
    if(shiftWords >= v.length) {
 
632
    if (shiftWords >= v.length) {
633
633
      return zeroI(v);
634
634
    }
635
635
    // Simple case - multiple of word size
636
 
    if(shiftBits == 0) {
 
636
    if (shiftBits == 0) {
637
637
      // Move whole words up
638
638
      System.arraycopy(v, 0, v, shiftWords, v.length - shiftWords);
639
639
      // Fill the initial words with zeros
643
643
    // Overlapping case
644
644
    final int unshiftBits = Long.SIZE - shiftBits;
645
645
    // Top-Down to not overlap the operations.
646
 
    for(int i = v.length - 1; i > shiftWords; i--) {
 
646
    for (int i = v.length - 1; i > shiftWords; i--) {
647
647
      final int src = i - shiftWords;
648
648
      v[i] = (v[src] << shiftBits) | (v[src - 1] >>> unshiftBits);
649
649
    }
662
662
   * @return cycled bit set
663
663
   */
664
664
  public static long cycleRightC(long v, int shift, int len) {
665
 
    if(shift == 0) {
 
665
    if (shift == 0) {
666
666
      return v;
667
667
    }
668
 
    if(shift < 0) {
 
668
    if (shift < 0) {
669
669
      return cycleLeftC(v, -shift, len);
670
670
    }
671
671
    final long ones = (1 << len) - 1;
698
698
    final int zapWords = (zap >>> LONG_LOG2_SIZE);
699
699
    final int zapbits = zap & LONG_LOG2_MASK;
700
700
    Arrays.fill(v, v.length - zapWords, v.length, 0);
701
 
    if(zapbits > 0) {
 
701
    if (zapbits > 0) {
702
702
      v[v.length - zapWords - 1] &= (LONG_ALL_BITS >>> zapbits);
703
703
    }
704
704
    return v;
713
713
   * @return cycled bit set
714
714
   */
715
715
  public static long cycleLeftC(long v, int shift, int len) {
716
 
    if(shift == 0) {
 
716
    if (shift == 0) {
717
717
      return v;
718
718
    }
719
 
    if(shift < 0) {
 
719
    if (shift < 0) {
720
720
      return cycleRightC(v, -shift, len);
721
721
    }
722
722
    final long ones = (1 << len) - 1;
746
746
   */
747
747
  public static String toString(long[] v) {
748
748
    final int mag = magnitude(v);
749
 
    if(v.length == 0 || mag == 0) {
 
749
    if (v.length == 0 || mag == 0) {
750
750
      return "0";
751
751
    }
752
752
    final int words = ((mag - 1) >>> LONG_LOG2_SIZE) + 1;
753
753
    char[] digits = new char[mag];
754
754
 
755
755
    int pos = mag - 1;
756
 
    for(int w = 0; w < words; w++) {
757
 
      long f = 1l;
758
 
      for(int i = 0; i < Long.SIZE; i++) {
 
756
    for (int w = 0; w < words; w++) {
 
757
      long f = 1L;
 
758
      for (int i = 0; i < Long.SIZE; i++) {
759
759
        digits[pos] = ((v[w] & f) == 0) ? '0' : '1';
760
760
        pos--;
761
761
        f <<= 1;
762
 
        if(pos < 0) {
 
762
        if (pos < 0) {
763
763
          break;
764
764
        }
765
765
      }
776
776
   */
777
777
  public static String toString(long[] v, int minw) {
778
778
    final int mag = Math.max(magnitude(v), minw);
779
 
    if(v.length == 0 || mag == 0) {
 
779
    if (v.length == 0 || mag == 0) {
780
780
      return "0";
781
781
    }
782
782
    final int words = ((mag - 1) >>> LONG_LOG2_SIZE) + 1;
783
783
    char[] digits = new char[mag];
784
784
 
785
785
    int pos = mag - 1;
786
 
    for(int w = 0; w < words; w++) {
787
 
      long f = 1l;
788
 
      for(int i = 0; i < Long.SIZE; i++) {
 
786
    for (int w = 0; w < words; w++) {
 
787
      long f = 1L;
 
788
      for (int i = 0; i < Long.SIZE; i++) {
789
789
        digits[pos] = ((v[w] & f) == 0) ? '0' : '1';
790
790
        pos--;
791
791
        f <<= 1;
792
 
        if(pos < 0) {
 
792
        if (pos < 0) {
793
793
          break;
794
794
        }
795
795
      }
805
805
   */
806
806
  public static String toString(long v) {
807
807
    final int mag = magnitude(v);
808
 
    if(mag == 0) {
 
808
    if (mag == 0) {
809
809
      return "0";
810
810
    }
811
811
    char[] digits = new char[mag];
812
812
 
813
813
    int pos = mag - 1;
814
 
    long f = 1l;
815
 
    for(int i = 0; i < Long.SIZE; i++) {
 
814
    long f = 1L;
 
815
    for (int i = 0; i < Long.SIZE; i++) {
816
816
      digits[pos] = ((v & f) == 0) ? '0' : '1';
817
817
      pos--;
818
818
      f <<= 1;
819
 
      if(pos < 0) {
 
819
      if (pos < 0) {
820
820
        break;
821
821
      }
822
822
    }
830
830
   * @return Position of first set bit, -1 if no set bit was found.
831
831
   */
832
832
  public static int numberOfTrailingZerosSigned(long[] v) {
833
 
    for(int p = 0;; p++) {
834
 
      if(p == v.length) {
 
833
    for (int p = 0;; p++) {
 
834
      if (p == v.length) {
835
835
        return -1;
836
836
      }
837
 
      if(v[p] != 0) {
 
837
      if (v[p] != 0) {
838
838
        return Long.numberOfTrailingZeros(v[p]) + p * Long.SIZE;
839
839
      }
840
840
    }
847
847
   * @return Position of first set bit, v.length * 64 if no set bit was found.
848
848
   */
849
849
  public static int numberOfTrailingZeros(long[] v) {
850
 
    for(int p = 0;; p++) {
851
 
      if(p == v.length) {
 
850
    for (int p = 0;; p++) {
 
851
      if (p == v.length) {
852
852
        return p * Long.SIZE;
853
853
      }
854
 
      if(v[p] != 0) {
 
854
      if (v[p] != 0) {
855
855
        return Long.numberOfTrailingZeros(v[p]) + p * Long.SIZE;
856
856
      }
857
857
    }
860
860
  /**
861
861
   * Find the number of trailing zeros.
862
862
   * 
863
 
  * Note: this has different semantics to {@link Long#numberOfLeadingZeros}
864
 
  * when the number is 0.
 
863
   * Note: this has different semantics to {@link Long#numberOfLeadingZeros}
 
864
   * when the number is 0.
865
865
   * 
866
866
   * @param v Long
867
867
   * @return Position of first set bit, -1 if no set bit was found.
869
869
  public static int numberOfTrailingZerosSigned(long v) {
870
870
    return Long.numberOfTrailingZeros(v);
871
871
  }
872
 
  
 
872
 
873
873
  /**
874
874
   * Find the number of trailing zeros.
875
875
   * 
883
883
  }
884
884
 
885
885
  /**
 
886
   * Find the number of trailing zeros.
 
887
   * 
 
888
   * Note: this is the same as {@link Long#numberOfTrailingZeros}
 
889
   * 
 
890
   * @param v Long
 
891
   * @return Position of first set bit, 64 if no set bit was found.
 
892
   */
 
893
  public static int numberOfTrailingZeros(int v) {
 
894
    return Integer.numberOfTrailingZeros(v);
 
895
  }
 
896
 
 
897
  /**
886
898
   * Find the number of leading zeros.
887
899
   * 
888
900
   * @param v Bitset
889
901
   * @return Position of first set bit, -1 if no set bit was found.
890
902
   */
891
903
  public static int numberOfLeadingZerosSigned(long[] v) {
892
 
    for(int p = 0, ip = v.length - 1;; p++, ip--) {
893
 
      if(p == v.length) {
 
904
    for (int p = 0, ip = v.length - 1;; p++, ip--) {
 
905
      if (p == v.length) {
894
906
        return -1;
895
907
      }
896
 
      if(v[ip] != 0) {
 
908
      if (v[ip] != 0) {
897
909
        return Long.numberOfLeadingZeros(v[ip]) + p * Long.SIZE;
898
910
      }
899
911
    }
906
918
   * @return Position of first set bit, v.length * 64 if no set bit was found.
907
919
   */
908
920
  public static int numberOfLeadingZeros(long[] v) {
909
 
    for(int p = 0, ip = v.length - 1;; p++, ip--) {
910
 
      if(p == v.length) {
 
921
    for (int p = 0, ip = v.length - 1;; p++, ip--) {
 
922
      if (p == v.length) {
911
923
        return p * Long.SIZE;
912
924
      }
913
 
      if(v[ip] != 0) {
 
925
      if (v[ip] != 0) {
914
926
        return Long.numberOfLeadingZeros(v[ip]) + p * Long.SIZE;
915
927
      }
916
928
    }
926
938
   * @return Position of first set bit, -1 if no set bit was found.
927
939
   */
928
940
  public static int numberOfLeadingZerosSigned(long v) {
929
 
    if(v == 0) {
 
941
    if (v == 0) {
930
942
      return -1;
931
943
    }
932
944
    return Long.numberOfLeadingZeros(v);
933
945
  }
934
946
 
935
947
  /**
 
948
   * Find the number of leading zeros; -1 if all zero
 
949
   * 
 
950
   * Note: this has different semantics to {@link Long#numberOfLeadingZeros}
 
951
   * when the number is 0.
 
952
   * 
 
953
   * @param v Bitset
 
954
   * @return Position of first set bit, -1 if no set bit was found.
 
955
   */
 
956
  public static int numberOfLeadingZerosSigned(int v) {
 
957
    if (v == 0) {
 
958
      return -1;
 
959
    }
 
960
    return Integer.numberOfLeadingZeros(v);
 
961
  }
 
962
 
 
963
  /**
936
964
   * Find the number of leading zeros; 64 if all zero
937
965
   * 
938
966
   * Note: this the same as {@link Long#numberOfLeadingZeros}.
941
969
   * @return Position of first set bit, 64 if no set bit was found.
942
970
   */
943
971
  public static int numberOfLeadingZeros(long v) {
944
 
    return Long.numberOfLeadingZeros(v);
 
972
    return Long.SIZE - magnitude(v);
 
973
  }
 
974
 
 
975
  /**
 
976
   * Find the number of leading zeros; 64 if all zero
 
977
   * 
 
978
   * Note: this the same as {@link Long#numberOfLeadingZeros}.
 
979
   * 
 
980
   * @param v Bitset
 
981
   * @return Position of first set bit, 64 if no set bit was found.
 
982
   */
 
983
  public static int numberOfLeadingZeros(int v) {
 
984
    return Integer.SIZE - magnitude(v);
945
985
  }
946
986
 
947
987
  /**
952
992
   * @return Position of previous set bit, or -1.
953
993
   */
954
994
  public static int previousSetBit(long[] v, int start) {
955
 
    if(start == -1) {
 
995
    if (start == -1) {
956
996
      return -1;
957
997
    }
958
998
    int wordindex = start >>> LONG_LOG2_SIZE;
959
 
    if(wordindex >= v.length) {
 
999
    if (wordindex >= v.length) {
960
1000
      return magnitude(v) - 1;
961
1001
    }
962
1002
    // Initial word
963
1003
    final int off = Long.SIZE - 1 - (start & LONG_LOG2_MASK);
964
1004
    long cur = v[wordindex] & (LONG_ALL_BITS >>> off);
965
 
    for(;;) {
966
 
      if(cur != 0) {
 
1005
    for (;;) {
 
1006
      if (cur != 0) {
967
1007
        return (wordindex + 1) * Long.SIZE - 1 - Long.numberOfLeadingZeros(cur);
968
1008
      }
969
 
      if(wordindex == 0) {
 
1009
      if (wordindex == 0) {
970
1010
        return -1;
971
1011
      }
972
1012
      wordindex--;
982
1022
   * @return Position of previous clear bit, or -1.
983
1023
   */
984
1024
  public static int previousClearBit(long[] v, int start) {
985
 
    if(start == -1) {
 
1025
    if (start == -1) {
986
1026
      return -1;
987
1027
    }
988
1028
    int wordindex = start >>> LONG_LOG2_SIZE;
989
 
    if(wordindex >= v.length) {
 
1029
    if (wordindex >= v.length) {
990
1030
      return magnitude(v);
991
1031
    }
992
1032
    final int off = Long.SIZE + 1 - (start & LONG_LOG2_MASK);
993
1033
    // Initial word
994
1034
    long cur = ~v[wordindex] & (LONG_ALL_BITS >>> off);
995
 
    for(;;) {
996
 
      if(cur != 0) {
 
1035
    for (;;) {
 
1036
      if (cur != 0) {
997
1037
        return (wordindex + 1) * Long.SIZE - 1 - Long.numberOfTrailingZeros(cur);
998
1038
      }
999
 
      if(wordindex == 0) {
 
1039
      if (wordindex == 0) {
1000
1040
        return -1;
1001
1041
      }
1002
1042
      wordindex--;
1013
1053
   */
1014
1054
  public static int nextSetBit(long[] v, int start) {
1015
1055
    int wordindex = start >>> LONG_LOG2_SIZE;
1016
 
    if(wordindex >= v.length) {
 
1056
    if (wordindex >= v.length) {
1017
1057
      return -1;
1018
1058
    }
1019
1059
 
1020
1060
    // Initial word
1021
1061
    long cur = v[wordindex] & (LONG_ALL_BITS << start);
1022
 
    for(;;) {
1023
 
      if(cur != 0) {
 
1062
    for (;;) {
 
1063
      if (cur != 0) {
1024
1064
        return (wordindex * Long.SIZE) + Long.numberOfTrailingZeros(cur);
1025
1065
      }
1026
1066
      wordindex++;
1027
 
      if(wordindex == v.length) {
 
1067
      if (wordindex == v.length) {
1028
1068
        return -1;
1029
1069
      }
1030
1070
      cur = v[wordindex];
1040
1080
   */
1041
1081
  public static int nextClearBit(long[] v, int start) {
1042
1082
    int wordindex = start >>> LONG_LOG2_SIZE;
1043
 
    if(wordindex >= v.length) {
 
1083
    if (wordindex >= v.length) {
1044
1084
      return -1;
1045
1085
    }
1046
1086
 
1047
1087
    // Initial word
1048
1088
    long cur = ~v[wordindex] & (LONG_ALL_BITS << start);
1049
 
    for(; wordindex < v.length;) {
1050
 
      if(cur != 0) {
 
1089
    for (; wordindex < v.length;) {
 
1090
      if (cur != 0) {
1051
1091
        return (wordindex * Long.SIZE) + Long.numberOfTrailingZeros(cur);
1052
1092
      }
1053
1093
      wordindex++;
1063
1103
   * @return position of highest bit set, or 0.
1064
1104
   */
1065
1105
  public static int magnitude(long[] v) {
1066
 
    final int l = numberOfLeadingZerosSigned(v);
1067
 
    if(l < 0) {
1068
 
      return 0;
1069
 
    }
 
1106
    final int l = numberOfLeadingZeros(v);
1070
1107
    return capacity(v) - l;
1071
1108
  }
1072
1109
 
1077
1114
   * @return position of highest bit set, or 0.
1078
1115
   */
1079
1116
  public static int magnitude(long v) {
1080
 
    final int l = numberOfLeadingZerosSigned(v);
1081
 
    if(l < 0) {
1082
 
      return 0;
1083
 
    }
1084
 
    return Long.SIZE - l;
 
1117
    int log = 0, t;
 
1118
    if ((v & 0xffffffff00000000L) != 0) {
 
1119
      t = (int) (v >>>= 32);
 
1120
      log = 32;
 
1121
    } else {
 
1122
      t = (int) v;
 
1123
    }
 
1124
    if ((t & 0xffff0000) != 0) {
 
1125
      t >>>= 16;
 
1126
      log += 16;
 
1127
    }
 
1128
    if (t >= 256) {
 
1129
      t >>>= 8;
 
1130
      log += 8;
 
1131
    }
 
1132
    if (t >= 16) {
 
1133
      t >>>= 4;
 
1134
      log += 4;
 
1135
    }
 
1136
    if (t >= 4) {
 
1137
      t >>>= 2;
 
1138
      log += 2;
 
1139
    }
 
1140
    if (t >= 2) {
 
1141
      t >>>= 1;
 
1142
      log += 1;
 
1143
    }
 
1144
    return log + t;
 
1145
  }
 
1146
 
 
1147
  /**
 
1148
   * The magnitude is the position of the highest bit set
 
1149
   * 
 
1150
   * @param v Vector v
 
1151
   * @return position of highest bit set, or 0.
 
1152
   */
 
1153
  public static int magnitude(int v) {
 
1154
    int log = 0;
 
1155
    if ((v & 0xffff0000) != 0) {
 
1156
      v >>>= 16;
 
1157
      log = 16;
 
1158
    }
 
1159
    if (v >= 256) {
 
1160
      v >>>= 8;
 
1161
      log += 8;
 
1162
    }
 
1163
    if (v >= 16) {
 
1164
      v >>>= 4;
 
1165
      log += 4;
 
1166
    }
 
1167
    if (v >= 4) {
 
1168
      v >>>= 2;
 
1169
      log += 2;
 
1170
    }
 
1171
    if (v >= 2) {
 
1172
      v >>>= 1;
 
1173
      log += 1;
 
1174
    }
 
1175
    return log + v;
1085
1176
  }
1086
1177
 
1087
1178
  /**
1103
1194
   */
1104
1195
  public static int compare(long[] x, long[] y) {
1105
1196
    int p = Math.min(x.length, y.length) - 1;
1106
 
    for(int i = x.length - 1; i > p; i--) {
1107
 
      if(x[i] != 0) {
 
1197
    for (int i = x.length - 1; i > p; i--) {
 
1198
      if (x[i] != 0) {
1108
1199
        return +1;
1109
1200
      }
1110
1201
    }
1111
 
    for(int i = y.length - 1; i > p; i--) {
1112
 
      if(y[i] != 0) {
 
1202
    for (int i = y.length - 1; i > p; i--) {
 
1203
      if (y[i] != 0) {
1113
1204
        return -1;
1114
1205
      }
1115
1206
    }
1116
 
    for(; p >= 0; p--) {
 
1207
    for (; p >= 0; p--) {
1117
1208
      final long xp = x[p];
1118
1209
      final long yp = y[p];
1119
 
      if(xp != yp) {
1120
 
        if(xp < 0) {
1121
 
          if(yp < 0) {
 
1210
      if (xp != yp) {
 
1211
        if (xp < 0) {
 
1212
          if (yp < 0) {
1122
1213
            return (yp < xp) ? -1 : ((yp == xp) ? 0 : 1);
1123
 
          }
1124
 
          else {
 
1214
          } else {
1125
1215
            return +1;
1126
1216
          }
1127
 
        }
1128
 
        else {
1129
 
          if(yp < 0) {
 
1217
        } else {
 
1218
          if (yp < 0) {
1130
1219
            return -1;
1131
 
          }
1132
 
          else {
 
1220
          } else {
1133
1221
            return (xp < yp) ? -1 : ((xp == yp) ? 0 : 1);
1134
1222
          }
1135
1223
        }
1137
1225
    }
1138
1226
    return 0;
1139
1227
  }
1140
 
}
 
 
b'\\ No newline at end of file'
 
1228
}