Hangi biraz Java (ikili temsil varsa) bir tamsayı üzerinde hangi bitleri kontrol etmek için bu kodu yazdım Java

Question

bir tamsayı için açıktır:

public static List<String> list(int val) 
{ 
    List<String> dummyList = new ArrayList<String>(); 

    int bit = 1; 
    int x; 

    for(int i=0; i<32; i++) 
    { 
     x = bit; 
     if((x&val)!=0) 
      dummyList.add(String.valueOf(i+1)); 
     bit = bit << 1; 
    } 

    return dummyList; 
} 

yukarıda yazılı kod çalışıyor. Ama 32 kez çalışan bir döngü vardır (Java tamsayı 32 bit uzunluğundadır). Bu karmaşıklığı en aza indirmek istiyorum. Lütfen daha iyi çözümü paylaşın. Şimdiden teşekkürler.

Answer 1

Karmaşıklık O (1) 'dir, bu yüzden orada "en aza indirecek" çok şey yoktur.

Sizin kodunuz tamam .. burada biraz geri yüklenir.

public static List<String> list(int val) { 
    List<String> dummyList = new ArrayList<String>(); 
    for (int i = 0; i < 32; i++) 
     if ((1 << i & val) != 0) 
      dummyList.add("" + (i+1)); 
    return dummyList; 
} 

Btw, bir BitSet kullanarak kabul var?

Answer 2

32 döngü bu uygulama için iyi geliyor. Rakamları daha hızlı toplamak istiyorsanız, Listenin yerine StringBuffer kullanabilirsiniz.

public static String list(int val) 
{ 
    StringBuffer dummyList = new StringBuffer(); 

    int bit = 1; 
    int x; 

    for(int i=0; i<32; i++) 
    { 
     x = bit; 
     dummyList.append((x&val) ? '1' : '0'); 
     bit = bit << 1; 
    } 

    return dummyList.toString(); 
} 

Answer 3

O(1) kodu iyileştirilmesi önemsiz görünüyor ama bu kod biraz ilerleme kaydetmiş durumda:

public static List<String> list(int val) { 
    List<String> dummyList = new ArrayList<String>(); 
    for (int i=0; val!=0 && i<32; ++i){ 
     if ((1 << i & val) != 0) { 
      dummyList.add("" + (i+1)); 
      val &= val -1; // unset the last set bit (current bit) 
     }     // causes loop to end early when all bits are counted 
    } 
    return dummyList; 

Aksine sonra tüm 32 bitlik karşılaştırmalar yaparak

bu kod en kısa sürede son bit sayılır edildiği gibi sona erecektir. 1 s ile seyrek olarak doldurulmuş ve yüksek oranda doldurulmuş olan tamsayılar için daha az verimli olmayan tamsayılar için çok daha verimlidir.

Answer 4

Tamsayı uzunluğunu bildiğiniz için, bunun yerine bir bool[] kullanmanızı öneririm. Karmaşıklıkla ilgili yapabileceğiniz çok şey yok. Olabildiğince hızlı ve JIT muhtemelen bu kodun döngüsünü yine de açacak.

public static bool[] list(int val) 
{ 
    bool[] a = new bool[32]; 
    for(int i=0; i<32; i++) 
    { 
     a[i] = ((1 << i) & val) != 0; 
    } 
    return a; 
} 

Answer 5

Döngüden geçen süreleri azaltmaya çalışmak için bir bit maskesi kullanabilirsiniz. Birkaç işlemleri eklemek ama potansiyel yarım döngü yapmak.

public static List<String> list(int val) { 
    List<String> dummyList = new ArrayList<String>(); 
    int loop = 32; 

    // Mask the 16 MSB if all are zero only loop on the 16 LSB 
    if((val & 0xFFFF0000) == 0){ 
     loop = 16; 
    } 

    int bit = 1; 
    int x; 

    for (int i = 0; i < loop; i++) { 
     x = bit; 
     if ((x & val) != 0) { 
      dummyList.add(String.valueOf(i + 1)); 
     } 
     bit <<= 1; 
    } 

    return dummyList; 
} 

Bu durum potansiyel olarak veri geliyor bağlı süresini artıracak

Ayrıca aynı anda iki biti yaparak yarısında döngü azaltabilir:

public static List<String> list(int val) { 
    List<String> dummyList = new ArrayList<String>(); 

    int bit = 3; 
    int x; 

    for (int i = 0; i < 32; i += 2) { 
     x = (bit & val); 
     switch (x) { 
      case 1: 
       dummyList.add(String.valueOf(i + 1)); 
       break; 
      case 2: 
       dummyList.add(String.valueOf(i+2)); 
       break; 
      case 3: 
       dummyList.add(String.valueOf(i+1)); 
       dummyList.add(String.valueOf(i+2)); 
       break; 
      default: 
     } 
     val >>= 2; 
    } 

    return dummyList; 
}