Jaki jest najskuteczniejszy sposób znalezienia indeksu lewego/prawego najbardziej niezmienionego bitu w Javie?

Question

Załóżmy, że mamy int x = 371, czyli w formacie binarnym 101110011. Chcę znaleźć indeks najbardziej zbuntowanego bitu (w tym przypadku 7) i indeksu najbardziej zbuntowanego bitu (w tym przypadku 2). Jaki jest najskuteczniejszy sposób na zrobienie tego?

Oto co mam:

public class BitOperatons { 

    public static int setBit(int x, int i) { 
     int y = x | (1 << i); 
     return y; 
    } 

    public static boolean isBitSet(int x, int i) { 
     int y = setBit(0, i); 
     return y == (x & y); 
    }  

    public static int findLeftMostSetBit(int x) { 
     for (int i = 31; i >= 0; i--) { 
      if (isBitSet(x, i)) 
       return i; 
     } 
     return -1; 
    } 

    public static int findRightMostUnsetBit(int x) { 
     for (int i = 0; i <= 31; i++) { 
      if (! isBitSet(x, i)) 
       return i; 
     } 
     return -1; 
    } 

    public static int findLeftMostUnsetBit(int x) { 
     int k = findLeftMostSetBit(x); 
     for (int i = k; i >= 0; i--) { 
      if (! isBitSet(x, i)) 
       return i; 
     } 
     return -1; 
    } 

    public static1+ void main(String[] args) { 
     int x = 
      (1 << 0) | 
      (1 << 1) | 
      (1 << 4) | 
      (1 << 5) | 
      (1 << 6) | 
      (1 << 8); 
     System.out.println(findLeftMostUnsetBit(x)); 
     System.out.println(findRightMostUnsetBit(x)); 
    } 

} 

Jeśli nie jestem zły, moja obecna realizacja wymaga czasu liniowego. Czy możemy zrobić lepiej?

Answer 1

Dostępne są metody dostępne w klasie Integer.

Integer.numberOfTrailingZeros(Integer.lowestOneBit(~yourValue)) zrobi to dla najniższego bitu nieuzbrojonego, ponieważ najwyższy jest nieco trudniejszy, ponieważ najpierw musimy ustalić najwyższy ustawiony bit.

int leadingZeroBits = Integer.numberOfLeadingZeros(Integer.highestOneBit(yourValue)); 
result = Integer. 
     numberOfTrailingZeros(Integer.highestOneBit((~yourValue)<<leadingZeroBits) 
     -leadingZeroBits;` 

powinien to zrobić na najwyższym wyłączonym bit.

Może to być szybsze niż czas liniowy, ponieważ procesory często mają instrukcje maszynowe do szybkiego ustalenia wiodącego/końcowego bitowego punktu zerowego (ale nie są pewne, czy vm je wykorzystuje EDYCJA: teraz jestem pewien ;-).

EDIT: It seems they added the use of asm intrinsics for leading/trailing zeros in 1.6.0_18, ID 6823354

Answer 2

Pod nim znajduje się kod źródłowy Integer.numberOfLeadingZeros. Jak wskazano, pochodzi z HD (Hacker's Delight, Henry S. Warren, Jr)

Główną ideą jest użycie wyszukiwania binarnego zamiast iterowania bitów, jeden po drugim. Proszę sprawdzić książkę, jeśli interesuje Cię nieco twiddling. To wspaniałe dzieło sztuki.

public static int numberOfLeadingZeros(int i) { 
    // HD, Figure 5-6 
    if (i == 0) 
     return 32; 
    int n = 1; 
    if (i >>> 16 == 0) { n += 16; i <<= 16; } 
    if (i >>> 24 == 0) { n += 8; i <<= 8; } 
    if (i >>> 28 == 0) { n += 4; i <<= 4; } 
    if (i >>> 30 == 0) { n += 2; i <<= 2; } 
    n -= i >>> 31; 
    return n; 
}