Tìm thứ tự cao nhất 1 trong Java nguyên thủy

Question

Tôi cần tìm thứ tự cao nhất 1 trong một số thời gian, số nguyên và quần short trong Java. Ví dụ, nếu tôi có một char trông giống như 00110101, tôi cần một phương thức sẽ trả về 2 (chỉ số thứ tự cao nhất 1).

Bây giờ, tôi biết rằng bạn có thể làm điều này bằng cách sử dụng vòng lặp for như:

for(int i=0; i<8; i++) 
    if((x & 1<<i) != 0) return i; 
return -1; 

nhưng đây là cách chậm hơn so với những gì tôi muốn làm. Tôi biết các CPU hiện đại có hướng dẫn làm điều này trên chip, vì vậy tôi muốn biết làm thế nào tôi có thể thực hiện cuộc gọi đến đó thay vì có một vòng lặp rõ ràng.

CHỈNH SỬA: Điểm thưởng nếu bạn chỉ có thể trả về các chỉ mục của tất cả các số nguyên trong số nguyên thủy.

Cảm ơn.

Answer 1

Integer.numberOfLeadingZeros(i) + 1

Đó phương pháp sử dụng một cách tiếp cận thoải mái chia-và-chinh phục, sao chép vào đây để đánh giá của bạn:

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

Answer 2

Tôi không biết về việc nhấn lệnh CPU, nhưng tôi biết rằng điều này sẽ nhanh hơn rất nhiều nếu bạn bỏ vòng lặp và sử dụng mặt nạ bit rõ ràng.

Ngoài ra, một char không phải là 8 bit ... Tôi nghĩ bạn có thể có nghĩa là một byte.

Answer 3

Trang "Bit Twiddling Hacks" chứa nhiều hacks bit. Một cách là tìm số index of the highest order bit.

Answer 4

Theo như tôi có thể nói, Pentium và bạn bè không có hướng dẫn sẵn sàng cho việc này. Vì vậy, điều cần làm là sử dụng một thuật toán phong nha.

Chìa khóa để nhận câu trả lời của bạn nhanh chóng là sử dụng tìm kiếm nhị phân. Bạn đang xem một số long với 64 bit? 6 so sánh sẽ cung cấp cho bạn bit cao nhất của bạn, mỗi lần.

Mã hoạt động với một cây xấu xí lớn gồm 64 câu lệnh, nhưng chỉ một phần nhỏ sẽ được thực thi, vì vậy thời gian chạy là tốt.

Nếu bạn cần mã mẫu, tôi có thể làm điều đó. Nhưng tôi không muốn.

Answer 5

Tôi không có ý tưởng nếu điều này là nhanh hơn. Nhưng nó không có vòng lặp.

if(i==0) return -1; 

highest=0; 
if (i & 0xffff0000) 
{ 
    highest+=16; 
    i>>=16; 
} 
if (i & 0xff00) 
{ 
    highest+=8; 
    i>>=8; 
} 
if (i & 0xf0) 
{ 
    highest+=4; 
    i>>=4; 
} 
if (i & 0xC) 
{ 
    highest+=2; 
    i>>=2; 
} 
if (i & 0x2) 
{ 
    highest+=1; 
} 

return highest; 

Answer 6

Java được biên dịch thành bytecode độc ​​lập nền tảng, bạn không thể mong đợi hỗ trợ cho hướng dẫn CPU. Nếu không, mã của bạn hoặc Integer.highestOneBit() phải nhanh như nó được.

Answer 7

Có giống như sau này không?

System.out.println("00110101".indexOf("1"));