Cách hiệu quả nhất để tìm kiếm chỉ mục của bit không được đặt bên trái/bên phải nhiều nhất trong Java là gì?

Question

Giả sử rằng chúng tôi có int x = 371, có định dạng nhị phân 101110011. Tôi muốn tìm chỉ mục của bit không được đặt nhiều nhất bên trái (trong trường hợp này là 7) và chỉ mục của bit không được đặt nhiều nhất bên phải (trong trường hợp này là 2). Cách hiệu quả nhất để làm điều đó là gì?

Dưới đây là những gì tôi có:

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)); 
    } 

} 

Nếu tôi không sai, thực hiện hiện tại của tôi cần có thời gian tuyến tính. Chúng ta có thể làm tốt hơn không?

Answer 1

Có các phương pháp có sẵn trong lớp Integer.

Integer.numberOfTrailingZeros(Integer.lowestOneBit(~yourValue)) sẽ làm điều đó cho bit thấp nhất không được đặt, vì mức cao nhất sẽ khó hơn một chút vì trước tiên chúng tôi phải xác định bit đặt cao nhất.

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

Nên làm điều đó cho bit không được đặt cao nhất.

Và điều này có thể nhanh hơn thời gian tuyến tính vì bộ xử lý thường có hướng dẫn máy để xác định nhanh bit đầu/cuối không (nhưng không chắc chắn nếu vm sử dụng chúng EDIT: Bây giờ tôi chắc chắn ;-).

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

Answer 2

Dưới đây là mã nguồn của Integer.numberOfLeadingZeros. Khi nó được lấy từ HD (Delight của Delight bởi Henry S. Warren, Jr)

Ý tưởng chính là sử dụng tìm kiếm nhị phân thay vì lặp từng bit một. Xin vui lòng, kiểm tra các cuốn sách nếu bạn quan tâm đến bit twiddling. Đó là một tác phẩm nghệ thuật tuyệt vời.

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; 
}