जावा में बाएं/दाएं-सबसे अनसेट बिट की अनुक्रमणिका ढूँढने का सबसे प्रभावी तरीका क्या है?

Question

मान लीजिए कि हमारे पास int x = 371 है, जो बाइनरी प्रारूप 101110011 में है। मैं बाएं सबसे अनसेट बिट (इस मामले में 7) की अनुक्रमणिका, और सही-अनसेट बिट की अनुक्रमणिका (इस मामले में 2) को ढूंढना चाहता हूं। ऐसा करने का सबसे प्रभावी तरीका क्या है? अगर मैं गलत नहीं हूँ, मेरे वर्तमान कार्यान्वयन रैखिक समय लगता है

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

} 

:

यहाँ मैं क्या है है। क्या हम बेहतर कर सकते हैं?

Answer 1

इंटेगर कक्षा में विधियां उपलब्ध हैं।

Integer.numberOfTrailingZeros(Integer.lowestOneBit(~yourValue)) इसे सबसे कम एक अनसेट बिट के लिए करेगा, क्योंकि यह उच्चतम सेट है क्योंकि हमें सबसे पहले सेट बिट निर्धारित करना है।

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

इसे उच्चतम अनसेट बिट के लिए करना चाहिए।

और यह रैखिक समय से तेज़ हो सकता है क्योंकि प्रोसेसर के पास अक्सर अग्रणी/पिछला शून्य बिट निर्धारित करने के लिए मशीन निर्देश होते हैं (लेकिन यह सुनिश्चित नहीं है कि वीएम उनका उपयोग संपादित करें: मुझे अब यकीन है ;-)।

संपादित: It seems they added the use of asm intrinsics for leading/trailing zeros in 1.6.0_18, ID 6823354

Answer 2

यह नीचे Integer.numberOfLeadingZeros के स्रोत कोड है। जैसा कि यह इंगित किया गया है कि एचडी से लिया गया है (हेनरी एस वॉरेन, जूनियर द्वारा हैकर का डिलाइट)

मुख्य विचार बिट्स को दोहराने के बजाय बाइनरी खोज का उपयोग कर रहा है। कृपया, यदि आप थोड़ा twiddling में रुचि रखते हैं तो पुस्तक की जांच करें। यह कला का एक अद्भुत टुकड़ा है।

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